research-article

Linear-time enumeration of maximal K-edge-connected subgraphs in large networks by random contraction

Authors:

Yuichi YoshidaAuthors Info & Claims

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

Pages 909 - 918

https://doi.org/10.1145/2505515.2505751

Published: 27 October 2013 Publication History

Abstract

Capturing sets of closely related vertices from large networks is an essential task in many applications such as social network analysis, bioinformatics, and web link research. Decomposing a graph into k-core components is a standard and efficient method for this task, but obtained clusters might not be well-connected. The idea of using maximal k-edge-connected subgraphs was recently proposed to address this issue. Although we can obtain better clusters with this idea, the state-of-the-art method is not efficient enough to process large networks with millions of vertices.

In this paper, we propose a new method to decompose a graph into maximal k-edge-connected components, based on random contraction of edges. Our method is simple to implement but improves performance drastically. We experimentally show that our method can successfully decompose large networks and it is thousands times faster than the previous method. Also, we theoretically explain why our method is efficient in practice. To see the importance of maximal k-edge-connected subgraphs, we also conduct experiments using real-world networks to show that many k-core components have small edge-connectivity and they can be decomposed into a lot of maximal k-edge-connected subgraphs.

References

[1]

M. Altaf-Ul-Amin, Y. Shinbo, K. Mihara, K. Kurokawa, and S. Kanaya. Development and implementation of an algorithm for detection of protein complexes in large interaction networks. BMC Bioinformatics, 7(1):207, 2006.

[2]

J. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. How the k-core decomposition helps in understanding the internet topology. In ISMA Workshop on the Internet Topology, 2006.

[3]

J. I. Alvarez-hamelin, A. Barrat, and A. Vespignani. k-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media, page 371, 2008.

[4]

L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In SIGKDD, pages 44--54, 2006.

Digital Library

[5]

V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks. Arxiv preprint cs.DS/0310049, 2003.

[6]

P. Boldi, M. Rosa, M. Santini, and S. Vigna. Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In WWW, pages 587--596, 2011.

Digital Library

[7]

P. Boldi and S. Vigna. The webgraph framework I: compression techniques. In WWW, pages 595--602, 2004.

Digital Library

[8]

B. Bollobás. Random graphs. Cambridge University Press, 2001.

[9]

B. Bollobás and I. Simon. On the expected behavior of disjoint set union algorithms. In STOC, pages 224--231, 1985.

Digital Library

[10]

D. Callaway, M. Newman, S. Strogatz, and D. Watts. Network robustness and fragility: percolation on random graphs. Phys. Rev. Lett., 85(25):5468--5471, 2000.

[11]

S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, and E. Shir. A model of internet topology using k-shell decomposition. PNAS, 104(27):11150--11154, 2007.

[12]

C. S. Chekuri, A. V. Goldberg, D. R. Karger, M. S. Levine, and C. Stein. Experimental study of minimum cut algorithms. In SODA, pages 324--333, 1997.

Digital Library

[13]

J. Chen and B. Yuan. Detecting functional modules in the yeast protein-protein interaction network. Bioinformatics, 22(18):2283--2290, 2006.

Digital Library

[14]

J. Cheng, Y. Ke, S. Chu, and M. T. Ozsu. Efficient core decomposition in massive networks. In ICDE, pages 51--62, 2011.

Digital Library

[15]

W. Didimo, G. Liotta, F. Montecchiani, and P. Palladino. An advanced network visualization system for financial crime detection. In Paci cVis, pages 203 --210, 2011.

Digital Library

[16]

P. Doreian. On the connectivity of social networks. J. Math. Sociol., 3(2):245--258, 1974.

[17]

Y. Dourisboure, F. Geraci, and M. Pellegrini. Extraction and classification of dense communities in the web. In WWW, pages 461--470, 2007.

Digital Library

[18]

P. Erdös and A. Rényi. On the evolution of random graphs. Akad. Kiadò, 1960.

[19]

D. Karger. Global min-cuts in RNC, and other ramifications of a simple min-out algorithm. In SODA, pages 21--30, 1993.

Digital Library

[20]

M. Kitsak, L. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. Stanley, and H. Makse. Identification of influential spreaders in complex networks. Nature Physics, 6(11):888--893, 2010.

[21]

D. E. Knuth and A. Schönhage. The expected linearity of a simple equivalence algorithm. Theor. Comput. Sci., 6(3):281--315, 1978.

[22]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1), 2007.

Digital Library

[23]

T. Luczak. Size and connectivity of the k-core of a random graph. Discrete Math., 91(1):61--68, July 1991.

Digital Library

[24]

M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In ISWC, volume 2870, pages 351--368. 2003.

Digital Library

[25]

S. Seidman. Network structure and minimum degree. Social networks, 5(3):269--287, 1983.

[26]

S. Seidman and B. Foster. A graph-theoretic generalization of the clique concept. J. Math. Sociol., 6(1):139--154, 1978.

[27]

M. Stoer and F. Wagner. A simple min-cut algorithm. J. ACM, 44(4):585--591, 1997.

Digital Library

[28]

J. Wang and J. Cheng. Truss decomposition in massive networks. PVLDB, 5(9):812--823, 2012.

Digital Library

[29]

N. Wang, J. Zhang, K.-L. Tan, and A. K. H. Tung. On triangulation-based dense neighborhood graph discovery. PVLDB, 4(2):58--68, 2010.

Digital Library

[30]

D. White and F. Harary. The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociol. Methodol., 31(1):305--359, 2001.

[31]

A. C.-c. Yao. On the average behavior of set merging algorithms. In STOC, pages 192--195, 1976.

Digital Library

[32]

R. Zhou, C. Liu, J. X. Yu, W. Liang, B. Chen, and J. Li. Finding maximal k-edge-connected subgraphs from a large graph. In EDBT, pages 480--491, 2012.

Digital Library

Cited By

Wang JWang KLin XZhang WZhang Y(2024)Efficient Unsupervised Community Search with Pre-Trained Graph TransformerProceedings of the VLDB Endowment10.14778/3665844.366585317:9(2227-2240)Online publication date: 6-Aug-2024
https://dl.acm.org/doi/10.14778/3665844.3665853
Sadri HSrinivasan VThomo A(2024)Efficient Computation of K-Edge Connected Components: An Empirical AnalysisModelling and Mining Networks10.1007/978-3-031-59205-8_6(80-96)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-59205-8_6
Zhang QLi RQin HWang GZhang ZYuan Y(2023)Stable Subgraph Isomorphism Search in Temporal NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.317580035:6(6405-6420)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3175800
Show More Cited By

Index Terms

Linear-time enumeration of maximal K-edge-connected subgraphs in large networks by random contraction
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Finding maximal k-edge-connected subgraphs from a large graph
EDBT '12: Proceedings of the 15th International Conference on Extending Database Technology

In this paper, we study how to find maximal k-edge-connected subgraphs from a large graph. k-edge-connected subgraphs can be used to capture closely related vertices, and finding such vertex clusters is interesting in many applications, e. g., social ...
Vulnerability of super edge-connected networks

When the underlying topology of an interconnection network is modeled by a connected graph G, the connectivity of G is an important measurement for reliability and fault tolerance of the network. For a given integer h>=0, a subset F of edges in a ...
Finding densest k-connected subgraphs
Abstract
Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

October 2013

2612 pages

ISBN:9781450322638

DOI:10.1145/2505515

General Chairs:
Qi He
LinkedIn, USA
,
Arun Iyengar
IBM T.J. Watson Research Center, USA
,
Program Chairs:
Wolfgang Nejdl
L3S Research Center, Germany
,
Jian Pei
Simon Fraser University, Canada
,
Rajeev Rastogi
Amazon, India

Copyright © 2013 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM'13

Sponsor:

CIKM'13: 22nd ACM International Conference on Information and Knowledge Management

October 27 - November 1, 2013

California, San Francisco, USA

Acceptance Rates

CIKM '13 Paper Acceptance Rate 143 of 848 submissions, 17%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
448
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)4

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang JWang KLin XZhang WZhang Y(2024)Efficient Unsupervised Community Search with Pre-Trained Graph TransformerProceedings of the VLDB Endowment10.14778/3665844.366585317:9(2227-2240)Online publication date: 6-Aug-2024
https://dl.acm.org/doi/10.14778/3665844.3665853
Sadri HSrinivasan VThomo A(2024)Efficient Computation of K-Edge Connected Components: An Empirical AnalysisModelling and Mining Networks10.1007/978-3-031-59205-8_6(80-96)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-59205-8_6
Zhang QLi RQin HWang GZhang ZYuan Y(2023)Stable Subgraph Isomorphism Search in Temporal NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.317580035:6(6405-6420)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3175800
Trung TChang LLong NYao KThanh Binh H(2023)Verification-Free Approaches to Efficient Locally Densest Subgraph Discovery2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00008(1-13)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00008
Chang LWang Z(2023)A near-optimal approach to edge connectivity-based hierarchical graph decompositionThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00797-x33:1(49-71)Online publication date: 6-May-2023
https://dl.acm.org/doi/10.1007/s00778-023-00797-x
ITO TSANO YYAMANAKA KHIRAYAMA T(2022)A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced SubgraphsIEICE Transactions on Information and Systems10.1587/transinf.2021FCP0005E105.D:3(466-473)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transinf.2021FCP0005
Chang LWang Z(2022)A near-optimal approach to edge connectivity-based hierarchical graph decompositionProceedings of the VLDB Endowment10.14778/3514061.351406315:6(1146-1158)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.14778/3514061.3514063
Lu CYu JWei HZhang Y(2022)Enumerating Maximum Cliques in Massive GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.303601334:9(4215-4230)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TKDE.2020.3036013
Peng YBian SLi RWang SYu J(2022)Finding Top-r Influential Communities under Aggregation Functions2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00191(1941-1954)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00191
Banerjee SPal B(2022) An efficient updation approach for enumerating maximal (Δ, γ )-cliques of a temporal network Journal of Complex Networks10.1093/comnet/cnac02710:5Online publication date: 23-Sep-2022
https://doi.org/10.1093/comnet/cnac027
Show More Cited By

View Options

Get Access

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