Sabeur Aridhi
Martin Brugnara
Alberto Montresor
ABSTRACT
Distributed processing of large, dynamic graphs has recently received considerable attention, especially in domains such as the analytics of social networks, web graphs and spatial networks. k-core decomposition is one of the significant figures of merit that can be analyzed in graphs. Efficient algorithms to compute k-cores exist already, both in centralized and decentralized setting. Yet, these algorithms have been designed for static graphs, without significant support to deal with the addition or removal of nodes and edges. Typically, this challenge is handled by re-executing the algorithm again on the updated graph. In this work, we propose distributed k-core decomposition and maintenance algorithms for large dynamic graphs. The proposed algorithms exploit, as much as possible, the topology of the graph to compute all the k-cores and maintain them in streaming settings where edge insertions and removals happen frequently. The key idea of the maintenance strategy is that whenever the original graph is updated by the insertion/deletion of one or more edges, only a limited number of nodes need their coreness to be re-evaluated. We present an implementation of the proposed approach on top of the AKKA framework, and experimentally show the efficiency of our approach in the case of large dynamic networks.
- H. Aksu, M. Canim, Y.-C. Chang, I. Korpeoglu, and O. Ulusoy. Distributed k -core view materialization and maintenance for large dynamic graphs. IEEE Trans. Knowl. Data Eng., 26(10):2439--2452, Oct. 2014.Google Scholar
Cross Ref
- J. I. Alvarez-Hamelin, A. Barrat, A. Vespignani, and et al. K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media, 3(2):371, 2008.Google ScholarCross Ref
- J. I. Alvarez-Hamelin, M. G. Beiró, and J. R. Busch. Understanding edge connectivity in the Internet through core decomposition. Internet Mathematics, 7(1):45--66, 2011.Google ScholarCross Ref
- G. Bader and C. Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4(1), 2003.Google Scholar
- V. Batagelj and M. ZaverÅąnik. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 5(2):129--145, 2011. Google ScholarDigital Library
- J. Cheng, Y. Ke, S. Chu, and M. T. Ozsu. Efficient core decomposition in massive networks. In Proc. of the 27th Int. Conf. on Data Engineering, ICDE '11, pages 51--62, Washington, DC, USA, 2011. IEEE Computer Society. Google ScholarDigital Library
- C. Giatsidis, D. Thilikos, and M. Vazirgiannis. Evaluating cooperation in communities with the k-core structure. In Proc. of the Int. Conf. on Advances in Social Networks Analysis and Mining, ASONAM'11, pages 87--93, July 2011. Google ScholarDigital Library
- P. Jakma, M. Orczyk, C. S. Perkins, and M. Fayed. Distributed k-core decomposition of dynamic graphs. In Proc. of the 2012 ACM CoNEXT Student Workshop, pages 39--40, New York, NY, USA, 2012. ACM. Google ScholarDigital Library
- J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.Google Scholar
- R. Li, J. X. Yu, and R. Mao. Efficient core maintenance in large dynamic graphs. IEEE Trans. Knowl. Data Eng., 26(10):2453--2465, 2014.Google ScholarCross Ref
- G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In Proc. of the ACM Int. Conf. on Management of Data, SIGMOD'10, pages 135--146. ACM, 2010. Google ScholarDigital Library
- D. Miorandi and F. De Pellegrini. K-shell decomposition for dynamic complex networks. In Proc. of the 8th Int. Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks), WiOpt'10, pages 488--496, May 2010.Google Scholar
- A. Montresor, F. D. Pellegrini, and D. Miorandi. Distributed k-core decomposition. IEEE Trans. Parallel Distrib. Syst., 24(2):288--300, 2013. Google ScholarDigital Library
- R. Patuelli, A. Reggiani, P. Nijkamp, and F.-J. Bade. The evolution of the commuting network in Germany: Spatial and connectivity patterns. Journal of Transport and Land Use, 2(3), 2010.Google ScholarCross Ref
- A. Sala, L. Cao, C. Wilson, R. Zablit, H. Zheng, and B. Y. Zhao. Measurement-calibrated graph models for social network experiments. In Proc. of the 19th Int. Conf. on World Wide Web, WWW'10, pages 861--870, New York, NY, USA, 2010. ACM. Google ScholarDigital Library
- A. E. Saríyüce, B. Gedik, G. Jacques-Silva, K.-L. Wu, and U. V. Çatalyürek. Streaming algorithms for k-core decomposition. PVLDB, 6(6):433--444, Apr. 2013. Google ScholarDigital Library
- S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269--287, 1983.Google ScholarCross Ref
- T. von Landesberger, A. Kuijper, T. Schreck, J. Kohlhammer, J. van Wijk, J.-D. Fekete, and D. Fellner. Visual analysis of large graphs: State-of-the-art and future research challenges. Computer Graphics Forum, 30(6):1719--1749, 2011.Google ScholarCross Ref
- D. Wyatt. Akka Concurrency. Artima Inc., USA, 2013. Google ScholarDigital Library
- D. Yan, J. Cheng, Y. Lu, and W. Ng. Blogel: A block-centric framework for distributed computation on real-world graphs. PVLDB, 7(14):1981--1992, 2014. Google ScholarDigital Library
Index Terms
- Distributed k-core decomposition and maintenance in large dynamic graphs
Recommendations
Efficient Core Maintenance in Large Bipartite Graphs
PACMMODAs an important cohesive subgraph model in bipartite graphs, the (α, β)-core (a.k.a. bi-core) has found a wide spectrum of real-world applications, such as product recommendation, fraudster detection, and community search. In these applications, the ...
Parallel Order-Based Core Maintenance in Dynamic Graphs
ICPP '23: Proceedings of the 52nd International Conference on Parallel ProcessingThe core numbers of vertices in a graph are one of the most well-studied cohesive subgraph models because of the linear running time. In practice, many data graphs are dynamic graphs that are continuously changing by inserting or removing edges. The ...
Large Induced Forests in Graphs
In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least 8n-2m-2/9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a ...
Comments