nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Defining and Evaluating Network Communities Based on Ground-Truth in Online Social Networks

verfasst von : Sanjeev Dhawan, Kulvinder Singh, Amit Batra

Erschienen in: Recent Innovations in Computing

Verlag: Springer Singapore

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A social network is a cluster or aggregation of vertices such as persons or social entities, and edges which are used to depict personal relationship between these nodes. Social networks have a noteworthy role in the movement of data, and social network exploration has gained a focus in research. The analysis of these social networks has resulted into uncovering of variety of communities in the network. The main objective of uncovering the structure of a community is to break the network into dense areas of the graph, and these dense areas represent entities which are related closely and hence they belong to a community. Plentiful algorithms have been suggested and recommended, and surveys have been conducted currently. In this manuscript, we will discuss numerous strategies for uncovering the structure of communities and techniques which have been suggested so far. We will divide these algorithms into several categories. These categories correspond to traditional approach of community detection, overlapping community detection, established clustering techniques for uncovering the structure of communities, nonclique-based techniques for uncovering the structure of communities, community detection using genetic algorithms, improved modularity approach for uncovering the structure of communities and so forth. We will start by discussing and understanding several metrics which can be used to ascertain the structure and hence the quality of communities. We will also compare all these community detection algorithms based on approaches used, along with parameters these algorithms depend on.

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 Particle Swarm Optimization and Genetic Mutation Based Routing Technique for IoT-Based Homogeneous Software-Defined WSNs

Nächstes Kapitel Microstrip Patch Antenna with Truncated Edges for Bandwidth Improvement for Wireless Applications

Ozturk, K.: Community Detection in Social Networks. Middle East Technical University, Graduate School of Natural and Applied Sciences (2014)

Tang L., Liu H.: Community Detection and Mining in Social Media, vol. 2, no. 1 (2010)

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

Coscia, M., Giannotti, F., Pedreschi, D.: A classification for community discovery methods in complex networks. Stat. Anal. Data Min. 4(5), 512–546 (2011)MathSciNetMATHCrossRef

Fortunato S., Castellano C.: Community structure in graphs. Comput. Complex. Theory, Tech. Appl. 9781461418, 490–512 (2012)

Porter, M.A., Onnela, J.P., Mucha, P.J.: Communities in networks. Not. Am. Math Soc. 56, 1082–1097 (2009)

Danon, L., Díaz-Guilera, A., Duch, J., Arenas, A.: Comparing community structure identification. J. Stat. Mech. Theory Exp. 09008(9), 219–228 (2005)

Plantié, M. and Crampes, M.: Survey on social community detection. Soc. Media Retr. Comput. Commun. Networks. London SpringerVerlag, 65–85 (2013)

Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99, 7821–7826 (2002)

10.

Newman M. E. J., Girvan M.: Finding and evaluating community structure in networks. Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. 69(22), 1–15 (2004)

11.

Rattigan, M.J., Maier, M., Jensen, D.: Graph clustering with network structure indices. ACM Int. Conf. Proc. Ser. 227, 783–790 (2007)

12.

Chen, J., Yuan, B.: Detecting functional modules in the yeast protein-protein interaction network. Bioinformatics 22(18), 2283–2290 (2006)CrossRef

13.

Holme, P., Huss, M., Jeong, H.: Subnetwork hierarchies of biochemical pathways. Bioinformatics 19(4), 532–538 (2003)CrossRef

14.

Pinney, J.W., Westhead, D.R.: Betweenness-based decomposition methods for social and biological networks. Soft Matter, 87–90 (2005)

15.

Gregory, S.: An algorithm to find overlapping community structure in networks. Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 4702 LNAI, pp. 91–102, (2007)

16.

Guimerà, R., Danon, L., Díaz-Guilera, A., Giralt, F., Arenas, A.: Self-similar community structure in a network of human interactions. Phys. Rev. E - Stat. Physics, Plasmas, Fluids, Relat. Interdiscip. Top. 68(6), 1–4 (2003)

17.

Arenas, A., Danon, L., Díaz-Guilera, A., Gleiser, P.M., Guimerà, R.: Community analysis in social networks. Eur. Phys. J. B 38(2), 373–380 (2004)MATHCrossRef

18.

Tyler, J.R., Wilkinson, D.M., Huberman, B.A.: E-Mail as spectroscopy: automated discovery of community structure within organizations. Inf. Soc. 21(2), 133–141 (2005)CrossRef

19.

Moon, S., Lee, J.G., Kang, M., Choy, M., Woo, L.J.: Parallel community detection on large graphs with MapReduce and GraphChi. Data Knowl. Eng. 104, 17–31 (2016)CrossRef

20.

Newman, M.E.J.: Fast algorithm for detecting community structure in networks. Phys. Rev. E - Stat. Physics, Plasmas, Fluids, Relat. Interdiscip. Top. 69(6), 5 (2004)

21.

Ye, Z., Hu, S., Yu, J.: Adaptive clustering algorithm for community detection in complex networks. Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. 78(4), 1–6 (2008)

22.

Wahl, S., Sheppard J.: Hierarchical fuzzy spectral clustering in social networks using spectral characterization. In: Proceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015, pp. 305–310 (2015)

23.

Falkowski, T., Barth, A., Spiliopoulou, M.: DENGRAPH: a density-based community detection algorithm. In: Procedings of the IEEE/WIC/ACM International Conference on Web Intelligence WI 2007, pp. 112–115 (2007)

24.

Dongen, S.V.: Graph clustering by flow simulation. University of Utrecht (2000)

25.

Nikolaev, A.G., Razib, R., Kucheriya, A.: On efficient use of entropy centrality for social network analysis and community detection. Soc. Netw. 40, 154–162 (2015)CrossRef

26.

Steinhaeuser, K., Chawla, N.V.: Identifying and evaluating community structure in complex networks. Pattern Recognit. Lett. 31(5), 413–421 (2010)CrossRef

27.

Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E - Stat. Physics Plasmas Fluids Relat. Interdiscip. Top. 70(6), 6 (2004)

28.

Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 10, 2008 (2008)MATH

29.

Guimerà, R., Sales-Pardo, M., Amaral, L.A.N.: Modularity from fluctuations in random graphs and complex networks. Phys. Rev. E - Stat. Physics, Plasmas, Fluids, Relat. Interdiscip. Top. 70(2), 4 (2004)

30.

Zhou, Z., Wang, W., Wang, L.: Community detection based on an improved modularity. Commun. Comput. Inf. Sci. 321 CCIS, 638–645 (2012)

31.

Duch, J., Arenas, A.: Community detection in complex networks using extremal optimization. Phys. Rev. E - Stat. Nonlinear Soft Matter Phys. 72(2), 1–4 (2005)

32.

Zhou, Z., Wang, W., Wang, L.: Community detection based on an improved modularity. In: Liu, C.L., Zhang, C., Wang, L. (eds.) Pattern Recognition. Communications in Computer and Information Science, vol. 321, Springer (2012)

33.

Chen, Y., Huang, C., Zhai, K.: Scalable Community Detection Algorithm with MapReduce. Commun. ACM 53, 359–366 (2009)

34.

Newman, M.E.J.: Analysis of weighted networks. Phys. Rev. E - Stat. Physics, Plasmas, Fluids, Relat. Interdiscip. Top. 70(5), 9 (2004)

35.

Newman, M.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103, 8577–8582 (2006)CrossRef

36.

Pizzuti, C.: GA-Net: a genetic algorithm for community detection in social networks. Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5199 LNCS, pp. 1081–1090 (2008)

37.

Pizzuti, C.: A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans. Evol. Comput. 16(3), 418–430 (2012)CrossRef

38.

Hafez, A.I., Ghali, N.I., Hassanien, A.E., Fahmy, A.A.: Genetic algorithms for community detection in social networks. Int. Conf. Intell. Syst. Des. Appl. ISDA,. 460–465 (2012)

39.

Mazur, P., ZmarzŁowski, K., OrŁowski, A.J.: Genetic algorithms approach to community detection. Acta Phys. Pol. A 117(4), 703–705 (2010)CrossRef

40.

Liu, X., Li, D., Wang, S., Tao, Z.: Effective algorithm for detecting community structure in complex networks based on GA and clustering. Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 4488 LNCS, no. PART 2, pp. 657–664 (2007)

41.

Tasgin, M., Herdagdelen, A., Bingol, H.: Community detection in complex networks using genetic algorithms. arXiv Prepr. arXiv (2007)

42.

Zadeh, P.M., Kobti, Z.: A multi-population cultural algorithm for community detection in social networks. Procedia Comput. Sci. 52(1), 342–349 (2015)CrossRef

43.

Nicosia, V., Mangioni, G., Carchiolo, V., Malgeri, M.: Extending the definition of modularity to directed graphs with overlapping communities. J. Stat. Mech. Theory Exp. 3, 2009 (2009)MATH

44.

Amelio, A., Pizzuti, C: Overlapping community discovery methods: a survey. In: Social Networks: Analysis and Case Studies. Lecture Notes in Social Networks, pp. 105–125. Weinheim Springer-Verlag (2014)

45.

Xie, J., Kelley, S., Szymanski, B.K.: Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput. Surv. 45(4) (2013)

46.

Pizzuti, C.: Overlapped community detection in complex networks. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO-2009), pp. 859–866 (2009)

47.

Lancichinetti, A., Radicchi, F., Ramasco, J.J., Fortunato, S.: Finding statistically significant communities in networks. PLoS One 6(4) (2011)

48.

Baumes, J., Goldberg M., Krishnamoorthy, M., Magdon-Ismail, M., Preston, N.: Finding communities by clustering a graph into overlapping subgraphs. Int. Conf. Appl. Comput. (IADIS 2005), pp. 97–104, 2005.

49.

Chen, W., Liu, Z., Sun, X., Wang, Y.: A game-theoretic framework to identify overlapping communities in social networks. Data Min. Knowl. Discov. 21(2), 224–240 (2010)MathSciNetCrossRef

50.

Alvari, H., Hashemi, S., Hamzeh, A.: Detecting overlapping communities in social networks by game theory and structural equivalence concept. Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 7003 LNAI, no. PART 2, pp. 620–630 (2011)

51.

Alvari, H., Hajibagheri, A., Sukthankar, G.: Community detection in dynamic social networks: A game-theoretic approach. In: ASONAM 2014—Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 101–107 (2014)

52.

Shi, C., Cai, Y., Fu, D., Dong, Y., Wu, B.: A link clustering based overlapping community detection algorithm. Data Knowl. Eng. 87, 394–404 (2013)CrossRef

53.

Xing, Y., Fanrong, M., Yong, Z., Ranran, Z.: Overlapping community detection by local community expansion. J. Inf. Sci. Eng. 31(4), 1213–1232 (2015)

54.

Bhat, S.Y., Abulais, M.: OCMiner: A density-based overlapping community detection method for social networks. Intell. Data Anal. 19(4), 917–974 (2015)CrossRef

55.

Zhang, H., King, I., Lyu, M.R.: Incorporating implicit link preference into overlapping community detection. Proc. Natl. Conf. Artif. Intell. 1, 396–402 (2015)

56.

Kozdoba, M., Mannor, S.: Overlapping Community Detection by Online Cluster Aggregation. arXiv Prepr. arXiv1504.06798, pp. 1–15 (2015)

57.

Whang, J.J., Gleich, D.F., Dhillon, I.S.: Overlapping community detection using neighborhood-inflated seed expansion. IEEE Trans. Knowl. Data Eng. 28(5), 1272–1284 (2016)CrossRef

58.

Rees, B.S., Gallagher, K.B.: Overlapping community detection by collective friendship group inference. In: Proceedings of the 2010 nternational Conference on Advances in Social Networks Analysis and Mining, ASONAM 2010, pp. 375–379 (2010)

59.

WW Z.: An information flow model for conflict and fission in small groups. J Anthr. Res, vol. 33, pp. 452–473, 1977.

60.

Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.: The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait? Behav. Ecol. Sociobiol. 54(4), 396–405 (2003)CrossRef

61.

Clark, T.D., Davis, A., Gardner, B.B., Gardner, M.R., Warner, W.L.: Deep South: A Social Anthropological Study of Caste and Class. J. South. Hist. 8(3), 439 (1942)CrossRef

62.

Lancichinetti, A., Fortunato, S.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E - Stat. Nonlinear Soft Matter Phys 80(1), 1–8 (2009)

63.

Cao, C., Ni, Q., Zhai, Y.: An improved collaborative filtering recommendation algorithm based on community detection in social networks. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, ACM, pp. 1–8 (2015)

64.

Al-Ayyoub, M., Al-andoli, M., Jararweh, Y., Smadi, M., Gupta, B.: Improving fuzzy C-mean-based community detection in social networks using dynamic parallelism. Comput. Electr. Eng. 74, 533–546 (2019)CrossRef

65.

Chen, X., Xia, C., Wang, J.: A novel trust-based community detection algorithm used in social networks. Chaos, Solitons Fractals 108, 57–65 (2018)MathSciNetCrossRef

66.

Ahajjam, S., El Haddad, M., Badir, H.: A new scalable leader-community detection approach for community detection in social networks. Soc. Netw. 54, 41–49 (2018)CrossRef

67.

Jiang, L., Shi, L., Liu, L., Yao, J., Yousuf, M.A.: User interest community detection on social media using collaborative filtering. Wirel. Netw. 4 (2019)

68.

Kanavos, A., Perikos, I., Hatzilygeroudis, I., Tsakalidis, A.: Emotional community detection in social networks. Comput. Electr. Eng. 65, 449–460 (2018)CrossRef

69.

Zhao, Z., Li, C., Zhang, X., Chiclana, F., Viedma E.H.: An incremental method to detect communities in dynamic evolving social networks. Knowledge-Based Syst. 163(Chao Li), 404–415 (2019)

70.

Zheng, X., Cai, Z., Luo, G., Tian, L., Bai, X.: Privacy-preserved community discovery in online social networks. Futur. Gener. Comput. Syst. 93, 1002–1009 (2019)CrossRef

71.

Singh, P.K., Paprzycki, M.: Introduction on wireless sensor networks ıssues and challenges in current era. In: Singh, P.K., Bhargava, B.K., Paprzycki, M., Kaushal, N.C., Hong, W.C. (eds.) Handbook of Wireless Sensor Networks: Issues and Challenges in Current Scenario’s, Advances in Intelligent Systems and Computing, vol. 1132, pp. 3–12. Springer, Cham, Switzerland (2020)

72.

Meet, K., Reecha, S., Anu, S.: A review on hybrid WSN-NGPON2 network for smart world. In: Singh, P.K., Bhargava, B.K., Paprzycki, M., Kaushal, N.C., Hong, W.C. (eds.) Handbook of Wireless Sensor Networks: Issues and Challenges in Current Scenario’s, Advances in Intelligent Systems and Computing, vol. 1132, pp. 655–671. Springer, Cham, Switzerland (2020)

73.

Chaudhary, L., Singh, B.: Community detection using maximizing modularity and similarity measures in social networks. In: Somani A., Shekhawat R., Mundra A., Srivastava S., Verma V. (eds) Smart Systems and IoT: Innovations in Computing. Smart Innovation, Systems and Technologies, vol. 141, pp. 197–206. Springer (2020)

74.

Fatima, S., Badugu, S.: A study on overlapping community detection for multimedia social network. In: Satapathy, S., Raju, K., Shyamala, K., Krishna, D., Favorskaya, M. (eds.) Advances in Decision Sciences, Image Processing, Security and Computer Vision. Learning and Analytics in Intelligent Systems, vol. 4., pp. 572–578. Springer (2020)

Titel: Defining and Evaluating Network Communities Based on Ground-Truth in Online Social Networks
verfasst von: Sanjeev Dhawan
Kulvinder Singh
Amit Batra
Verlag: Springer Singapore
Buch: Recent Innovations in Computing
Print ISBN: 978-981-15-8296-7

Electronic ISBN: 978-981-15-8297-4

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-981-15-8297-4_13

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"