Ricky Laishram
Ali Pinar
ABSTRACT
The concept of k-cores is important for understanding the global structure of networks, as well as for identifying central or important nodes within a network. It is often valuable to understand the resilience of the k-cores of a network to attacks and dropped edges (i.e., damaged communications links). We provide a formal definition of a network»s core resilience, and examine the problem of characterizing core resilience in terms of the network»s structural features: in particular, which structural properties cause a network to have high or low core resilience? To measure this, we introduce two novel node properties,Core Strength andCore Influence, which measure the resilience of individual nodes» core numbers and their influence on other nodes» core numbers. Using these properties, we propose theMaximize Resilience of k-Core algorithm to add edges to improve the core resilience of a network. We consider two attack scenarios - randomly deleted edges and randomly deleted nodes. Through experiments on a variety of technological and infrastructure network datasets, we verify the efficacy of our node-based resilience measures at predicting the resilience of a network, and evaluate MRKC at the task of improving a network»s core resilience. We find that on average, for edge deletion attacks, MRKC improves the resilience of a network by 11.1% over the original network, as compared to the best baseline method, which improves the resilience of a network by only 2%. For node deletion attacks, MRKC improves the core resilience of the original network by 19.7% on average, while the best baseline improves it by only 3%.
- Abhijin Adiga and Anil Kumar S. Vullikanti. 2013. How Robust Is the Core of a Network? Springer Berlin Heidelberg, Berlin, Heidelberg, 541--556. Google Scholar
Digital Library
- Md Altaf-Ul-Amine, Kensaku Nishikata, Toshihiro Korna, Teppei Miyasato, Yoko Shinbo, Md Arifuzzaman, Chieko Wada, Maki Maeda, Taku Oshima, Hirotada Mori, et al. 2003. Prediction of protein functions based on k-cores of proteinprotein interaction networks and amino acid sequences. Genome Informatics 14 (2003), 498--499.Google Scholar
- J. Ignacio Alvarez-Hamelin, Alain Barrat, and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. In NIPS. 41--50. Google ScholarDigital Library
- José Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. 2005. K-core decomposition of internet graphs: hierarchies, selfsimilarity and measurement biases. arXiv preprint cs/0511007 (2005).Google Scholar
- J. Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. 2008. K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media 3, 2 (2008), 371--293. http://cnet.fi.uba.ar/ignacio.alvarez-hamelin/pdf/NHM_AH_D_B_V_2008.pdfGoogle ScholarCross Ref
- V. Batagelj and M. Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. Technical Report cs/0310049. Arxiv.Google Scholar
- Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core Decomposition of Uncertain Graphs. In KDD. 1316--1325. Google ScholarDigital Library
- Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. 2007. A model of Internet topology using k-shell decomposition. Proceedings of the National Academy of Sciences 104, 27 (2007), 11150--11154.Google ScholarCross Ref
- James Cheng, Yiping Ke, Shumo Chu, and M. Tamer Ozsu. 2011. Efficient Core Decomposition in Massive Networks. In ICDE. 51--62. Google ScholarDigital Library
- Sergey N Dorogovtsev, Alexander V Goltsev, and Jose Ferreira F Mendes. 2006. K-core organization of complex networks. Physical review letters 96, 4 (2006), 040601.Google Scholar
- P. Erd's and A. Hajnal. 1966. On chromatic number of graphs and set-systems. Acta Mathematica Hungarica 17 (1966), 61--99.Google ScholarCross Ref
- Christos Giatsidis, Dimitrios M. Thilikos, and Michalis Vazirgiannis. 2011. Evaluating Cooperation in Communities with the k-Core Structure. In ASONAM. 87--93. Google ScholarDigital Library
- Christos Giatsidis, Dimitrios M. Thilikos, and Michalis Vazirgiannis. 2013. Dcores: measuring collaboration of directed graphs based on degeneracy. Knowl. Inf. Syst. 35, 2 (2013), 311--343.Google ScholarCross Ref
- WU Jun, Mauricio Barahona, Tan Yue-Jin, and Deng Hong-Zhong. 2010. Natural connectivity of complex networks. Chinese physics letters 27, 7 (2010), 078902.Google Scholar
- Wissam Khaouid, Marina Barsky, S. Venkatesh, and Alex Thomo. 2015. K-Core Decomposition of Large Networks on a Single PC. PVLDB 9, 1 (2015), 13--23. http://www.vldb.org/pvldb/vol9/p13-khaouid.pdf Google ScholarDigital Library
- D. Matula and L. Beck. 1983. Smallest-last ordering and clustering and graph coloring algorithms. JACM 30, 3 (1983), 417--427. Google ScholarDigital Library
- David. W. Matula. 1968. A min-max theorem for graphs with application to graph coloring. SIAM Rev. 10, 4 (1968), 481--482.Google Scholar
- Michael P. O'Brien and Blair D. Sullivan. 2014. Locally Estimating Core Numbers. In ICDM. 460--469. Google ScholarDigital Library
- Chengbin Peng, Tamara G Kolda, and Ali Pinar. 2014. Accelerating community detection by using k-core subgraphs. arXiv preprint arXiv:1403.2226 (2014).Google Scholar
- Ahmet Erdem Sariyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and Ü. V. Çatalyürek. 2013. Streaming Algorithms for K-core Decomposition. Proc. VLDB Endow. 6, 6 (April 2013), 433--444. Google ScholarDigital Library
- Stephen B Seidman. 1983. Network structure and minimum degree. Social networks 5, 3 (1983), 269--287.Google Scholar
- Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. 2016. CoreScope: Graph Mining Using k-Core Analysis Patterns, Anomalies and Algorithms. In Data Mining (ICDM), 2016 IEEE 16th International Conference on. IEEE, 469--478.Google ScholarCross Ref
- D. Wen, L. Qin, Y. Zhang, X. Lin, and J. Yu. 2016. I/O efficient Core Graph Decomposition at web scale. In ICDE. 133--144.Google Scholar
- Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017. Finding Critical Users for Social Network Engagement: The Collapsed k-Core Problem. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4--9, 2017, San Francisco, California, USA. 245--251. http://aaai.org/ocs/index.php/ AAAI/AAAI17/paper/view/14349Google Scholar
Index Terms
- Measuring and Improving the Core Resilience of Networks
Recommendations
Improving the core resilience of real-world hypergraphs
AbstractInteractions that involve a group of people or objects are omnipresent in practice. Some examples include the list of recipients of an email, the group of co-authors of a publication, and the users participating in online discussion threads. These ...
Resilience in computer systems and networks
ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided DesignThe term resilience is used differently by different communities. In general engineering systems, fast recovery from a degraded system state is often termed as resilience. Computer networking community defines it as the combination of trustworthiness (...
Resilience improvement of cyber-physical supply chain networks considering cascading failures with mixed failure modes
Highlights- A CPSCN model with different network topologies and coupling modes is developed.
- A new cascading failure model with four mixed failure modes is proposed.
- A joint improvement model for two-stage recovery is used to enhance ...
AbstractFailure mode analysis and recovery strategy improvement are critical to maintain the resilience of cyber-physical supply chain networks (CPSCNs). However, current literature mostly focuses on single failure mode and single-stage recovery strategy ...
Comments