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

Home ▸ Tools ▸ NetworkX

Contents

1. Use

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

2. Functions related to communities

2.1 kernighan_lin_bisection

2.1.1 Description

Partition a graph into two blocks using the Kernighan–Lin algorithm.

This algorithm paritions a network into two sets by iteratively swapping pairs of nodes to reduce the edge cut between the two sets.

2.1.2 Reference

  • Kernighan, B. W.; Lin, Shen (1970). “An efficient heuristic procedure for partitioning graphs.” Bell Systems Technical Journal 49: 291–307. Oxford University Press 2011.

Back to Top

2.2 k_clique_communities

2.2.1 Description

Find k-clique communities in graph using the percolation method.

A k-clique community is the union of all cliques of size k that can be reached through adjacent (sharing k-1 nodes) k-cliques.

2.2.2 Reference

  • Gergely Palla, Imre Derényi, Illés Farkas1, and Tamás Vicsek, Uncovering the overlapping community structure of complex networks in nature and society Nature 435, 814-818, 2005, doi:10.1038/nature03607

Back to Top

2.3 asyn_lpa_communities

2.3.1 Description

Returns communities in G as detected by asynchronous label propagation.

The asynchronous label propagation algorithm is described in the reference. The algorithm is probabilistic and the found communities may vary on different executions.

The algorithm proceeds as follows. After initializing each node with a unique label, the algorithm repeatedly sets the label of a node to be the label that appears most frequently among that nodes neighbors. The algorithm halts when each node has the label that appears most frequently among its neighbors. The algorithm is asynchronous because each node is updated without waiting for updates on the remaining nodes.

This generalized version of the algorithm in [1] accepts edge weights.

2.3.2 Reference

  • Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. “Near linear time algorithm to detect community structures in large-scale networks.” Physical Review E 76.3 (2007): 036106.

Back to Top

2.4 coverage

2.4.1 Description

Returns the coverage of a partition.

The coverage of a partition is the ratio of the number of intra-community edges to the total number of edges in the graph.

2.4.2 Reference

Back to Top

2.5 performance

2.5.1 Description

Returns the performance of a partition.

The performance of a partition is the ratio of the number of intra-community edges plus inter-community non-edges with the total number of potential edges.

2.5.2 Reference

Back to Top

2.6 girvan_newman

2.6.1 Description

Finds communities in a graph using the Girvan–Newman method.

Back to Top