Distributed Truss Computation in Dynamic Graphs

Ziwei Mo; Qi Luo; Dongxiao Yu; Hao Sheng; Jiguo Yu; Xiuzhen Cheng

doi:10.26599/TST.2022.9010019

Tsinghua Science and Technology 2023, 28(5): 873-887 https://doi.org/10.26599/TST.2022.9010019

Open Access | Issue | Published: 19 May 2023

Distributed Truss Computation in Dynamic Graphs

Show Author's Information Hide Author's Information Ziwei Mo^¹, Qi Luo^¹(

), Dongxiao Yu^¹, Hao Sheng^², Jiguo Yu^³, Xiuzhen Cheng^¹

1School of Computer Science and Technology, Shandong University, Qingdao 266200, China

2State Key Laboratory of Software Development Environment, School of Computer Science and Engineering and the Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University, Beijing 100191, China

3Big Data Institute, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China

Keywords:

distributed algorithm, graph mining, cohesive subgraph, dynamic graph, k-truss

Cite this article:

Mo Z, Luo Q, Yu D, et al. Distributed Truss Computation in Dynamic Graphs. Tsinghua Science and Technology, 2023, 28(5): 873-887. https://doi.org/10.26599/TST.2022.9010019

Download citation

EndNote(RIS)

BibTeX

394

Views

Downloads

Citations

Crossref

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

Large-scale graphs usually exhibit global sparsity with local cohesiveness, and mining the representative cohesive subgraphs is a fundamental problem in graph analysis. The $k$ -truss is one of the most commonly studied cohesive subgraphs, in which each edge is formed in at least $k - 2$ triangles. A critical issue in mining a $k$ -truss lies in the computation of the trussness of each edge, which is the maximum value of $k$ that an edge can be in a $k$ -truss. Existing works mostly focus on truss computation in static graphs by sequential models. However, the graphs are constantly changing dynamically in the real world. We study distributed truss computation in dynamic graphs in this paper. In particular, we compute the trussness of edges based on the local nature of the $k$ -truss in a synchronized node-centric distributed model. Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm. Moreover, the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation. Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.

Full text

Abstract

Full text

Outline

About this article

Distributed Truss Computation in Dynamic Graphs

Show Author's information Hide Author's Information Ziwei Mo^¹, Qi Luo^¹(

), Dongxiao Yu^¹, Hao Sheng^², Jiguo Yu^³, Xiuzhen Cheng^¹

1School of Computer Science and Technology, Shandong University, Qingdao 266200, China

3Big Data Institute, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China

Abstract

Keywords: distributed algorithm, graph mining, cohesive subgraph, dynamic graph, k-truss

References(42)

[1]

Q. Luo, D. Yu, Z. Cai, X. Lin, and X. Cheng, Hypercore maintenance in dynamic hypergraphs, in Proc. 37^th IEEE Int. Conf. on Data Engineering, Chania, Greece, 2021, pp. 2051–2056.

DOI Google Scholar

[2]

Q. Luo, D. Yu, F. Li, Z. Dou, Z. Cai, J. Yu, and X. Cheng, Distributed core decomposition in probabilistic graphs, in Proc. 8^th Int. Conf. on Computational Data and Social Networks, Ho Chi Minh City, Vietnam, 2019, pp. 16–32.

DOI Google Scholar

[3]

D. Yu, N. Wang, Q. Luo, F. Li, J. Yu, X. Cheng, and Z. Cai, Fast core maintenance in dynamic graphs, IEEE Trans. Comput. Soc. Syst., vol. 9, no. 3, pp. 710–723, 2022.

DOI Google Scholar

[4]

J. Abello, M. G. C. Resende, and S. Sudarsky, Massive quasi-clique detection, in Proc. 5^th Latin American Symp. on LATIN 2002: Theoretical Informatics, Cancun, Mexico, 2002, pp. 598–612.

DOI Google Scholar

[5]

S. B. Seidman, Network structure and minimum degree, Soc. Netw., vol. 5, no. 3, pp. 269–287, 1983.

DOI Google Scholar

[6]

S. B. Seidman and B. L. Foster, A graph-theoretic generalization of the clique concept, J. Math. Sociol., vol. 6, no. 1, pp. 139–154, 1978.

DOI Google Scholar

[7]

R. J. Mokken, Cliques, clubs and clans, Qual. Quant., vol. 13, no. 2, pp. 161–173, 1979.

DOI Google Scholar

[8]

J. Cohen, Trusses: Cohesive Subgraphs for Social Network Analysis., Tech. Rep., National Security Agency, Middleburg, VA, USA, 2008.

[9]

X. Huang, L. V. S. Lakshmanan, J. X. Yu, and H. Cheng, Approximate closest community search in networks, Proc. VLDB Endow., vol. 9, no. 4, pp. 276–287, 2015.

DOI Google Scholar

[10]

M. Sozio and A. Gionis, The community-search problem and how to plan a successful cocktail party, in Proc. 16^th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Washington, DC, USA, 2010, pp. 939–948.

DOI Google Scholar

[11]

J. Zhang, P. S. Yu, and Y. Lv, Enterprise employee training via project team formation, in Proc. 10^th ACM Int. Conf. on Web Search and Data Mining, Cambridge, UK, 2017, pp. 3–12.

DOI Google Scholar

[12]

T. Chakraborty, S. Patranabis, P. Goyal, and A. Mukherjee, On the formation of circles in co-authorship networks, in Proc. 21^th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 109–118.

DOI Google Scholar

[13]

J. Ugander, L. Backstrom, C. Marlow, and J. M. Kleinberg, Structural diversity in social contagion, Proc. Natl. Acad. Sci. USA, vol. 109, no. 16, pp. 5962–5966, 2012.

DOI Google Scholar

[14]

J. Wang and J. Cheng, Truss decomposition in massive networks, Proc. VLDB Endow., vol. 5, no. 9, pp. 812–823, 2012.

DOI Google Scholar

[15]

X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu, Querying k-truss community in large and dynamic graphs, in Proc. 2014 ACM SIGMOD Int. Conf. on Management of Data, Snowbird, UT, USA, 2014, pp. 1311–1322.

DOI Google Scholar

[16]

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. 2010 ACM SIGMOD Int. Conf. on Management of Data, Indianapolis, IN, USA, 2010, pp. 135–146.

DOI Google Scholar

[17]

Y. C. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein, Distributed graphlab: A framework for machine learning and data mining in the cloud, Proc. VLDB Endow., vol. 5, no. 8, pp. 716–727, 2012.

DOI Google Scholar

[18]

J. Sun, D. Zhou, H. Chen, C. Chang, Z. Chen, W. Li, and L. He, GPSA: A graph processing system with actors. in Proc. 44^th Int. Conf. on Parallel Processing, Beijing, China, 2015, pp. 709–718.

DOI Google Scholar

[19]

S. Chu and J. Cheng, Triangle listing in massive networks and its applications, in Proc. 17^th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, San Diego, CA, USA, 2011, pp. 672–680.

DOI Google Scholar

[20]

A. E. Sariyüce and A. Pinar, Fast hierarchy construction for dense subgraphs, roceedings VLDB Endowment, vol. 10, no. 3, pp. 97–108, 2016.

DOI Google Scholar

[21]

A. E. Sariyüce, C. Seshadhri, and A. Pinar, Local algorithms for hierarchical dense subgraph discovery, Proc. VLDB Endow., vol. 12, no. 1, pp. 43–56, 2018.

DOI Google Scholar

[22]

Y. Zhang and S. Parthasarathy, Extracting analyzing and visualizing triangle K-core motifs within networks, in Proc. 2012 IEEE 28^th Int. Conf. on Data Engineering, Arlington, VA, USA, 2012, pp. 1049–1060.

DOI Google Scholar

[23]

J. Cohen, Graph twiddling in a mapreduce world, Comput. Sci. Eng., vol. 11, no. 4, pp. 29–41, 2009.

DOI Google Scholar

[24]

Y. Che, Z. Lai, S. Sun, Y. Wang, and Q. Luo, Accelerating truss decomposition on heterogeneous processors, Proc. VLDB Endow., vol. 13, no. 10, pp. 1751–1764, 2020.

DOI Google Scholar

[25]

P. L. Chen, C. K. Chou, and M. S. Chen, Distributed algorithms for k-truss decomposition, in Proc. 2014 IEEE Int. Conf. on Big Data, Washington, DC, USA, 2014, pp. 471–480.

DOI Google Scholar

[26]

H. Kabir and K. Madduri, Parallel k-truss decomposition on multicore systems. in Proc. 2017 IEEE High Performance Extreme Computing Conf., Waltham, MA, USA, 2017, pp. 1–7.

DOI Google Scholar

[27]

H. Kabir and K. Madduri, Shared-memory graph truss decomposition, in Proc. 2017 IEEE 24^th Int. Conf. on High Performance Computing, Jaipur, India, 2017, pp. 13–22.

DOI Google Scholar

[28]

Y. Shao, L. Chen, and B. Cui, Efficient cohesive subgraphs detection in parallel, in Proc. 2014 ACM SIGMOD Int. Conf. on Management of Data, Snowbird, UT, USA, 2014, pp. 613–624.

DOI Google Scholar

[29]

S. Smith, X. Liu, N. K. Ahmed, A. S. Tom, F. Petrini, and G. Karypis, Truss decomposition on shared-memory parallel systems, in Proc. 2017 IEEE High Performance Extreme Computing Conf., Waltham, MA, USA, 2017, pp. 1–6.

DOI Google Scholar

[30]

F. Esfahani, J. Wu, V. Srinivasan, A. Thomo, and K. Wu, Fast truss decomposition in large-scale probabilistic graphs, In Proc. 22^nd Int. Conf. on Extending Database Technology, Lisbon, Portugal, 2019, pp. 722–725.

Google Scholar

[31]

Z. Zou, Bitruss decomposition of bipartite graphs, in Proc. 21^st Int. Conf. on Database Systems for Advanced Applications, Dallas, TX, USA, 2016, pp. 218–233.

DOI Google Scholar

[32]

X. Huang, W. Lu, and L. V. S. Lakshmanan, Truss decomposition of probabilistic graphs: Semantics and algorithms, in Proc. 2016 Int. Conf. on Management of Data, San Francisco, CA, USA, 2016, pp. 77–90.

DOI Google Scholar

[33]

H. Sun, Y. Zhang, X. Jia, P. Wang, R. Huang, J. Huang, L. He, and Z. Sun, A truss-based approach for densest homogeneous subgraph mining in node-attributed graphs, Comput. Intell., vol. 37, no. 2, pp. 995–1010, 2021.

DOI Google Scholar

[34]

E. Akbas and P. Zhao, Truss-based community search: A truss-equivalence based indexing approach, Proc. VLDB Endow., vol. 10, no. 11, pp. 1298–1309, 2017.

DOI Google Scholar

[35]

Y. Zhang and J. X. Yu, Unboundedness and efficiency of truss maintenance in evolving graphs, in Proc. 2019 Int. Conf. on Management of Data, Amsterdam, The Netherlands, 2019, pp. 1024–1041.

DOI Google Scholar

[36]

R. Zhou, C. Liu, J. X. Yu, W. Liang, and Y. Zhang, Efficient truss maintenance in evolving networks, arXiv preprint arXiv: 1402.2807, 2014.

Google Scholar

[37]

Q. Luo, D. Yu, X. Cheng, Z. Cai, J. Yu, and W. Lv, Batch processing for truss maintenance in large dynamic graphs, IEEE Trans. Comput. Soc. Syst., vol. 7, no. 6, pp. 1435–1446, 2020.

DOI Google Scholar

[38]

A. Montresor, F. De Pellegrini, and D. Miorandi, Distributed k-core decomposition, IEEE Trans. Parallel Distrib. Syst., vol. 24, no. 2, pp. 288–300, 2013.

DOI Google Scholar

[39]

T. G. Kolda, A. Pinar, T. D. Plantenga, and C. Seshadhri, A scalable generative graph model with community structure, SIAM J. Sci. Comput., vol. 36, no. 5, pp. C424–C452, 2014.

DOI Google Scholar

[40]

D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature, vol. 393, no. 6684, pp. 440–442, 1998.

DOI Google Scholar

[41]

A. L. Barabási and R. Albert, Emergence of scaling in random networks, Science, vol. 286, no. 5439, pp. 509–512, 1999.

DOI Google Scholar

[42]

P. Holme and B. J. Kim, Growing scale-free networks with tunable clustering, Phys. Rev. E, vol. 65, no. 2, p. 026107, 2002.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 14 March 2022

Revised: 10 May 2022

Accepted: 14 June 2022

Published: 19 May 2023

Issue date: October 2023

Copyright

Acknowledgements

This work was supported in part by the National Key Research and Development Program of China (No. 2020YFB1005900), in part by National Natural Science Foundation of China (No. 62122042), and in part by Shandong University Multidisciplinary Research and Innovation Team of Young Scholars (No. 2020QNQT017).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).