More Web Proxy on the site http://driver.im/

research-article

Measuring and maximizing group closeness centrality over disk-resident graphs

Authors:

Xiaohong GuanAuthors Info & Claims

WWW '14 Companion: Proceedings of the 23rd International Conference on World Wide Web

Pages 689 - 694

https://doi.org/10.1145/2567948.2579356

Published: 07 April 2014 Publication History

Abstract

As an important metric in graphs, group closeness centrality measures how close a group of vertices is to all other vertices in a graph, and it is used in numerous graph applications such as measuring the dominance and influence of a node group over the graph. However, when a large-scale graph contains hundreds of millions of nodes/edges which cannot reside entirely in computer's main memory, measuring and maximizing group closeness become challenging tasks. In this paper, we present a systematic solution for efficiently calculating and maximizing the group closeness for disk-resident graphs. Our solution first leverages a probabilistic counting method to efficiently estimate the group closeness with high accuracy, rather than exhaustively computing it in an exact fashion. In addition, we design an I/O-efficient greedy algorithm to find a node group that maximizes group closeness. Our proposed algorithm significantly reduces the number of random accesses to disk, thereby dramatically improving computational efficiency. Experiments on real-world big graphs demonstrate the efficacy of our approach.

References

[1]

_______________. Technique report. http://nskeylab.xjtu.edu.cn/dataset/jzzhao/NodeGroup_TR.pdf, 2013.

[2]

B. Berger, J. Rompel, and P. W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. JCSS, 49(3), 1994.

Digital Library

[3]

F. Chierichetti, R. Kumar, and A. Tomkins. Max-Cover in Map-Reduce. In WWW, 2010.

Digital Library

[4]

G. Cormode, H. Karloff, and A. Wirth. Set cover algorithms for very large datasets. In CIKM, 2010.

Digital Library

[5]

J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, 2004.

Digital Library

[6]

D. Eppstein and J. Wang. Fast approximation of centrality. Journal of Graph Algorithms and Applications, 2004.

[7]

M. G. Everett and S. P. Borgatti. The centrality of groups and classes. Journal of Mathematical Sociology, 23(3):181--201, 1999.

[8]

P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications. JCSS, 31(2), 1985.

Digital Library

[9]

M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. JACM, 34:596--615, 1987.

Digital Library

[10]

L. C. Freeman. Centrality in social networks: Conceptual clarification. Social Networks, 1:215--239, 1978.

[11]

D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1):1--13, 1977.

Digital Library

[12]

U. Kang, S. Papadimitriou, J. Sun, and H. Tong. Centralities in large networks: Algorithms and observations. In SDM, 2011.

[13]

H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In WWW, 2010.

Digital Library

[14]

A. Kyrola, G. Blelloch, and C. Guestrin. GraphChi: Large-scale graph computation on just a PC. In OSDI, 2012.

Digital Library

[15]

A. S. Maiya and T. Y. Berger-Wolf. Online sampling of high centrality individuals in social networks. In PAKDD, 2010.

Digital Library

[16]

G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of approximations for maximizing submodular set functions. Math. Prog., 14, 1978.

[17]

K. Okamoto, W. Chen, and X.-Y. Li. Ranking of closeness centrality for large-scale social networks. Frontiers in Algorithmics, 5059, 2008.

Digital Library

[18]

H. Oktay, A. S. Balkir, I. Foster, and D. D. Jensen. Distance estimation for very large networks using mapreduce and network structure indices. In Workshop on Information Networks, 2011.

[19]

C. R. Palmer, P. B. Gibbons, and C. Faloutsos. ANF: A fast and scalable tool for data mining in massive graphs. In KDD, 2002.

Digital Library

[20]

A. E. Sariyuce, E. Saule, K. kaya, and U. V. Catalyurek. Streamer : A distributed framework for incremental closeness centrality computation. In IEEE Cluster 13 Conference, 2013.

[21]

Y. sup Lim, B. Ribeiro, D. S. Menasche, P. Basu, and D. Towsley. Online estimating the top k nodes of a network. In IEEE NSW, 2011.

Cited By

Zhao CParilina E(2024)Network Structure Properties and Opinion Dynamics in Two-Layer Networks with HypocrisyMathematical Optimization Theory and Operations Research10.1007/978-3-031-62792-7_21(300-314)Online publication date: 18-Jun-2024
https://doi.org/10.1007/978-3-031-62792-7_21
Xie YBrynildsen JWindisch KBlendy J(2023) Neural network connectivity following opioid dependence is altered by a common genetic variant in the mu-opioid receptor, OPRM1 A118G The Journal of Neuroscience10.1523/JNEUROSCI.1492-23.2023(JN-RM-1492-23)Online publication date: 8-Dec-2023
https://doi.org/10.1523/JNEUROSCI.1492-23.2023
Li XAbdelfattah AYero Jd'Aragona DCerny TTaibi D(2023)Analyzing Organizational Structure of Microservice Projects based on Contributor Collaboration2023 IEEE International Conference on Service-Oriented System Engineering (SOSE)10.1109/SOSE58276.2023.00007(1-8)Online publication date: Jul-2023
https://doi.org/10.1109/SOSE58276.2023.00007
Show More Cited By

Index Terms

Measuring and maximizing group closeness centrality over disk-resident graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

I/O-efficient calculation of H-group closeness centrality over disk-resident graphs

We introduce H-group closeness centrality in this work. H-group closeness centrality of a group of nodes measures how close this node group is to other nodes in a graph, and can be used in numerous applications such as measuring the importance and ...
Minimum order of graphs with given coloring parameters

A complete k -coloring of a graph G = ( V , E ) is an assignment : V { 1 , , k } of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively ...
On Group Connectivity of Graphs

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z ₃-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '14 Companion: Proceedings of the 23rd International Conference on World Wide Web

April 2014

1396 pages

ISBN:9781450327459

DOI:10.1145/2567948

General Chair:
Chin-Wan Chung
Korea Advanced Institute of Science and Technology, Korea
,
Program Chairs:
Andrei Broder
Google Inc., USA
,
Kyuseok Shim
Seoul National University, Korea
,
Torsten Suel
New York University, USA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 April 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

WWW '14

Sponsor:

IW3C2

WWW '14: 23rd International World Wide Web Conference

April 7 - 11, 2014

Seoul, Korea

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
334
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)3

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao CParilina E(2024)Network Structure Properties and Opinion Dynamics in Two-Layer Networks with HypocrisyMathematical Optimization Theory and Operations Research10.1007/978-3-031-62792-7_21(300-314)Online publication date: 18-Jun-2024
https://doi.org/10.1007/978-3-031-62792-7_21
Xie YBrynildsen JWindisch KBlendy J(2023) Neural network connectivity following opioid dependence is altered by a common genetic variant in the mu-opioid receptor, OPRM1 A118G The Journal of Neuroscience10.1523/JNEUROSCI.1492-23.2023(JN-RM-1492-23)Online publication date: 8-Dec-2023
https://doi.org/10.1523/JNEUROSCI.1492-23.2023
Li XAbdelfattah AYero Jd'Aragona DCerny TTaibi D(2023)Analyzing Organizational Structure of Microservice Projects based on Contributor Collaboration2023 IEEE International Conference on Service-Oriented System Engineering (SOSE)10.1109/SOSE58276.2023.00007(1-8)Online publication date: Jul-2023
https://doi.org/10.1109/SOSE58276.2023.00007
Zhang QLi RQin HDai YYuan YWang G(2023)Neighborhood Skyline on Graphs: Concepts, Algorithms and Applications2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00051(585-598)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00051
Rajbhandari BOlsen PBirnbaum JHwang J(2022)PRESTO: Fast and Effective Group Closeness MaximizationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3178925(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3178925
Wang RLi YLin SXie HXu YLui J(2021)On Modeling Influence Maximization in Social Activity Networks under General SettingsACM Transactions on Knowledge Discovery from Data10.1145/345121815:6(1-28)Online publication date: 19-May-2021
https://dl.acm.org/doi/10.1145/3451218
Singh R(2021)Centrality Measures: A Tool to Identify Key Actors in Social NetworksPrinciples of Social Networking10.1007/978-981-16-3398-0_1(1-27)Online publication date: 19-Aug-2021
https://doi.org/10.1007/978-981-16-3398-0_1
Li XZhang BTurunen M(2020)A preliminary network analysis on steam game tagsProceedings of the 23rd International Conference on Academic Mindtrek10.1145/3377290.3377300(65-73)Online publication date: 29-Jan-2020
https://dl.acm.org/doi/10.1145/3377290.3377300
Li HPeng RShan LYi YZhang Z(2019)Current Flow Group Closeness Centrality for Complex Networks?The World Wide Web Conference10.1145/3308558.3313490(961-971)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313490
Zhao PLi YXie HWu ZXu YLui J(2017)Measuring and Maximizing Influence via Random Walk in Social Activity NetworksDatabase Systems for Advanced Applications10.1007/978-3-319-55699-4_20(323-338)Online publication date: 22-Mar-2017
https://doi.org/10.1007/978-3-319-55699-4_20
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents