Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3308558.3313490 | WWW '19: The Web Conference on The World Wide Web Conference WWW 2019 |
Keywords | Field | DocType |
Centrality, Combinatorial Optimization, Social Networks, Spectral Graph Theory | Discrete mathematics,Data mining,Randomized algorithm,Spectral graph theory,Vertex (geometry),Computer science,Cardinality,Centrality,Greedy algorithm,Combinatorial optimization,Complex network | Journal |
Volume | ISSN | Citations |
abs/1802.02556 | WWW'2019 | 0 |
PageRank | References | Authors |
0.34 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Huan Li | 1 | 18 | 4.60 |
| Richard Peng | 2 | 522 | 42.64 |
| Liren Shan | 3 | 12 | 3.17 |
| Yuhao Yi | 4 | 22 | 6.91 |
| Zhongzhi Zhang | 5 | 85 | 22.02 |