igraph.community

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.

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.

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

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.

Also note that the community _labels_ (numbers) have no semantic meaning and igraph is free to re-number communities. If you use fixed labels, igraph may still re-number the communities, but co-community membership constraints will be respected: if you had two vertices with fixed labels that belonged to the same community, they will still be in the same community at the end. Similarly, if you had two vertices with fixed labels that belonged to different communities, they will still be in different communities at the end.

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.

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 Graph.community_leading_eigenvector method instead.

Finds the community structure of the graph using the Leiden algorithm of Traag, van Eck & Waltman.

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 incident 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.

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.

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

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.

Returns some k-cores of the graph.

The method accepts an arbitrary number of arguments representing the desired indices of the k-cores to be returned. The arguments can also be lists or tuples. The result is a single Graph object if an only integer argument was given, otherwise the result is a list of Graph objects representing the desired k-cores in the order the arguments were specified. If no argument is given, returns all k-cores in increasing order of k.

Calculates the modularity score of the graph with respect to a given clustering.

The modularity of a graph w.r.t. some division measures how good the division is, or how separated are the different vertex types from each other. It's defined as Q = 1 ⁄ (2m)*sum(Aij − gamma*ki*kj ⁄ (2m)delta(ci, cj), i, j). m is the number of edges, Aij is the element of the A adjacency matrix in row i and column j, ki is the degree of node i, kj is the degree of node j, and Ci and cj are the types of the two vertices (i and j), and gamma is a resolution parameter that defaults to 1 for the classical definition of modularity. delta(x, y) is one iff x = y, 0 otherwise.

If edge weights are given, the definition of modularity is modified as follows: Aij becomes the weight of the corresponding edge, ki is the total weight of edges adjacent to vertex i, kj is the total weight of edges adjacent to vertex j and m is the total edge weight in the graph.