research-article

Fast Connectivity Minimization on Large-Scale Networks

Authors:

Hanghang TongAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 15, Issue 3

Article No.: 53, Pages 1 - 25

https://doi.org/10.1145/3442342

Published: 03 May 2021 Publication History

Abstract

The connectivity of networks has been widely studied in many high-impact applications, ranging from immunization, critical infrastructure analysis, social network mining, to bioinformatic system studies. Regardless of the end application domains, connectivity minimization has always been a fundamental task to effectively control the functioning of the underlying system. The combinatorial nature of the connectivity minimization problem imposes an exponential computational complexity to find the optimal solution, which is intractable in large systems. To tackle the computational barrier, greedy algorithm is extensively used to ensure a near-optimal solution by exploiting the diminishing returns property of the problem. Despite the empirical success, the theoretical and algorithmic challenges of the problems still remain wide open. On the theoretical side, the intrinsic hardness and the approximability of the general connectivity minimization problem are still unknown except for a few special cases. On the algorithmic side, existing algorithms are hard to balance between the optimization quality and computational efficiency. In this article, we address the two challenges by (1) proving that the general connectivity minimization problem is NP-hard and

is the best approximation ratio for any polynomial algorithms, and (2) proposing the algorithm CONTAIN and its variant CONTAIN+ that can well balance optimization effectiveness and computational efficiency for eigen-function based connectivity minimization problems in large networks.

References

[1]

Réka Albert, Hawoong Jeong, and Albert-László Barabási. 1999. Internet: Diameter of the world-wide web. Nature 401, 6749 (1999), 130.

[2]

Réka Albert, Hawoong Jeong, and Albert-László Barabási. 2000. Error and attack tolerance of complex networks. Nature 406, 6794 (2000), 378–382.

[3]

Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences 115, 48 (2018), E11221--E11230.

[4]

Béla Bollobás. 2001. The Evolution of Random Graphs–the Giant Component (2 ed.). Cambridge University Press, 130–159.

[5]

Deepayan Chakrabarti, Yang Wang, Chenxi Wang, Jurij Leskovec, and Christos Faloutsos. 2008. Epidemic thresholds in real networks. ACM Transactions on Information and System Security 10, 4 (2008), 1.

Digital Library

[6]

Hau Chan, Leman Akoglu, and Hanghang Tong. 2014. Make it or break it: Manipulating robustness in large networks. In Proceedings of the 2014 SIAM International Conference on Data Mining. SIAM, 325–333.

[7]

Hau Chan, Shuchu Han, and Leman Akoglu. 2015. Where graph topology matters: The robust subgraph problem. In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 10–18.

[8]

Chen Chen, Jingrui He, Nadya Bliss, and Hanghang Tong. 2015. On the connectivity of multi-layered networks: Models, measures and optimal control. In Proceedings of the 2015 IEEE International Conference on Data Mining (ICDM ’15). IEEE, 715–720.

Digital Library

[9]

Chen Chen, Ruiyue Peng, Lei Ying, and Hanghang Tong. 2018. Network connectivity optimization: Fundamental limits and effective algorithms. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 1167–1176.

Digital Library

[10]

Chen Chen and Hanghang Tong. 2017. On the eigen-functions of dynamic graphs: Fast tracking and attribution algorithms. Statistical Analysis and Data Mining: The ASA Data Science Journal 10, 2 (2017), 121–135.

[11]

Chen Chen, Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2016. Eigen-optimization on large graphs by edge manipulation. ACM Transactions on Knowledge Discovery from Data 10, 4 (June 2016), 30 pages.

Digital Library

[12]

Chen Chen, Hanghang Tong, B. Aditya Prakash, Charalampos E. Tsourakakis, Tina Eliassi-Rad, Christos Faloutsos, and Duen Horng Chau. 2016. Node immunization on large graphs: Theory and algorithms. IEEE Transactions on Knowledge and Data Engineering 28, 1 (2016), 113–126.

Digital Library

[13]

Liangzhe Chen, Xinfeng Xu, Sangkeun Lee, Sisi Duan, Alfonso G. Tarditi, Supriya Chinthavali, and B. Aditya Prakash. 2017. Hotspots: Failure cascades on heterogeneous critical infrastructure networks. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. ACM, 1599–1607.

Digital Library

[14]

Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1029–1038.

Digital Library

[15]

Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 199–208.

Digital Library

[16]

Xilun Chen and K. Selcuk Candan. 2014. LWI-SVD: Low-rank, windowed, incremental singular value decompositions on time-evolving data sets. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 987–996.

Digital Library

[17]

Reuven Cohen, Shlomo Havlin, and Daniel Ben-Avraham. 2003. Efficient immunization strategies for computer networks and populations. Physical Review Letters 91, 24 (2003), 247901.

[18]

Allan Peter Davis, Cynthia J. Grondin, Kelley Lennon-Hopkins, Cynthia Saraceni-Richards, Daniela Sciaky, Benjamin L. King, Thomas C. Wiegers, and Carolyn J. Mattingly. 2015. The comparative toxicogenomics database’s 10th year anniversary: Update 2015. Nucleic Acids Research 43, D1 (2015), D914–D920.

[19]

Thang N. Dinh, Ying Xuan, My T. Thai, Panos M. Pardalos, and Taieb Znati. 2011. On new approaches of assessing network vulnerability: Hardness and approximation. IEEE/ACM Transactions on Networking 20, 2 (2011), 609–619.

Digital Library

[20]

Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the internet topology. ACM SIGCOMM Computer Communication Review 29, 4 (1999), 251–262.

Digital Library

[21]

Linton C. Freeman. 1978. Centrality in social networks conceptual clarification. Social Networks 1, 3 (1978), 215–239.

[22]

Mark Jerrum and Alistair Sinclair. 1988. Conductance and the rapid mixing property for Markov chains: The approximation of permanent resolved. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing. ACM, 235–244.

Digital Library

[23]

Ling Jian, Jundong Li, and Huan Liu. 2018. Toward online node classification on streaming networks. Data Mining and Knowledge Discovery 32, 1 (2018), 231–257.

Digital Library

[24]

W.U. Jun, Mauricio Barahona, Tan Yue-Jin, and Deng Hong-Zhong. 2010. Natural connectivity of complex networks. Chinese Physics Letters 27, 7 (2010), 078902.

[25]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 137–146.

Digital Library

[26]

Samir Khuller, Anna Moss, and Joseph Seffi Naor. 1999. The budgeted maximum coverage problem. Information Processing Letters 70, 1 (1999), 39–45.

Digital Library

[27]

Jon Kleinberg and Eva Tardos. 2006. Algorithm Design. Pearson Education India.

Digital Library

[28]

Michael A. Kohanski, Daniel J. Dwyer, and James J. Collins. 2010. How antibiotics kill bacteria: From targets to networks. Nature Reviews Microbiology 8, 6 (2010), 423.

[29]

Istvan A. Kovacs and Albert-Laszlo Barabasi. 2015. Network science: Destruction perfected. Nature 524, 7563 (2015), 38–39.

[30]

Long T. Le, Tina Eliassi-Rad, and Hanghang Tong. 2015. MET: A fast algorithm for minimizing propagation in large graphs with small eigen-gaps. In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 694–702.

[31]

Jure Leskovec, Lada A. Adamic, and Bernardo A. Huberman. 2007. The dynamics of viral marketing. ACM Transactions on the Web 1, 1 (2007), 5.

Digital Library

[32]

Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, 177–187.

Digital Library

[33]

Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data 1, 1 (2007), 2.

Digital Library

[34]

Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 420–429.

Digital Library

[35]

Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, and Huan Liu. 2017. Attributed network embedding for learning in a dynamic environment. In Proceedings of the CIKM 2017. ACM, 387–396.

Digital Library

[36]

Liangyue Li, Hanghang Tong, Yanghua Xiao, and Wei Fan. 2015. Cheetah: Fast graph kernel tracking on dynamic graphs. In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 280–288.

[37]

Rong-Hua Li and Jeffrey Xu Yu. 2015. Triangle minimization in large networks. Knowledge and Information Systems 45, 3 (2015), 617–643.

Digital Library

[38]

Qiao Liu, Chen Chen, Annie Gao, Hang Hang Tong, and Lei Xie. 2017. VariFunNet, an integrated multiscale modeling framework to study the effects of rare non-coding variants in genome-wide association studies: Applied to Alzheimer’s disease. In Proceedings of the 2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM ’17). 2177–2182.

[39]

Julian Mcauley and Jure Leskovec. 2014. Discovering social circles in ego networks. ACM Transactions on Knowledge Discovery from Data 8, 1 (2014), 4.

Digital Library

[40]

Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (2002), 824–827.

[41]

Flaviano Morone and Hernán A. Makse. 2015. Influence maximization in complex networks through optimal percolation. Nature 524, 7563 (2015), 65.

[42]

George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions–I. Mathematical Programming 14, 1 (1978), 265–294.

Digital Library

[43]

Mark E. J. Newman. 2008. The mathematics of networks. The New Palgrave Encyclopedia of Economics 2, 2008 (2008), 1–12.

[44]

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report.

[45]

B. Aditya Prakash, Deepayan Chakrabarti, Nicholas C. Valler, Michalis Faloutsos, and Christos Faloutsos. 2012. Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and Information Systems 33, 3 (2012), 549–575.

Digital Library

[46]

Yilin Shen, Nam P. Nguyen, Ying Xuan, and My T. Thai. 2012. On the discovery of critical links and nodes for assessing network vulnerability. IEEE/ACM Transactions on Networking 21, 3 (2012), 963–973.

Digital Library

[47]

Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing Company.

Digital Library

[48]

Daniel Spielman. 2012. Spectral graph theory. In Combinatorial Scientific Computing. Number 18. Citeseer.

[49]

Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnetminer: Extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 990–998.

Digital Library

[50]

Lei Tang and Huan Liu. 2009. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 817–826.

Digital Library

[51]

Charalampos E. Tsourakakis. 2008. Fast counting of triangles in large real networks without counting: Algorithms and laws. In Proceedings of the 2008 8th IEEE International Conference on Data Mining. IEEE, 608–617.

Digital Library

[52]

Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Vol. 8. Cambridge University Press.

[53]

Hao Yin, Austin R. Benson, and Jure Leskovec. 2019. The local closure coefficient: A new perspective on network clustering. Networks 26, 41 (2019), 44.

[54]

Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. 2017. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 555–564.

Digital Library

Cited By

Zhou XSun HLi WZhang Z(2024)Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge additionTheoretical Computer Science10.1016/j.tcs.2023.114220980:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114220
Ren RShao JBishop AZheng W(2023)Modeling and Detecting Communities in Node Attributed NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.319761235:7(7206-7219)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3197612
Zhu LBao QZhang Z(2023)Measures and Optimization for Robustness and Vulnerability in Disconnected NetworksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.327997918(3350-3362)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3279979
Show More Cited By

Index Terms

Fast Connectivity Minimization on Large-Scale Networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems

Recommendations

Network Connectivity Optimization: Fundamental Limits and Effective Algorithms
KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Network connectivity optimization, which aims to manipulate network connectivity by changing its underlying topology, is a fundamental task behind a wealth of high-impact data mining applications, ranging from immunization, critical infrastructure ...
Connectivity in Complex Networks: Measures, Inference and Optimization
WSDM '18: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining

Networks are ubiquitous in many high impact domains. Among the various aspects of network studies, connectivity is the one that plays important role in many applications (e.g., information dissemination, robustness analysis, community detection, etc.). ...
Fast L1---L2 Minimization via a Proximal Operator

This paper aims to develop new and fast algorithms for recovering a sparse vector from a small number of measurements, which is a fundamental problem in the field of compressive sensing (CS). Currently, CS favors incoherent systems, in which any two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 15, Issue 3

June 2021

533 pages

ISSN:1556-4681

EISSN:1556-472X

DOI:10.1145/3454120

Issue’s Table of Contents

Copyright © 2021 Association for Computing Machinery.

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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 May 2021

Accepted: 01 December 2020

Revised: 01 August 2020

Received: 01 December 2019

Published in TKDD Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Science Foundation
NSF Program on Fairness in AI in collaboration with Amazon

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
178
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou XSun HLi WZhang Z(2024)Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge additionTheoretical Computer Science10.1016/j.tcs.2023.114220980:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114220
Ren RShao JBishop AZheng W(2023)Modeling and Detecting Communities in Node Attributed NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.319761235:7(7206-7219)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3197612
Zhu LBao QZhang Z(2023)Measures and Optimization for Robustness and Vulnerability in Disconnected NetworksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.327997918(3350-3362)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3279979
Adiga APalmer NBaek YMortveit HRavi S(2022)Network Models and Simulation Analytics for Multi-scale Dynamics of Biological InvasionsFrontiers in Big Data10.3389/fdata.2022.7968975Online publication date: 7-Feb-2022
https://doi.org/10.3389/fdata.2022.796897

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents