Name
Abstract | ||
|---|---|---|
The structural diversity of an edge, which is measured by the number of connected components of the edge’s ego-network, has recently been recognized as a key metric for analyzing social influence and information diffusion in social networks. Given this, an important problem in social network analysis is to identify top-k edges that have the highest structural diversities. In this work, we for the first time perform a systematical study for the top-k edge structural diversity search problem on large graphs. Specifically, we first develop a new online search framework with two basic upper-bounding rules to efficiently solve this problem. Then, we propose a new index structure using near-linear space to process the top-k edge structural diversity search in near-optimal time. To create such an index structure, we devise an efficient algorithm based on an interesting connection between our problem and the 4-clique enumeration problem. In addition, we also propose efficient index maintenance techniques to handle dynamic graphs. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/ICDE48307.2020.00025 | 2020 IEEE 36th International Conference on Data Engineering (ICDE) |
Keywords | DocType | ISSN |
index structure,4-clique enumeration problem,structural diversity,ego-network,social influence,information diffusion,social network analysis,structural diversities,online search framework,upper-bounding rules,index maintenance techniques,top-k edge structural diversity search problem,dynamic graphs | Conference | 1063-6382 |
ISBN | Citations | PageRank |
978-1-7281-2904-4 | 1 | 0.35 |
References | Authors | |
25 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qi Zhang | 1 | 931 | 179.66 |
| Rong-Hua Li | 2 | 381 | 33.77 |
| Qixuan Yang | 3 | 1 | 0.35 |
| Guoren Wang | 4 | 1366 | 159.46 |
| Lu Qin | 5 | 1430 | 95.44 |