Seminars in Social Networks and Markets -- Academic Year 2016/17

Project Request :

Compute basic statistics (degree distribution) and advanced statistics (clustering coefficient, closeness/betweenness centrality, etc.) for one of the networks of the Stanford Large Network Dataset Collection.

If the network is too large, you should use some approximation algorithm (see below for references). Visualize the results using a plotting software such as gnuplot, Gephi or R.

Implement the fast approximation algorithm of Eppstein and Wang for closeness centrality and use it to compute the closeness centrality of the nodes of a large network.

Implement one of the fast approximation algorithms of Riondato and Kornaropoulos for betweenness centrality and use it to compute the betweenness centrality of the nodes of a large network.

Dataset : http://snap.stanford.edu/data/egonets-Twitter.html

centrality.pptx : related algorithms brief description and results for the measurements

AdjacencyList.py : create Adjacency List. Input: Twitter data files with name format:NodeId.edges. Output : in_degree.csv and out_degree.csv

for the measurments : Input in_degree.csv and out_degree.csv files

degree_centrality.py : calculate in-degree and out-degree.

closeness_centrality.py : calculate closeness for the each node in the graph

betweenness_centrality.py : calculate betweenness for each node in the graph

[1] Centrality Wikipedia

[2] Centrality measures

[3] David Eppstein, Joseph Wang. Fast Approximation of Centrality

[4] Ulrik Brandes. A Faster Algorithm for Betweenness Centrality

[5] Matteo Riondato, Evgenios M. Kornaropoulos. Fast Approximation of Betweenness Centrality through Sampling