A Modular Framework for Centrality and Clustering in Complex Networks
  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.
