nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Distributed Algorithm for Truss Maintenance in Dynamic Graphs

verfasst von : Qi Luo, Dongxiao Yu, Hao Sheng, Jiguo Yu, Xiuzhen Cheng

Erschienen in: Parallel and Distributed Computing, Applications and Technologies

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Construction of Completely Independent Spanning Tree Based on Vertex Degree

Nächstes Kapitel 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)

Titel: Distributed Algorithm for Truss Maintenance in Dynamic Graphs
verfasst von: Qi Luo
Dongxiao Yu
Hao Sheng
Jiguo Yu
Xiuzhen Cheng
Verlag: Springer International Publishing
Buch: Parallel and Distributed Computing, Applications and Technologies
Print ISBN: 978-3-030-69243-8

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"