nach oben

The VLDB Journal

Erschienen in:

01.07.2019 | Regular Paper

Fast diversified coherent core search on multi-layer graphs

verfasst von: Rong Zhu, Zhaonian Zou, Jianzhong Li

Erschienen in: The VLDB Journal | Ausgabe 4/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Mining dense subgraphs on multi-layer graphs is an interesting problem, which has witnessed lots of applications in practice. To overcome the limitations of the quasi-clique-based approach, we propose d-coherent core (d-CC), a new notion of dense subgraph on multi-layer graphs, which has several elegant properties. We formalize the diversified coherent core search (DCCS) problem, which finds kd-CCs that can cover the largest number of vertices. We propose a greedy algorithm with an approximation ratio of \(1 - 1/e\) and two search algorithms with an approximation ratio of 1/4. Furthermore, we propose some optimization techniques to further speed up the algorithms. The experiments verify that the search algorithms are faster than the greedy algorithm and produce comparably good results as the greedy algorithm in practice. As opposed to the quasi-clique-based approach, our DCCS algorithms can fast detect larger dense subgraphs that cover most of the quasi-clique-based results.

Vorheriger Artikel Prescriptive analytics: a survey of emerging trends and technologies

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

Nur mit Berechtigung zugänglich

We do not need to consider \(I_0\) since vertices in \(I_0\) are not in the d-core on any layer of the multi-layer graph \({\mathcal {G}}\).

http://string-db.org.

http://cn.aminer.org.

http://konect.uni-koblenz.de.

http://snap.stanford.edu.

http://mips.helmholtz-muenchen.de.

Abdel-Rahim, A., Oman, P., Johnson, B.K., Sadiq R.A.: Assessing surface transportation network component criticality: a multi-layer graph-based approach. In: IEEE Intelligent Transportation Systems Conference, pp. 1000–1003 (2007)

Ausiello, G., Boria, N., Giannakos, A., Lucarelli, G., Paschos, V.T.: Online maximum k-coverage. In: International Conference on Fundamentals of Computation Theory, pp. 181–192 (2011)

Batagelj, V., Zaversnik, M.: An O(m) algorithm for cores decomposition of networks. Comput. Sci. 1(6), 34–37 (2003)

Bilbro, G.L.: Solution of the recirculant multilayer graph problem using compensated simulated annealing. In: Proceedings of SPIE, the International Society for Optical Engineering, vol. 1766 (1992)

Boden, B., Nnemann, S., Hoffmann, H., Seidl, T.: Mining coherent subgraphs in multi-layer graphs with edge labels. In: KDD, pp. 1258–1266 (2012)

Bogue, E.T., de Souza, C.C., Xavier, E.C., Freire, A.S.: An integer programming formulation for the maximum k-subset intersection problem. In: Lecture Notes in Computer Science, vol. 8596, pp. 87–99 (2014)

Chakraborty, T., Narayanam, R.: Cross-layer betweenness centrality in multiplex networks with applications. In: ICDE, pp. 397–408 (2016)

Chuang, J.R., Lin, J.M.: Efficient multi-layer obstacle-avoiding preferred direction rectilinear Steiner tree construction. In: Asia and South Pacific Design Automation Conference, pp. 527–532 (2011)

David, C.W.: Stirling’s Approximation. Betascript Publishing, Saarbrücken (2007)

10.

Dong, X., Frossard, P., Vandergheynst, P., Nefedov, N.: Clustering with multi-layer graphs: a spectral perspective. IEEE Trans. Signal Process. 60(11), 5820–5831 (2011)MathSciNetCrossRefMATH

11.

Fang, Y., Zhang, H., Ye, Y., Li, X.: Detecting hot topics from twitter: a multiview approach. J. Inf. Sci. 40(5), 578–593 (2014)CrossRef

12.

Frickey, T., Weiller, G.: Mclip: motif detection based on cliques of gapped local profile-to-profile alignments. Bioinformatics 23(4), 502–3 (2007)CrossRef

13.

Hu, H., Yan, X., Huang, Y., Han, J., Zhou, X.J.: Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics 21(suppl-1), i213 (2005)CrossRef

14.

Kim, J., Lee, J.G.: Community detection in multi-layer graphs: a survey. ACM SIGMOD Record 44(3), 37–48 (2015)CrossRef

15.

Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J.P., Moreno, Y., Porter, M.A.: Multilayer networks. J. Complex Netw. 2(3), 203–271 (2014)CrossRef

16.

Lee, V.E., Ruan, N., Jin, R., Aggarwal, C.C.: A survey of algorithms for dense subgraph discovery. In: Aggarwal, C.C., Wang, H. (eds.) Managing and Mining Graph Data, pp. 303–336. Springer, New York (2010)CrossRef

17.

Li, H., Nie, Z., Lee, W.C., Giles, L., Wen, J.R.: Scalable community discovery on textual data with relations. In: CIKM, pp. 1203–1212 (2008)

18.

Li, R.H., Qin, L., Yu, J.X., Mao, R.: Influential community search in large networks. PVLDB 8(5), 509–520 (2015)

19.

Liu, J., Wang, C., Gao, J., Han, J.: Multi-view clustering via joint nonnegative matrix factorization. In: SDM, pp. 252–260 (2013)

20.

Pei, J., Jiang, D., Zhang, A.: On mining cross-graph quasi-cliques. In: KDD, pp. 228–238 (2005)

21.

Qi, G.J., Aggarwal, C.C., Huang, T.: Community detection with edge content in social media networks. In: ICDE, pp. 534–545 (2012)

22.

Ruan, Y., Fuhry, D., Parthasarathy, S.: Efficient community detection in large networks using content and links. In: WWW, pp. 1089–1098 (2012)

23.

Sanjeev, K., Gilbert, H.: Multilayer Networks. Wiley, Hoboken (2011)

24.

Silva, A., Jr, W.M., Zaki, M.J.: Mining attribute-structure correlated patterns in large attributed graphs. PVLDB 5(5), 466–477 (2012)

25.

Solé-Ribalta, A., De Domenico, M., Gómez, S., Arenas, A.: Centrality rankings in multiplex networks. In: Proceedings of the 2014 ACM Conference on Web Science, pp. 149–155. ACM (2014)

26.

Sun, Y., Yu, Y., Han, J.: Ranking-based clustering of heterogeneous information networks with star network schema. In: KDD, pp. 797–806 (2009)

27.

Szklarczyk, D., Morris, J.H., Cook, H., Kuhn, M., Wyder, S., Simonovic, M., Santos, A., Doncheva, N.T., Roth, A., Bork, P.: The string database in 2017: quality-controlled protein-protein association networks, made broadly accessible. Nucleic Acids Res. 45(Database), D362–D368 (2017)CrossRef

28.

Tang, W., Lu, Z., Dhillon, I.S.: Clustering with multiple graphs. In: ICDM, pp. 1016–1021 (2009)

29.

Xu, Z., Ke, Y., Wang, Y., Cheng, H., Cheng, J.: A model-based approach to attributed graph clustering. In: SIGMOD, pp. 505–516 (2012)

30.

Yan, X., Han, J.: gSpan: graph-based substructure pattern mining. In: ICDM, pp. 721–724 (2002)

31.

Yang, Y., Yan, D., Wu, H., Cheng, J., Zhou, S., Lui, J.C.S.: Diversified temporal subgraph pattern mining. In: KDD, pp. 1965–1974 (2016)

32.

Zeng, Z., Wang, J., Zhou, L., Karypis, G.: Coherent closed quasi-clique discovery from large dense graph databases. In: KDD, pp. 797–802 (2006)

33.

Zhang, J., Kong, X., Yu, P.S.: Predicting social links for new users across aligned heterogeneous social networks. In: ICDM, pp. 1289–1294 (2013)

34.

Zhou, P., Miao, G., Bing, B.: Cross-layer congestion control and scheduling in multi-hop OFDMA wireless networks. In: IEEE Conference on Global Telecommunications, pp. 1–6 (2009)

35.

Zhou, Y., Cheng, H., Yu, J.X.: Graph clustering based on structural/attribute similarities. PVLDB 2(1), 718–729 (2009)

Titel: Fast diversified coherent core search on multi-layer graphs
verfasst von: Rong Zhu
Zhaonian Zou
Jianzhong Li
Publikationsdatum: 01.07.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: The VLDB Journal / Ausgabe 4/2019
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI: https://doi.org/10.1007/s00778-019-00542-3

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"

Weitere Artikel der Ausgabe 4/2019

Scalable computational geometry in MapReduce

Compact representations of temporal databases

Interleaving with coroutines: a systematic and practical approach to hide memory latency in index joins

Fast and scalable method for distributed Boolean tensor factorization

Parametric schema inference for massive JSON datasets

Prescriptive analytics: a survey of emerging trends and technologies

Premium Partner