nach oben

World Wide Web

Erschienen in:

17.07.2021

Finding attribute diversified community over large attributed networks

verfasst von: Afzal Azeem Chowdhary, Chengfei Liu, Lu Chen, Rui Zhou, Yun Yang

Erschienen in: World Wide Web | Ausgabe 2/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Well connected users are generally discovered in communities which is one of the most important tasks for network data analytics and has tremendous real applications. In recent years, community search in attributed graphs has begun to attract attention, which aims to find communities that are both structure and attribute cohesive. Meanwhile, searching a community that is structure cohesive but attribute diversified, denoted as attribute diversified community search, is still at an early stage. In this paper, we introduce our recent effort for discovering attribute diversified community. In fact, for different applications, the needs of attribute diversification for modelling the community are quite different. We introduce three attribute diversified community models in which attribute diversification takes different roles for presenting as an objective and as a constraint. We also discuss major techniques for speeding up the attribute diversified community search. We conduct extensive experiments to show the effectiveness and efficiency of our algorithms for finding attribute diversified communities in various settings.

Vorheriger Artikel On flexible cohesive subgraph mining

Nächster Artikel Powerful graph of graphs neural network for structured entity analysis

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

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

Al-Baghdadi, A., Lian, X.: Topic-based community search over spatial-social networks. Proc VLDB Endowment 13(12), 2104–2117 (2020)CrossRef

Anwar, M.M., Liu, C., Li, J.: Discovering and tracking query oriented active online social groups in dynamic information network. World Wide Web 22(4), 1819–1854 (2019)CrossRef

Batagelj, V., Zaversnik, M.: An o(m) algorithm for cores decomposition of networks. arXiv:0310049 (2003)

Bi, F., Chang, L., Lin, X., Zhang, W.: An optimal and progressive approach to online search of top-k influential communities. PVLDB 11(9), 1056–1068 (2018)

Bron, C., Kerbosch, J.: Algorithm 457: Finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)CrossRef

Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. In: Annual Symposium on Foundations of Computer Science, pp 649–658 (2012)

Cai, G., Sun, Y.: The minimum augmentation of any graph to a k edge connected graph. Networks 19(1), 151–172 (1989)MathSciNetCrossRef

Chang, L., Yu, J.X., Qin, L., Lin, X., Liu, C., Liang, W.: Efficiently computing k-edge connected components via graph decomposition. In: SIGMOD, pp 205–216. ACM (2013)

10.

Chen, L., Liu, C., Liao, K., Li, J., Zhou, R.: Contextual community search over large social networks. In: ICDE, pp 88–99. IEEE (2019)

11.

Chen, L., Liu, C., Zhou, R., Li, J., Yang, X., Wang, B.: Maximum co-located community search in large scale social networks. PVLDB 11 (10), 1233–1246 (2018)

12.

Chen, L., Liu, C., Zhou, R., Xu, J., Yu, J.X., Li, J.: Finding effective geo-social group for impromptu activities with diverse demands. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp 698–708 (2020)

13.

Chen, S., Wei, R., Popova, D., Thomo, A.: Efficient computation of importance based communities in web-scale networks using a single machine. In: International on Conference on Information and Knowledge Management, pp 1553–1562. ACM (2016)

14.

Chowdhary, A.A., Liu, C., Chen, L., Zhou, R., Yang, Y.: Finding attribute diversified communities in complex networks. In: DASFAA, vol. 2020 (2020)

15.

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

16.

Eppstein, D., Löffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: International Symposium on Algorithms and Computation, pp 403–414. Springer (2010)

17.

Eppstein, D., Löffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. J. Exp. Algorithmics (JEA) 18, 3–1 (2013)MATH

18.

Fang, Y., Cheng, R., Chen, Y., Luo, S., Hu, J.: Effective and efficient attributed community search. VLDB J. 26(6), 803–828 (2017)CrossRef

19.

Fang, Y., Cheng, R., Li, X., Luo, S., Hu, J.: Effective community search over large spatial graphs. PVLDB 10(6), 709–720 (2017)

20.

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 (2019)

21.

Fang, Y., Wang, Z., Cheng, R., Wang, H., Hu, J.: Effective and efficient community search over large directed graphs. TKDE (2018)

22.

Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)MathSciNetCrossRef

23.

Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30–55 (1989)MathSciNetCrossRef

24.

Hsu, B.Y., Shen, C.Y.: On extracting social-aware diversity-optimized groups in social networks. In: 2018 IEEE Global Communications Conference (GLOBECOM), pp 206–212. IEEE (2018)

25.

Huang, X., Cheng, H., Yu, J.X.: Dense community detection in multi-valued attributed networks. Inform. Sci. 314(C), 77–99 (2015)CrossRef

26.

Koch, I.: Enumerating all connected maximal common subgraphs in two graphs. Theor. Comput. Sci. 250(1-2), 1–30 (2001)MathSciNetCrossRef

27.

Li, J., Cai, T., Deng, K., Wang, X., Sellis, T., Xia, F.: Community-diversified influence maximization in social networks. Inf. Syst. 92, 101522 (2020)CrossRef

28.

Li, J., Sellis, T., Culpepper, J.S., He, Z., Liu, C., Wang, J.: Geo-social influence spanning maximization. IEEE Trans. Knowl. Data Eng. 29(8), 1653–1666 (2017)CrossRef

29.

Li, J., Wang, X., Deng, K., Yang, X., Sellis, T., Yu, J.X.: Most influential community search over large social networks. In: ICDE, pp 871–882. IEEE (2017)

30.

Li, R., Qin, L., Ye, F., Wang, G., Yu, J.X., Xiao, X., Xiao, N., Zheng, Z.: Finding skyline communities in multi-valued networks. VLDB J. 29, 1407–1432 (2020)CrossRef

31.

Li, R.H., Qin, L., Ye, F., Yu, J.X., Xiao, X., Xiao, N., Zheng, Z.: Skyline community search in multi-valued networks. In: SIGMOD, pp 457–472. ACM (2018)

32.

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

33.

Li, Y., Sha, C., Huang, X., Zhang, Y.: Community detection in attributed graphs: an embedding approach. In: Thirty-Second AAAI Conference on Artificial Intelligence (2018)

34.

Liu, C., Chen, L., Zhou, R., Chowdhary, A.A.: Attribute diversified community search. In: Qin, L., Zhang, W., Zhang, Y., Peng, Y. , Kato, H., Wang, W., Xiao, C. (eds.) Software Foundations for Data Interoperability and Large Scale Graph Data Analytics, pp 3–17. Springer International Publishing, Cham (2020)

35.

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), vol. 937–948. IEEE (2020)

36.

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)

37.

Nallapati, R.M., Ahmed, A., Xing, E.P., Cohen, W.W.: Joint latent topic models for text and citations. In: SIGKDD, pp 542–550. ACM (2008)

38.

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

39.

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

40.

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

41.

Wang, H.C., Fussell, S.R., Cosley, D.: From diversity to creativity: Stimulating group brainstorming with cultural differences and conversationally-retrieved pictures. In: Proceedings of the ACM 2011 Conference on Computer Supported Cooperative Work, pp 265–274 (2011)

42.

Wang, K., Cao, X., Lin, X., Zhang, W., Qin, L.: Efficient computing of radius-bounded k-cores. In: ICDE, pp 233–244. IEEE (2018)

43.

Wang, Z., Wang, W., Wang, C., Gu, X., Li, B., Meng, D.: Community focusing: yet another query-dependent community detection. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp 329–337 (2019)

44.

Wen, D., Qin, L., Zhang, Y., Chang, L., Chen, L.: Enumerating k-vertex connected components in large graphs. In: ICDE, pp 52–63. IEEE (2019)

45.

Wu, P., Pan, L.: Mining application-aware community organization with expanded feature subspaces from concerned attributes in social networks. Knowl.Based Syst. 139, 1–12 (2018)CrossRef

46.

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

47.

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

48.

Yang, J., McAuley, J., Leskovec, J.: Community detection in networks with node attributes. In: ICDM, pp 1151–1156. IEEE (2013)

49.

Zhang, F., Lin, X., Zhang, Y., Qin, L., Zhang, W.: Efficient community discovery with user engagement and similarity. The VLDB Journal 28(6), 987–1012 (2019)CrossRef

50.

Zhang, F., Zhang, Y., Qin, L., Zhang, W., Lin, X.: When engagement meets similarity: efficient (k, r)-core computation on social networks. PVLDB 10(10), 998–1009 (2017)

51.

Zhang, Q., Li, R.H., Yang, Q., Wang, G., Qin, L.: Efficient top-k edge structural diversity search. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp 205–216. IEEE (2020)

52.

Zhang, Z., Huang, X., Xu, J., Choi, B., Shang, Z.: Keyword-centric community search. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp 422–433. IEEE (2019)

53.

Zhou, R., Liu, C., Yu, J.X., Liang, W., Chen, B., Li, J.: Finding maximal k-edge-connected subgraphs from a large graph. In: EDBT, pp 480–491. ACM (2012)

54.

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

55.

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)

Titel: Finding attribute diversified community over large attributed networks
verfasst von: Afzal Azeem Chowdhary
Chengfei Liu
Lu Chen
Rui Zhou
Yun Yang
Publikationsdatum: 17.07.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-00891-6

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"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2022

Key-core: cohesive keyword subgraph exploration in large graphs

Efficient maintenance for maximal bicliques in bipartite graph streams

Editor’s Note

Powerful graph of graphs neural network for structured entity analysis

Efficient critical relationships identification in bipartite networks

GSBRL : Efficient RDF graph storage based on reinforcement learning