iGraph - SergiuTripon/msc-thesis-na-epsrc GitHub Wiki

Home ▸ Tools ▸ iGraph

Contents

1. Use

  • 10 functions related to communities
  • analysing the networks
  • visualising the networks
  • applying community detection algorithms to the networks

2. Functions related to communities

2.1 community_fastgreedy

2.1.1 Description

Community structure based on the greedy optimization of modularity.

This algorithm merges individual nodes into communities in a way that greedily maximizes the modularity score of the graph. It can be proven that if no merge can increase the current modularity score, the algorithm can be stopped since no further increase can be achieved.

This algorithm is said to run almost in linear time on sparse graphs.

2.1.2 Reference

  • A Clauset, MEJ Newman and C Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004).

Back to Top

2.2 community_infomap

2.2.1 Description

Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T. Bergstrom.

2.2.2 References

Back to Top

2.3 community_leading_eigenvector_naive

2.3.1 Description

A naive implementation of Newman's eigenvector community structure detection.

This function splits the network into two components according to the leading eigenvector of the modularity matrix and then recursively takes the given number of steps by splitting the communities as individual networks.

This is not the correct way, however, see the reference for explanation. Consider using the correct community_leading_eigenvector method instead.

2.3.2 Reference

  • MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, arXiv:physics/0605087

Back to Top

2.4 community_leading_eigenvector

2.4.1 Description

Newman's leading eigenvector method for detecting community structure. This is the proper implementation of the recursive, divisive algorithm: each split is done by maximizing the modularity regarding the original network.

2.4.2 Reference

  • MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, arXiv:physics/0605087

Back to Top

2.5 community_label_propagation

2.5.1 Description

Finds the community structure of the graph according to the label propagation method of Raghavan et al.

Initially, each vertex is assigned a different label. After that, each vertex chooses the dominant label in its neighbourhood in each iteration. Ties are broken randomly and the order in which the vertices are updated is randomized before every iteration. The algorithm ends when vertices reach a consensus. Note that since ties are broken randomly, there is no guarantee that the algorithm returns the same community structure after each run. In fact, they frequently differ.

See the paper of Raghavan et al on how to come up with an aggregated community structure.

2.5.2 Reference

  • Raghavan, U.N. and Albert, R. and Kumara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106, 2007. http://arxiv.org/abs/0709.2938.

Back to Top

2.6 community_multilevel

2.6.1 Description

Community structure based on the multilevel algorithm of Blondel et al.

This is a bottom-up algorithm: initially every vertex belongs to a separate community, and vertices are moved between communities iteratively in a way that maximizes the vertices' local contribution to the overall modularity score. When a consensus is reached (i.e. no single move would increase the modularity score), every community in the original graph is shrank to a single vertex (while keeping the total weight of the adjacent edges) and the process continues on the next level. The algorithm stops when it is not possible to increase the modularity any more after shrinking the communities to vertices.

This algorithm is said to run almost in linear time on sparse graphs.

2.6.2 Reference

  • VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks, J Stat Mech P10008 (2008), http://arxiv.org/abs/0803.0476

Back to Top

2.7 community_optimal_modularity

2.7.1 Description

Calculates the optimal modularity score of the graph and the corresponding community structure.

This function uses the GNU Linear Programming Kit to solve a large integer optimization problem in order to find the optimal modularity score and the corresponding community structure, therefore it is unlikely to work for graphs larger than a few (less than a hundred) vertices. Consider using one of the heuristic approaches instead if you have such a large graph.

Back to Top

2.8 community_edge_betweenness

2.8.1 Description

Community structure based on the betweenness of the edges in the network.

The idea is that the betweenness of the edges connecting two communities is typically high, as many of the shortest paths between nodes in separate communities go through them. So we gradually remove the edge with the highest betweenness and recalculate the betweennesses after every removal. This way sooner or later the network falls of to separate components. The result of the clustering will be represented by a dendrogram.

Back to Top

2.9 community_spinglass

2.9.1 Description

Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt.

2.9.2 References

Back to Top

2.10 community_walktrap

2.10.1 Description

Community detection algorithm of Latapy & Pons, based on random walks.

The basic idea of the algorithm is that short random walks tend to stay in the same community. The result of the clustering will be represented as a dendrogram.

2.10.2 Reference

Back to Top