Home Tsinghua Science and Technology Article
PDF (7 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

Distributed Truss Computation in Dynamic Graphs

School of Computer Science and Technology, Shandong University, Qingdao 266200, China
State 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
Big Data Institute, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China
Show Author Information

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.

Keywords

distributed algorithmdynamic graphgraph miningcohesive subgraphk-truss

References

[1]
Q. Luo, D. Yu, Z. Cai, X. Lin, and X. Cheng, Hypercore maintenance in dynamic hypergraphs, in Proc. 37th IEEE Int. Conf. on Data Engineering, Chania, Greece, 2021, pp. 2051–2056.
Crossref 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. 8th Int. Conf. on Computational Data and Social Networks, Ho Chi Minh City, Vietnam, 2019, pp. 16–32.
Crossref 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.
Crossref Google Scholar
[4]
J. Abello, M. G. C. Resende, and S. Sudarsky, Massive quasi-clique detection, in Proc. 5th Latin American Symp. on LATIN 2002: Theoretical Informatics, Cancun, Mexico, 2002, pp. 598–612.
Crossref Google Scholar
[5]
S. B. Seidman, Network structure and minimum degree, Soc. Netw., vol. 5, no. 3, pp. 269–287, 1983.
Crossref 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.
Crossref Google Scholar
[7]
R. J. Mokken, Cliques, clubs and clans, Qual. Quant., vol. 13, no. 2, pp. 161–173, 1979.
Crossref 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.
Crossref Google Scholar
[10]
M. Sozio and A. Gionis, The community-search problem and how to plan a successful cocktail party, in Proc. 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Washington, DC, USA, 2010, pp. 939–948.
Crossref Google Scholar
[11]
J. Zhang, P. S. Yu, and Y. Lv, Enterprise employee training via project team formation, in Proc. 10th ACM Int. Conf. on Web Search and Data Mining, Cambridge, UK, 2017, pp. 3–12.
Crossref Google Scholar
[12]
T. Chakraborty, S. Patranabis, P. Goyal, and A. Mukherjee, On the formation of circles in co-authorship networks, in Proc. 21th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 109–118.
Crossref 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.
Crossref Google Scholar
[14]
J. Wang and J. Cheng, Truss decomposition in massive networks, Proc. VLDB Endow., vol. 5, no. 9, pp. 812–823, 2012.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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. 44th Int. Conf. on Parallel Processing, Beijing, China, 2015, pp. 709–718.
Crossref Google Scholar
[19]
S. Chu and J. Cheng, Triangle listing in massive networks and its applications, in Proc. 17th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, San Diego, CA, USA, 2011, pp. 672–680.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[22]
Y. Zhang and S. Parthasarathy, Extracting analyzing and visualizing triangle K-core motifs within networks, in Proc. 2012 IEEE 28th Int. Conf. on Data Engineering, Arlington, VA, USA, 2012, pp. 1049–1060.
Crossref Google Scholar
[23]
J. Cohen, Graph twiddling in a mapreduce world, Comput. Sci. Eng., vol. 11, no. 4, pp. 29–41, 2009.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[27]
H. Kabir and K. Madduri, Shared-memory graph truss decomposition, in Proc. 2017 IEEE 24th Int. Conf. on High Performance Computing, Jaipur, India, 2017, pp. 13–22.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[30]
F. Esfahani, J. Wu, V. Srinivasan, A. Thomo, and K. Wu, Fast truss decomposition in large-scale probabilistic graphs, In Proc. 22nd Int. Conf. on Extending Database Technology, Lisbon, Portugal, 2019, pp. 722–725.
Google Scholar
[31]
Z. Zou, Bitruss decomposition of bipartite graphs, in Proc. 21st Int. Conf. on Database Systems for Advanced Applications, Dallas, TX, USA, 2016, pp. 218–233.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 28 Issue 5,
October 2023
Pages 873-887
DOI: 10.26599/TST.2022.9010019
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
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return