Parallel algorithms for evaluating centrality indices in real-world networks

被引:79
作者
Bader, David A. [1 ]
Madduri, Kamesh [1 ]
机构
[1] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA
来源
2006 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS | 2006年
关键词
D O I
10.1109/ICPP.2006.57
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
This paper discusses fast parallel algorithms for evaluating several centrality indices frequently used in complex network analysis. These algorithms have been optimized to exploit properties typically observed in real-world large scale networks, such as the low average distance, high local density, and heavy-tailed power law degree distributions. We test our implementations on real datasets such as the web graph, protein-interaction networks, movie-actor and citation networks, and report impressive parallel performance for evaluation of the computationally intensive centrality metrics (betweenness and closeness centrality) on high-end shared memory symmetric multiprocessor and multithreaded architectures. To our knowledge, these are the first parallel implementations of these widely-used social network analysis metrics. We demonstrate that it is possible to rigorously analyze networks three orders of magnitude larger than instances that can be handled by existing network analysis (SNA) software packages. For instance, we compute the exact betweenness centrality value for each vertex in a large US patent citation network (3 million patents, 16 million citations) in 42 minutes on 16 processors, utilizing 20GB RAM of the IBM p5 570. Current SNA packages on the other hand cannot handle graphs with more than hundred thousand edges.
引用
收藏
页码:539 / 547
页数:9
相关论文
共 50 条
  • [1] A Computational Study of External-Memory BFS Algorithms
    Ajwani, Deepak
    Dementiev, Roman
    Meyer, Ulrich
    [J]. PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 601 - +
  • [2] [Anonymous], P INT PAR DISTR PROC
  • [3] [Anonymous], UCINET 6 SOC NETW AN
  • [4] [Anonymous], P 34 INT C PAR PROC
  • [5] [Anonymous], INFLOW 3 1 SOCIAL NE
  • [6] [Anonymous], 1973, Soc. Sci. Res, DOI [DOI 10.1016/0049-089X(73)90010-0, 10.1016/0049-089X(73)90010-0]
  • [7] [Anonymous], 1994, SOCIAL NETWORK ANAL
  • [8] [Anonymous], P 4 SIAM INT C DAT M
  • [9] [Anonymous], PHYS REV E
  • [10] BADER D, 2006, MTA2 GEORG I TECHN