Current Flow Group Closeness Centrality for Complex Networks?
Current Flow Group Closeness Centrality for Complex Networks?
复制标题
DOI：
10.1145/3308558.3313490
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Huan Li;Richard Peng;Liren Shan;Yuhao Yi;Zhongzhi Zhang
中科院分区：
文献类型：
--
作者：
Huan Li;Richard Peng;Liren Shan;Yuhao Yi;Zhongzhi Zhang
在许多实际场景中，在某些约束下选择一组顶点以最大化其联合中心性的问题出现。本文将当前流接近中心度（CFCC）的概念推广到图中的一组顶点，并研究了在基数约束下，选择一个子集S使其CFCC C（S）最大化的问题|S| = k。我们证明了问题的NP-困难性，但提出了两个贪婪算法来最小化C（S）的倒数。我们证明了逼近比的单调性和超模性。一个建议的确定性贪婪算法有一个近似因子和立方运行时间。为了比较，建议的随机算法给出近似在近线性时间，任何？> 0。在模型和真实的网络上的大量实验证明了所提算法的有效性和效率，其中随机化算法被应用于超过百万个顶点的大规模网络。
The problem of selecting a group of vertices under certain constraints that maximize their joint centrality arises in many practical scenarios. In this paper, we extend the notion of current flow closeness centrality (CFCC) to a set of vertices in a graph, and investigate the problem of selecting a subset S to maximizes its CFCC C(S), with the cardinality constraint |S| = k. We show the NP-hardness of the problem, but propose two greedy algorithms to minimize the reciprocal of C(S). We prove the approximation ratios by showing the monotonicity and supermodularity. A proposed deterministic greedy algorithm has an approximation factor and cubic running time. To compare with, a proposed randomized algorithm gives -approximation in nearly-linear time, for any ? > 0. Extensive experiments on model and real networks demonstrate the effectiveness and efficiency of the proposed algorithms, with the randomized algorithm being applied to massive networks with more than a million vertices.