Network science

Network science is the study of complex networks. It is equal parts mathematics, insofar as networks are graphs; science, as the networks are measured from biological, social, and other natural systems; and statistics, when the networks are modeled statistically.

General references:

A large bibliography is in Cosma Shalizi’s notebook on complex networks , including pages on community detection , social networks , and power laws . Also, Shmuel Weinberger has selected important readings for a course on networks.

Internet Mathematics is a theoretically minded, open-access (arXiv overlay) journal publishing in this area.

Community detection

Community detection is the analogue of clustering for networks.

A family of community detection methods attempts to maximize modularity, an NP-hard problem.

  • Girvan & Newman, 2002: Community structure in social and biological networks (doi, arxiv)
    • Introduces the Girvan-Newman algorithm , a divisize hierarchical method that iteratively removes edges with the highest edge betweenness
  • Clauset, Newman, Moore, 2004: Finding community structure in very large networks (doi, arxiv)
    • Introduces the CNM algorithm for greedy modularity maximization
  • Newman, 2006: Modularity and community structure in networks (doi, arxiv)
    • Main reference for the Newman modularity of undirected networks
    • Directed variant: Leicht & Newman, 2008: Community structure in directed networks (doi, arxiv)
  • Blondel et al, 2008: Fast unfolding of communities in large networks (doi, arxiv, website )
    • Introduces the Louvain method , now very popular
    • A greedy, iterative algorithm for maximizing the Newman modularity, where communities found in one iteration become nodes in the next
    • Directed variant: DuguĂ© & Perez, 2015: Directed Louvain: Maximizing modularity in directed networks (hal )
  • Traag, Waltman, van Eck, 2019: From Louvain to Leiden: Guaranteeing well-connected communities (doi, arxiv, GitHub )
    • Observes and fixes a problem of the Louvain method, that the communities can be internally badly connected, even disconnected
    • Has some guarantees, however “the Leiden algorithm is considerably more complex than the Louvain algorithm”

Statistical analysis

See the stats/ML section for statistical models of network data.