Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

6. Related Work on CSMs and Solutions

verfasst von : Yixiang Fang, Kai Wang, Xuemin Lin, Wenjie Zhang

Erschienen in: Cohesive Subgraph Search Over Large Heterogeneous Information Networks

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In the literature, the topic of CSS on graphs has received tremendous research attention and it has been extensively studied in the past several decades, and most of existing research works focus on conventional homogeneous networks. However, the models and solutions of these works are highly related to the these of CSS over large HINs. In this chapter, we thoroughly review the five groups of works on CSS on homogeneous networks, which are core-, truss-, clique-, connectivity-, and density-based CSMs and solutions. In addition, we also review the works on HIN clustering and compare it with the earlier version of this book.

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 Comparison Analysis
Nächstes Kapitel Future Work and Conclusion
Literatur
10.
Bahmani, B., Kumar, R., & Vassilvitskii, S. (2012). Densest subgraph in streaming and mapreduce. PVLDB, 5(5), 454–465.
12.
Barber, M. J. (2007). Modularity and community detection in bipartite networks. Physical Review E, 76(6), 066102.MathSciNetCrossRef
14.
Batagelj, V., & Zaversnik, M. (2003). An o (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049.
16.
Beckett, S. J. (2016). Improved community detection in weighted bipartite networks. Royal Society Open Science, 3(1), 140536.MathSciNetCrossRef
17.
Berlowitz, D., Cohen, S., & Kimelfeld, B. (2015). Efficient enumeration of maximal k-plexes. In SIGMOD (pp. 431–444). ACM.
18.
Bi, F., Chang, L., Lin, X., & Zhang, W. (2018). An optimal and progressive approach to online search of top-k influential communities. PVLDB, 11(9), 1056–1068.
22.
Cazals, F., & Karande, C. (2008). A note on the problem of reporting maximal cliques. Theoretical Computer Science, 407(1–3), 564–568.MathSciNetMATHCrossRef
25.
Chang, L., Lin, X., Qin, L., Yu, J. X., & Zhang, W. (2015). Index-based optimal algorithms for computing Steiner components with maximum connectivity. In SIGMOD (pp. 459–474). ACM.
26.
Chang, L., Yu, J. X., Qin, L., Lin, X., Liu, C., & Liang, W. (2013). Efficiently computing k-edge connected components via graph decomposition. In SIGMOD (pp. 205–216). ACM.
27.
Charikar, M. (2000). Greedy approximation algorithms for finding dense components in a graph. In International Workshop on Approximation Algorithms for Combinatorial Optimization (pp. 84–95). Springer.
31.
Chen, L., Gao, Y., Zhang, Y., Jensen, C. S., & Zheng, B. (2019). Efficient and incremental clustering algorithms on star-schema heterogeneous graphs. In ICDE (pp. 256–267). IEEE.
32.
Chen, L., Liu, C., Zhou, R., Li, J., Yang, X., & Wang, B. (2018). Maximum co-located community search in large scale social networks. PVLDB, 11(10), 1233–1246.
33.
Chen, L., Liu, C., Zhou, R., Xu, J., & Li, J. (2021). Efficient exact algorithms for maximum balanced biclique search in bipartite graphs (pp. 248–260).
34.
Chen, P.-L., Chou, C.-K., & Chen, M.-S. (2014). Distributed algorithms for k-truss decomposition. In Big data (pp. 471–480). IEEE.
35.
Chen, S., Wei, R., Popova, D., & Thomo, A. (2016). Efficient computation of importance based communities in web-scale networks using a single machine. In CIKM (pp. 1553–1562).
37.
Chen, Y., Fang, Y., Cheng, R., Li, Y., Chen, X., & Zhang, J. (2018). Exploring communities in large profiled graphs. IEEE Transactions on Knowledge and Data Engineering, 31(8), 1624–1629.CrossRef
38.
Cheng, J., Ke, Y., Chu, S., & Özsu, M. T. (2011). Efficient core decomposition in massive networks. In ICDE (pp. 51–62). IEEE.
39.
Cheng, J., Ke, Y., Fu, A. W.-C., Yu, J. X., & Zhu, L. (2011). Finding maximal cliques in massive networks. TODS, 36(4), 1–34.CrossRef
41.
Cohen, J. (2008). Trusses: Cohesive subgraphs for social network analysis. National security Agency Technical Report, 16, 3–1.
42.
Danisch, M., Balalau, O., & Sozio, M. (2018). Listing k-cliques in sparse real-world graphs. In WWW (pp. 589–598).
43.
Danisch, M., Chan, T.-H. H., & Sozio, M. (2017). Large scale density-friendly graph decomposition via convex programming. In WWW (pp. 233–242).
48.
Ding, D., Li, H., Huang, Z., & Mamoulis, N. (2017). Efficient fault-tolerant group recommendation using alpha-beta-core. In CIKM (pp. 2047–2050).
50.
Dormann, C. F., & Strauss, R. (2014). A method for detecting modules in quantitative bipartite networks. Methods in Ecology and Evolution, 5(1), 90–98.CrossRef
54.
Fang, Y., Cheng, R., Chen, Y., Luo, S., & Hu, J. (2017). Effective and efficient attributed community search. The VLDB Journal, 26(6), 803–828.CrossRef
55.
Fang, Y., Cheng, R., Li, X., Luo, S., & Hu, J. (2017). Effective community search over large spatial graphs. PVLDB, 10(6), 709–720.
56.
Fang, Y., Cheng, R., Luo, S., & Hu, J. (2016). Effective community search for large attributed graphs. PVLDB, 9(12), 1233–1244.
57.
Fang, Y., Cheng, R., Luo, S., Hu, J., & Huang, K. (2017). C-explorer: Browsing communities in large graphs. PVLDB, 10(12), 1885–1888.
58.
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020). A survey of community search over big graphs. The VLDB Journal, 29(1), 353–392.CrossRef
59.
Fang, Y., Wang, K., Lin, X., & Zhang, W. (2021). Cohesive subgraph search over big heterogeneous information networks: Applications, challenges, and solutions. ACM SIGMOD (pp. 2829–2838).
60.
Fang, Y., Wang, Z., Cheng, R., Li, X., Luo, S., Hu, J., & Chen, X. (2019). On spatial-aware community search. TKDE, 31(4), 783–798.
61.
Fang, Y., Wang, Z., Cheng, R., Wang, H., & Hu, J. (2019). Effective and efficient community search over large directed graphs. TKDE, 31(11), 2093–2107.
63.
Fang, Y., Yu, K., Cheng, R., Lakshmanan, L. V., & Lin, X. (2019). Efficient algorithms for densest subgraph discovery. PVLDB, 12(11), 1719–1732.
67.
Gallo, G., Grigoriadis, M. D., & Tarjan, R. E. (1989). A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18(1), 30–55.MathSciNetMATHCrossRef
69.
Giatsidis, C., Thilikos, D. M., & Vazirgiannis, M. (2013). D-cores: Measuring collaboration of directed graphs based on degeneracy. Knowledge and Information Systems, 35(2), 311–343.CrossRef
70.
Gibbons, A. (1985). Algorithmic graph theory. Cambridge University Press.MATH
73.
Goldberg, A. V. (1984). Finding a maximum density subgraph. University of California Berkeley, CA.
75.
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2007). Module identification in bipartite and directed networks. Physical Review E, 76(3), 036102.CrossRef
82.
Hu, J., Wu, X., Cheng, R., Luo, S., & Fang, Y. (2016). Querying minimal Steiner maximum-connected subgraphs in large graphs. In CIKM (pp. 1241–1250).
83.
Hu, J., Wu, X., Cheng, R., Luo, S., & Fang, Y. (2017). On minimal Steiner maximum-connected subgraph queries. TKDE, 29(11), 2455–2469.
84.
Huang, X., Cheng, H., Qin, L., Tian, W., & Yu, J. X. (2014). Querying k-truss community in large and dynamic graphs. In SIGMOD (pp. 1311–1322). ACM.
85.
Huang, X., & Lakshmanan, L. V. (2017). Attribute-driven community search. PVLDB, 10(9), 949–960.
86.
Huang, X., Lakshmanan, L. V., & Xu, J. (2017). Community search over big graphs: Models, algorithms, and opportunities. In ICDE (pp. 1451–1454). IEEE.
87.
Huang, X., Lakshmanan, L. V., Yu, J. X., & Cheng, H. (2015). Approximate closest community search in networks. PVLDB, 9(4).
95.
Khaouid, W., Barsky, M., Srinivasan, V., & Thomo, A. (2015). K-core decomposition of large networks on a single pc. PVLDB, 9(1), 13–23.
99.
Larremore, D. B., Clauset, A., & Jacobs, A. Z. (2014). Efficiently inferring community structure in bipartite networks. Physical Review E, 90(1), 012805.CrossRef
104.
Li, R.-H., Gao, S., Qin, L., Wang, G., Yang, W., & Yu, J. X. (2020). Ordering heuristics for k-clique listing. PVLDB, 13(12), 2536–2548.
105.
Li, R.-H., Qin, L., Ye, F., Yu, J. X., Xiao, X., Xiao, N., & Zheng, Z. (2018). Skyline community search in multi-valued networks. In SIGMOD (pp. 457–472).
106.
Li, R.-H., Qin, L., Yu, J. X., & Mao, R. (2015). Influential community search in large networks. PVLDB, 8(5), 509–520.
108.
Li, R.-H., Yu, J. X., & Mao, R. (2013). Efficient core maintenance in large dynamic graphs. TKDE, 26(10), 2453–2465.
116.
Liu, Q., Zhao, M., Huang, X., Xu, J., & Gao, Y. (2020). Truss-based community search over large directed graphs. In SIGMOD (pp. 2183–2197).
117.
Liu, Q., Zhu, Y., Zhao, M., Huang, X., Xu, J., and Gao, Y. (2020). Vac: Vertex-centric attributed community search. In ICDE (pp. 937–948). IEEE.
119.
Liu, X., & Murata, T. (2010). Community detection in large-scale bipartite networks. Transactions of the Japanese Society for Artificial Intelligence, 25(1), 16–24.CrossRef
120.
Luo, L., Fang, Y., Cao, X., Zhang, X., & Zhang, W. (2021). Detecting communities from heterogeneous graphs: A context path-based graph neural network model. In CIKM (pp. 1170–1180).
124.
Ma, C., Fang, Y., Cheng, R., Lakshmanan, L. V., Zhang, W., & Lin, X. (2020). Efficient algorithms for densest subgraph discovery on large directed graphs. In SIGMOD (pp. 1051–1066). ACM.
125.
Ma, C., Fang, Y., Cheng, R., Lakshmanan, L. V., Zhang, W., & Lin, X. (2021). Efficient directed densest subgraph discovery. ACM SIGMOD Record, 50(1), 33–40.CrossRef
126.
Ma, C., Fang, Y., Cheng, R., Lakshmanan, L. V., Zhang, W., & Lin, X. (2021). On directed densest subgraph discovery. ACM Transactions on Database Systems (TODS), 46(4), 1–45.MathSciNetCrossRef
131.
Mitzenmacher, M., Pachocki, J., Peng, R., Tsourakakis, C., & Xu, S. C. (2015). Scalable large near-clique detection in large-scale networks via sampling. In SIGKDD (pp. 815–824). ACM.
132.
Montresor, A., De Pellegrini, F., & Miorandi, D. (2012). Distributed k-core decomposition. IEEE TPDS, 24(2), 288–300.
140.
Qin, L., Li, R.-H., Chang, L., & Zhang, C. (2015). Locally densest subgraph discovery. In KDD (pp. 965–974). ACM.
141.
Saito, K., Yamada, T., & Kazama, K. (2008). Extracting communities from complex networks by the k-dense method. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 91(11), 3304–3311.CrossRef
142.
Sarıyüce, A. E., Gedik, B., Jacques-Silva, G., Wu, K.-L., & Çatalyürek, Ü. V. (2016). Incremental k-core decomposition: Algorithms and evaluation. VLDBJ, 25(3), 425–447.CrossRef
144.
Schmidt, M. C., Samatova, N. F., Thomas, K., & Park, B.-H. (2009). A scalable, parallel algorithm for maximal clique enumeration. Journal of Parallel and Distributed Computing, 69(4), 417–428.CrossRef
145.
147.
Shi, C., Li, Y., Zhang, J., Sun, Y., & Philip, S. Y. (2016). A survey of heterogeneous information network analysis. TKDE, 29(1), 17–37.
148.
Shi, C., Wang, R., Li, Y., Yu, P. S., & Wu, B. (2014). Ranking-based clustering on general heterogeneous information networks by network projection. In CIKM (pp. 699–708). ACM.
152.
Sun, Y., Aggarwal, C. C., & Han, J. (2012). Relation strength-aware clustering of heterogeneous information networks with incomplete attributes. PVLDB, 5(5), 394–405.
154.
Sun, Y., Han, J., Zhao, P., Yin, Z., Cheng, H., & Wu, T. (2009). Rankclus: Integrating clustering with ranking for heterogeneous information network analysis. In EDBT (pp. 565–576). ACM.
155.
Sun, Y., Norick, B., Han, J., Yan, X., Yu, P. S., & Yu, X. (2012). Integrating meta-path selection with user-guided object clustering in heterogeneous information networks. In SIGKDD (pp. 1348–1356). ACM.
157.
Sun, Y., Yu, Y., & Han, J. (2009). Ranking-based clustering of heterogeneous information networks with star network schema. In SIGKDD (pp. 797–806). ACM.
160.
Tatti, N., & Gionis, A. (2015). Density-friendly graph decomposition. In WWW (pp. 1089–1099).
161.
Tomita, E., Tanaka, A., & Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1), 28–42.MathSciNetMATHCrossRef
162.
Tsourakakis, C. (2015). The k-clique densest subgraph problem. In WWW (pp. 1122–1132).
163.
Verma, A., & Butenko, S. (2013). Network clustering via clique relaxations: A community based. Graph Partitioning and Graph Clustering, 588, 129.MathSciNetMATHCrossRef
164.
Wang, J., & Cheng, J. (2012). Truss decomposition in massive networks. PVLDB, 5(9), 812–823.
166.
Wang, K., Cao, X., Lin, X., Zhang, W., & Qin, L. (2018). Efficient computing of radius-bounded k-cores. In ICDE (pp. 233–244). IEEE.
174.
Wang, Z., Yuan, Y., Zhou, X., & Qin, H. (2020). Effective and efficient community search in directed graphs across heterogeneous social networks. In Australasian Database Conference (ADC) (pp. 161–172).
175.
Wen, D., Qin, L., Zhang, Y., Lin, X., & Yu, J. X. (2016). I/O efficient core graph decomposition at web scale. In ICDE (pp. 133–144). IEEE.
178.
Yan, X., Zhou, X. J., & Han, J. (2005). Mining closed relational graphs with connectivity constraints. In SIGKDD (pp. 324–333). ACM.
184.
Zeng, Z., Wang, J., Zhou, L., & Karypis, G. (2007). Out-of-core coherent closed quasi-clique mining from large dense graph databases. TODS, 32(2), 13–es.
186.
Zhang, F., Zhang, Y., Qin, L., Zhang, W., & Lin, X. (2017). When engagement meets similarity: Efficient (k, r)-core computation on social networks. PVLDB, 10(10), 998–1009.
188.
Zhang, Y., & Parthasarathy, S. (2012). Extracting analyzing and visualizing triangle k-core motifs within networks. In ICDE (pp. 1049–1060). IEEE.
192.
Zhang, Y., & Yu, J. X. (2019). Unboundedness and efficiency of truss maintenance in evolving graphs. In SIGMOD (pp. 1024–1041). ACM.
193.
Zhang, Y., Yu, J. X., Zhang, Y., & Qin, L. (2017). A fast order-based approach for core maintenance. In ICDE (pp. 337–348). IEEE.
194.
Zhang, Z., Huang, X., Xu, J., Choi, B., & Shang, Z. (2019). Keyword-centric community search. In ICDE (pp. 422–433). IEEE.
196.
Zhou, R., Liu, C., Yu, J. X., Liang, W., Chen, B., & Li, J. (2012). Finding maximal k-edge-connected subgraphs from a large graph. In EDBT (pp. 480–491).
197.
Zhou, R., Liu, C., Yu, J. X., Liang, W., & Zhang, Y. (2014). Efficient truss maintenance in evolving networks. arXiv preprint arXiv:1402.2807.
199.
Zhou, Y., & Liu, L. (2013). Social influence based clustering of heterogeneous information networks. In KDD (pp. 338–346). ACM.
201.
Zhou, Z., & Amini, A. A. (2019). Analysis of spectral clustering algorithms for community detection: The general bipartite setting. Journal of Machine Learning Research, 20, 47–1.MathSciNetMATH
202.
Zhou, Z., & Amini, A. A. (2020). Optimal bipartite network clustering. Journal of Machine Learning Research, 21(40), 1–68.MathSciNetMATH
205.
Zhu, Y., He, J., Ye, J., Qin, L., Huang, X., & Yu, J. X. (2020). When structure meets keywords: Cohesive attributed community search. In CIKM (pp. 1913–1922).
Metadaten
Titel
Related Work on CSMs and Solutions
verfasst von
Yixiang Fang
Kai Wang
Xuemin Lin
Wenjie Zhang
Copyright-Jahr
2022
Buch
Cohesive Subgraph Search Over Large Heterogeneous Information Networks

Print ISBN: 978-3-030-97567-8

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

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-030-97568-5_6