Top

Published in:

2021 | OriginalPaper | Chapter

Distributed Algorithm for Truss Maintenance in Dynamic Graphs

Authors : Qi Luo, Dongxiao Yu, Hao Sheng, Jiguo Yu, Xiuzhen Cheng

Published in: Parallel and Distributed Computing, Applications and Technologies

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Cohesive subgraphs are applied in various fields. Mining cohesive components such as k-truss have attracted a lot of effort to improve time efficiency in large-scale graphs. The k-truss is a subgraph where each edge is contained in at least \(k-2\) triangles and the problem of truss decomposition is computing the k-trusses of a graph for all k. However, most graphs in real scenarios are usually changing over time. The previous studies take the static graphs as input, and the truss maintenance in dynamic graphs receives little attention. This paper focuses on distributed algorithms for truss maintenance. We present a distributed model underlying the real distributed processing model Pregel. Based on the model, we propose truss decomposition and truss maintenance algorithms. To confirm the effectiveness and efficiency of the proposed algorithms, we conduct extensive experiments over both real-world and synthetic graphs.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Construction of Completely Independent Spanning Tree Based on Vertex Degree

next chapter Short-Term Load Forecasting Based on CNN-BiLSTM with Bayesian Optimization and Attention Mechanism

http://networkx.github.io.

http://snap.stanford.edu/data/index.html.

Abello, J., Resende, M.G.C., Sudarsky, S.: Massive Quasi-Clique detection. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 598–612. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45995-2_51CrossRef

Akbas, E., Zhao, P.: Truss-based community search: a truss-equivalence based indexing approach. PVLDB 10(11), 1298–1309 (2017)

Cai, Z., He, Z., Guan, X., Li, Y.: Collective data-sanitization for preventing sensitive information inference attacks in social networks. IEEE Trans. Dependable Secur. Comput. 15(4), 577–590 (2018)

Chen, P., Chou, C., Chen, M.: Distributed algorithms for k-truss decomposition. In: 2014 IEEE International Conference on Big Data, Big Data 2014, Washington, DC, USA, 27–30 October 2014, pp. 471–480 (2014)

Cohen, J.: Trusses: Cohesive subgraphs for social network analysis. Technical report. National Security Agency (2008)

Cohen, J.: Graph twiddling in a MapReduce world. Comput. Sci. Eng. 11(4), 29–41 (2009)CrossRef

Das, A., Svendsen, M., Tirthapura, S.: Incremental maintenance of maximal cliques in a dynamic graph. VLDB J. 28(3), 351–375 (2019)CrossRef

Hua, Q., et al.: Faster parallel core maintenance algorithms in dynamic graphs. IEEE Trans. Parallel Distrib. Syst. 31(6), 1287–1300 (2020)CrossRef

Huang, X., Cheng, H., Qin, L., Tian, W., Yu, J.X.: Querying k-truss community in large and dynamic graphs. In: International Conference on Management of Data, SIGMOD, Snowbird, UT, USA, pp. 1311–1322 (2014)

10.

Huang, X., Lakshmanan, L.V.S., Yu, J.X., Cheng, H.: Approximate closest community search in networks. PVLDB 9(4), 276–287 (2015)

11.

Jin, H., Wang, N., Yu, D., Hua, Q., Shi, X., Xie, X.: Core maintenance in dynamic graphs: a parallel approach based on matching. IEEE Trans. Parallel Distrib. Syst. 29(11), 2416–2428 (2018)CrossRef

12.

Luo, Q., Yu, D., Cheng, X., Cai, Z., Yu, J., Lv, W.: Batch processing for truss maintenance in large dynamic graphs. IEEE Trans. Comput. Soc. Syst., 1–12 (2020)

13.

Luo, Q., et al.: Distributed core decomposition in probabilistic graphs. In: Tagarelli, A., Tong, H. (eds.) CSoNet 2019. LNCS, vol. 11917, pp. 16–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34980-6_2CrossRef

14.

Malewicz, G., et al.: Pregel: a system for large-scale graph processing. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD, Indianapolis, Indiana, USA, pp. 135–146 (2010)

15.

Montresor, A., Pellegrini, F.D., Miorandi, D.: Distributed k-core decomposition. IEEE Trans. Parallel Distrib. Syst. 24(2), 288–300 (2013)CrossRef

16.

Rossi, M.G., Malliaros, F.D., Vazirgiannis, M.: Spread it good, spread it fast: identification of influential nodes in social networks. In: Proceedings of the 24th International Conference on World Wide Web Companion, WWW, pp. 101–102. ACM (2015)

17.

Sariyüce, A.E., Pinar, A.: Fast hierarchy construction for dense subgraphs. PVLDB 10(3), 97–108 (2016)

18.

Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269–287 (1983)MathSciNetCrossRef

19.

Shao, Y., Chen, L., Cui, B.: Efficient cohesive subgraphs detection in parallel. In: SIGMOD Conference, pp. 613–624. ACM (2014)

20.

Sheng, H., Zheng, Y., Ke, W., Yu, D., Xiong, Z.: Mining hard samples globally and efficiently for person re-identification. IEEE Internet Things J. PP(99), 1 (2020)

21.

Wang, J., Cheng, J.: Truss decomposition in massive networks. PVLDB 5(9), 812–823 (2012)

22.

Wang, N., Yu, D., Jin, H., Qian, C., Xie, X., Hua, Q.: Parallel algorithm for core maintenance in dynamic graphs. In: Lee, K., Liu, L. (eds.) 37th IEEE International Conference on Distributed Computing Systems, ICDCS, pp. 2366–2371. IEEE Computer Society (2017)

23.

Yu, D., Zhang, L., Luo, Q., Cheng, X., Yu, J., Cai, Z.: Fast skyline community search in multi-valued networks. Big Data Anal. Mining 3(3), 171–180 (2020)CrossRef

24.

Zhang, Y., Yu, J.X.: Unboundedness and efficiency of truss maintenance in evolving graphs. In: SIGMOD, pp. 1024–1041 (2019)

25.

Zhou, R., Liu, C., Yu, J.X., Liang, W., Zhang, Y.: Efficient truss maintenance in evolving networks. CoRR abs/1402.2807 (2014)

Title: Distributed Algorithm for Truss Maintenance in Dynamic Graphs
Authors: Qi Luo
Dongxiao Yu
Hao Sheng
Jiguo Yu
Xiuzhen Cheng
Publisher: Springer International Publishing
Book: Parallel and Distributed Computing, Applications and Technologies
Print ISBN: 978-3-030-69243-8

Electronic ISBN: 978-3-030-69244-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-69244-5_9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner