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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
World Wide Web
Erschienen in: World Wide Web 2/2022

22.10.2021

Community search over large semantic-based attribute graphs

verfasst von: Peiying Lin, Siyang Yu, Xu Zhou, Peng Peng, Kenli Li, Xiangke Liao

Erschienen in: World Wide Web | Ausgabe 2/2022

Einloggen

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

search-config
loading …

Abstract

Community search has attracted widespread attention in many fields, such as protein interaction networks, social networks, and knowledge graphs. It aims to find cohesive subgraphs that are closely related to a query vertex q in a graph G. Existing community search researches based on attribute graphs rarely consider the semantic information of attributes and interpretability of the community. In this paper, we study Community Search over Semantic-based Attribute Graphs (CSSAG), where the attribute of each vertex in the graph G is a semantic graph. To guarantee both the attribute and structure cohesiveness of the community, we introduce the maximal common subgraph and minimal degree metric to measure the cohesiveness of the attribute and structure, respectively. In this way, we can get more understandable and diverse cohesive subgraphs as depicted in the experiment. Also, we design three different online query algorithms by integrating new pruning strategies to shift the search space. Extensive experiments on real-world networks show that our approaches are effective and efficient.
Vorheriger Artikel Locating pivotal connections: the K-Truss minimization and maximization problems
Nächster Artikel K-truss community most favorites query based on top-t

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

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

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
Fußnoten
Literatur
1.
Batagelj, V., Zaversnik, M.: An o (m) algorithm for cores decomposition of networks arXiv preprint cs/0310049 (2003)
2.
Bhatt, S., Padhee, S., Sheth, A., Chen, K., Shalin, V., Doran, D., Minnery, B.: Knowledge graph enhanced community detection and characterization. In: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 51–59 (2019)
3.
Chen, Y., Fang, Y., Cheng, R., Li, Y., Chen, X., Zhang, J.: Exploring communities in large profiled graphs. IEEE Trans. Knowl. Data Eng. 31 (8), 1624–1629 (2018)CrossRef
4.
Chu, D., Zhang, F., Lin, X., Zhang, W., Zhang, Y., Xia, Y., Zhang, C.: Finding the Best K in Core Decomposition: a Time and Space Optimal Solution. In: 2020 IEEE 36Th International Conference on Data Engineering (ICDE), Pp. 685–696. IEEE (2020)
5.
El Radie, E., Salem, S.: A Parallel Algorithm for Mining Maximal Frequent Subgraphs. In: 2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Pp. 1965–1971. IEEE (2017)
6.
Fang, Y., Cheng, R., Luo, S., Hu, J.: Effective community search for large attributed graphs. Proceedings of the VLDB Endowment 9(12), 1233–1244 (2016)CrossRef
7.
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., Lin, X.: A survey of community search over big graphs. The VLDB Journal 29(1), 353–392 (2020)CrossRef
8.
Fang, Y., Wang, Z., Cheng, R., Li, X., Luo, S., Hu, J., Chen, X.: On spatial-aware community search. IEEE Trans. Knowl. Data Eng. 31 (4), 783–798 (2018)CrossRef
9.
Fang, Y., Wang, Z., Cheng, R., Wang, H., Hu, J.: Effective and efficient community search over large directed graphs. IEEE Trans. Knowl. Data Eng. 31(11), 2093–2107 (2018)CrossRef
10.
Fang, Y., Yang, Y., Zhang, W., Lin, X., Cao, X.: Effective and efficient community search over large heterogeneous information networks. Proceedings of the VLDB Endowment 13(6), 854–867 (2020)CrossRef
11.
Galimberti, E., Bonchi, F., Gullo, F., Lanciano, T.: Core decomposition in multilayer networks: Theory, algorithms, and applications. ACM Transactions on Knowledge Discovery from Data (TKDD) 14(1), 1–40 (2020)CrossRef
12.
Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Analysis and applications 13(1), 113–129 (2010)MathSciNetCrossRef
13.
Kabir, H., Madduri, K.: Parallel K-Core Decomposition on Multicore Platforms. In: 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Pp. 1482–1491. IEEE (2017)
14.
Li, J., Wang, X., Deng, K., Yang, X., Sellis, T., Yu, J. X.: Most Influential Community Search over Large Social Networks. In: 2017 IEEE 33Rd International Conference on Data Engineering (ICDE), Pp. 871–882. IEEE (2017)
15.
Li, R. H., Su, J., Qin, L., Yu, J. X., Dai, Q.: Persistent Community Search in Temporal Networks. In: 2018 IEEE 34Th International Conference on Data Engineering (ICDE), Pp. 797–808. IEEE (2018)
16.
Liu, B.: Efficient Core Computation in Bipartite and Multilayer Graphs. Ph.D. thesis, Tsinghua University (2020)
17.
Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W., Zhou, J.: Efficient (α, β)-core computation in bipartite graphs. The VLDB Journal 29(5), 1075–1099 (2020)CrossRef
18.
Liu, B., Zhang, F., Zhang, C., Zhang, W., Lin, X.: Corecube: Core Decomposition in Multilayer Graphs. In: International Conference on Web Information Systems Engineering, Pp. 694–710. Springer (2020)
19.
Liu, Q., Zhu, Y., Zhao, M., Huang, X., Xu, J., Gao, Y.: Vac: Vertex-Centric Attributed Community Search. In: 2020 IEEE 36Th International Conference on Data Engineering (ICDE), Pp. 937–948. IEEE (2020)
20.
Luo, J., Cao, X., Xie, X., Qu, Q., Xu, Z., Jensen, C. S.: Efficient Attribute-Constrained Co-Located Community Search. In: 2020 IEEE 36Th International Conference on Data Engineering (ICDE), Pp. 1201–1212. IEEE (2020)
21.
Luo, W., Zhou, X., Yang, J., Peng, P., Xiao, G., Gao, Y.: Efficient approaches to top-r influential community search IEEE Internet of Things Journal (2020)
22.
Ma, C., Fang, Y., Cheng, R., Lakshmanan, L. V., Zhang, W., Lin, X.: Efficient algorithms for densest subgraph discovery on large directed graphs. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1051–1066 (2020)
23.
Marche, C., Atzori, L., Pilloni, V., Nitti, M.: How to exploit the social internet of things: Query generation model and device profiles’ dataset. Computer Networks p 107248 (2020)
24.
Peng, Y., Zhang, Y., Zhang, W., Lin, X., Qin, L.: Efficient Probabilistic K-Core Computation on Uncertain Graphs. In: 2018 IEEE 34Th International Conference on Data Engineering (ICDE), Pp. 1192–1203. IEEE (2018)
25.
Sozio, M., Gionis, A.: The community-search problem and how to plan a successful cocktail party. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 939–948 (2010)
26.
Sun, H., Huang, R., Jia, X., He, L., Sun, M., Wang, P., Sun, Z., Huang, J.: Community search for multiple nodes on attribute graphs. Knowl.-Based Syst. 193, 105393 (2020)CrossRef
27.
Wang, K., Cao, X., Lin, X., Zhang, W., Qin, L.: Efficient Computing of Radius-Bounded K-Cores. In: 2018 IEEE 34Th International Conference on Data Engineering (ICDE), Pp. 233–244. IEEE (2018)
28.
Wang, K., Lin, X., Qin, L., Zhang, W., Zhang, Y.: Efficient Bitruss Decomposition for Large-Scale Bipartite Graphs. In: 2020 IEEE 36Th International Conference on Data Engineering (ICDE), Pp. 661–672. IEEE (2020)
29.
Wang, K., Zhang, W., Lin, X., Zhang, Y., Qin, L., Zhang, Y.: Efficient and effective community search on large-scale bipartite graphs. arXiv preprint arXiv:2011.​08399 (2020)
30.
Wang, Y., Huang, H., Feng, C.: Query expansion based on a feedback concept model for microblog retrieval. In: Proceedings of the 26th International Conference on World Wide Web, pp. 559–568 (2017)
31.
Wang, Y., Li, Y., Fan, J., Ye, C., Chai, M.: A survey of typical attributed graph queries. World Wide Web, pp. 1–50 (2020)
32.
Wang, Y., Li, Y., Fan, J., Ye, C., Chai, M.: A survey of typical attributed graph queries. World Wide Web 24(1), 297–346 (2021)CrossRef
33.
Wu, W., Li, H., Wang, H., Zhu, K. Q.: Probase: a probabilistic taxonomy for text understanding. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pp. 481–492 (2012)
34.
Wu, Y., Jin, R., Zhu, X., Zhang, X.: Finding Dense and Connected Subgraphs in Dual Networks. In: 2015 IEEE 31St International Conference on Data Engineering, Pp. 915–926. IEEE (2015)
35.
Wu, Y., Zhu, X., Li, L., Fan, W., Jin, R., Zhang, X.: Mining dual networks: models, algorithms, and applications. ACM Transactions on Knowledge Discovery from Data (TKDD) 10(4), 1–37 (2016)CrossRef
36.
Xie, X., Song, M., Liu, C., Zhang, J., Li, J.: Effective influential community search on attributed graph. Neurocomputing 444, 111–125 (2021)CrossRef
37.
Xu, J., Fu, X., Wu, Y., Luo, M., Xu, M., Zheng, N.: Personalized top-n influential community search over large social networks. World Wide Web 23(3), 2153–2184 (2020)CrossRef
38.
Yang, Y., Fang, Y., Lin, X., Zhang, W.: Effective and Efficient Truss Computation over Large Heterogeneous Information Networks. In: 2020 IEEE 36Th International Conference on Data Engineering (ICDE), Pp. 901–912. IEEE (2020)
39.
Zhang, C., Zhang, Y., Zhang, W., Qin, L., Yang, J.: Efficient Maximal Spatial Clique Enumeration. In: 2019 IEEE 35Th International Conference on Data Engineering (ICDE), Pp. 878–889. IEEE (2019)
40.
Zhang, Y., Qin, L., Zhang, F., Zhang, W.: Hierarchical Decomposition of Big Graphs. In: 2019 IEEE 35Th International Conference on Data Engineering (ICDE), Pp. 2064–2067. IEEE (2019)
41.
Zhou, W., Huang, H., Hua, Q.S., Yu, D., Jin, H., Fu, X.: Core decomposition and maintenance in weighted graph. World Wide Web pp. 1–21
42.
Zhu, Y., He, J., Ye, J., Qin, L., Huang, X., Yu, J. X.: When structure meets keywords: Cohesive attributed community search. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 1913–1922 (2020)
43.
Zou, L., Özsu, M. T., Chen, L., Shen, X., Huang, R.: Zhao, d.: gstore: a graph-based sparql query engine. The VLDB journal 23(4), 565–590 (2014)CrossRef
Metadaten
Titel
Community search over large semantic-based attribute graphs
verfasst von
Peiying Lin
Siyang Yu
Xu Zhou
Peng Peng
Kenli Li
Xiangke Liao
Publikationsdatum
22.10.2021
Verlag
Springer US
Erschienen in
World Wide Web / Ausgabe 2/2022
Print ISSN: 1386-145X
Elektronische ISSN: 1573-1413
DOI
https://doi.org/10.1007/s11280-021-00942-y

Weitere Artikel der Ausgabe 2/2022

World Wide Web 2/2022 Zur Ausgabe

OriginalPaper

On flexible cohesive subgraph mining

OriginalPaper

Efficient distributed path computation on RDF knowledge graphs using partial evaluation

OriginalPaper

Efficient critical relationships identification in bipartite networks

OriginalPaper

GSBRL : Efficient RDF graph storage based on reinforcement learning

OriginalPaper

VEK: a vertex-oriented approach for edge k-core problem

OriginalPaper

Fast datalog evaluation for batch and stream graph processing

Premium Partner

    Bildnachweise