Current Flow Group Closeness Centrality for Complex Networks

Abstract

Current flow closeness centrality (CFCC) has a better discriminating ability than the ordinary closeness centrality based on shortest paths. In this paper, we extend this notion to a group of vertices in a weighted graph, and then study the problem of finding a subset $S$ of $k$ vertices to maximize its CFCC $C(S)$, both theoretically and experimentally. We show that the problem is NP-hard, but propose two greedy algorithms for minimizing the reciprocal of $C(S)$ with provable guarantees using the monotoncity and supermodularity. The first is a deterministic algorithm with an approximation factor $(1-\frac{k}{k-1}\cdot \frac{1}{e})$ and cubic running time; while the second is a randomized algorithm with a $(1-\frac{k}{k-1}\cdot \frac{1}{e}-\epsilon )$-approximation and nearly-linear running time for any $\epsilon >0$. Extensive experiments on model and real networks demonstrate that our algorithms are effective and efficient, with the second algorithm being scalable to massive networks with more than a million vertices.

arXiv comment31 pages, 4 figures

References in corpus (10)

• Emergence of scaling in random networks
• Vital nodes identification in complex networks
• On the limiting behavior of parameter-dependent network centrality measures
• The two-point resistance of a resistor network: A new formulation and application to the cobweb network
• Incremental Deployment of Network Monitors Based on Group Betweenness Centrality
• Current Flow Group Closeness Centrality for Complex Networks
• Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
• The Interplay Between Dynamics and Networks: Centrality, Communities, and Cheeger Inequality
• Scalable Betweenness Centrality Maximization via Sampling
• Measuring and Maximizing Influence via Random Walk in Social Activity Networks

Cited by in corpus (9)

• Current Flow Group Closeness Centrality for Complex Networks
• Maximizing Influence of Leaders in Social Networks
• Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time
• Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges
• Shifting Opinions in a Social Network Through Leader Selection
• Describing the effect of influential spreaders on the different sectors of Indian market: a complex networks perspective
• Maximizing the Smallest Eigenvalue of Grounded Laplacian Matrix
• A Distributed Laplacian Solver and its Applications to Electrical Flow and Random Spanning Tree Computation
• Efficient Algorithms for Relevant Quantities of Friedkin-Johnsen Opinion Dynamics Model