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:
- Newman, 2018: Networks, 2nd ed.
- Barabási, 2015: Network Science (online )
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.