# A Modular Framework for Centrality and Clustering in Complex Networks

arXiv: https://arxiv.org/abs/2111.11623 · HTML: https://mlsanity.com/paper/2111.11623/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 54 references that are in the map.
- First posted on arXiv 23 Nov 2021.

## Builds on (most cited first, 12 of 12)

- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [Local Graph Clustering with Network Lasso](https://mlsanity.com/paper/2004.12199/) (2020)
- [Immunization of networks with non-overlapping community structure](https://mlsanity.com/paper/1806.05637/) (2018)
- [On community structure in complex networks: challenges and opportunities](https://mlsanity.com/paper/1908.04901/) (2019)
- [Top influencers can be identified universally by combining classical centralities](https://mlsanity.com/paper/2006.07657/) (2020)
- [A change of perspective in network centrality](https://mlsanity.com/paper/1805.08740/) (2018)
- [Centrality Measures for Networks with Community Structure](https://mlsanity.com/paper/1601.07108/) (2016)
- [Identifying Influential Spreaders of Epidemics on Community Networks](https://mlsanity.com/paper/1601.07700/) (2016)
- [Centrality-Friendship Paradoxes: When Our Friends Are More Important Than Us](https://mlsanity.com/paper/1807.01496/) (2018)
- [Characterizing the Interactions Between Classical and Community-aware Centrality Measures in Complex Networks](https://mlsanity.com/paper/2105.07233/) (2021)

## Abstract (arXiv)

The structure of many complex networks includes edge directionality and weights on top of their topology. Network analysis that can seamlessly consider combination of these properties are desirable. In this paper, we study two important such network analysis techniques, namely, centrality and clustering. An information-flow based model is adopted for clustering, which itself builds upon an information theoretic measure for computing centrality. Our principal contributions include a generalized model of Markov entropic centrality with the flexibility to tune the importance of node degrees, edge weights and directions, with a closed-form asymptotic analysis. It leads to a novel two-stage graph clustering algorithm. The centrality analysis helps reason about the suitability of our approach to cluster a given graph, and determine `query' nodes, around which to explore local community structures, leading to an agglomerative clustering mechanism. The entropic centrality computations are amortized by our clustering algorithm, making it computationally efficient: compared to prior approaches using Markov entropic centrality for clustering, our experiments demonstrate multiple orders of magnitude of speed-up. Our clustering algorithm naturally inherits the flexibility to accommodate edge directionality, as well as different interpretations and interplay between edge weights and node degrees. Overall, this paper thus not only makes significant theoretical and conceptual contributions, but also translates the findings into artifacts of practical relevance, yielding new, effective and scalable centrality computations and graph clustering algorithms, whose efficacy has been validated through extensive benchmarking experiments.