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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Computational Social Networks: Tools, Perspectives, and Challenges Kapitel lesen Erstes Kapitel lesen

2012 | OriginalPaper | Buchkapitel

4. Detection and Interpretation of Communities in Complex Networks: Practical Methods and Application

verfasst von : Vincent Labatut, Jean-Michel Balasque

Erschienen in: Computational Social Networks

Verlag: Springer London

Einloggen

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

search-config
loading …

Abstract

Community detection, an important part of network analysis, has become a very popular field of research. This activity resulted in a profusion of community detection algorithms, all different in some not always clearly defined sense. This makes it very difficult to select an appropriate tool when facing the concrete task of having to identify and interpret groups of nodes, relatively to a system of interest. In this chapter, we tackle this problem in a very practical way, from the user’s point of view. We first review community detection algorithms and characterize them in terms of the nature of the communities they detect. We then focus on the methodological tools one can use to analyze the obtained community structure, both in terms of topological features and nodal attributes. To be as concrete as possible, we use a real-world social network to illustrate the application of the presented tools and give examples of interpretation of their results from a Business Science perspective.

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 Social Network Analysis Techniques for Social-Oriented Mobile Communication Networks
Nächstes Kapitel Metrics and Models for Social Networks
Literatur
1.
da Fontura Costa, L., Oliveira Jr., O.N., Travieso, G., Rodrigues, F.A., Villas Boas, P.R., Antiqueira, L., Viana, M.P., da Rocha, L.E.C.: Analyzing and modeling real-world phenomena with complex networks: a survey of applications. Adv. Phys. 60(3), 329–412 (2011). doi:10.1080/00018732.2011.572452CrossRef
2.
Freeman, L.C.: The Development of Social Network Analysis: A Study in the Sociology of Science. Empirical Press, New York (2004)
3.
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010). doi:DOI 10.1016/j.physrep. 2009.11.002MathSciNetCrossRef
4.
5.
Lancichinetti, A., Kivelä, M., Saramäki, J., Fortunato, S.: Characterizing the community structure of complex networks. PLoS One 5(8), e11976 (2010)CrossRef
6.
Lancichinetti, A., Fortunato, S.: Community detection algorithms: a comparative analysis. Phys. Rev. E 80(5), 056117 (2009)CrossRef
7.
Labatut, V., Balasque, J.-M.: Business-oriented analysis of a social network of University Students. In: Proceeding of the International Conference on Advances in Social Networks Analysis and Mining, Odense, pp. 25–32 (2010)
8.
Porter, M.A., Onnela, J.-P., Mucha, P.J.: Communities in networks. Not. Am. Math. Soc. 56, 1082 (2009)MathSciNetMATH
9.
Danon, L., Duch, J., Arenas, A., Díaz-Guilera, A.: Community structure identification. In: Large Scale Structure and Dynamics of Complex Networks: From Information Technology to Finance and Natural Science, pp. 93–113. World Scientific, Singapore (2007)CrossRef
10.
Reichardt, J., Bornholdt, S.: Statistical mechanics of community detection. Phys. Rev. E 74(1), 016110 (2006)MathSciNetCrossRef
11.
Newman, M.E.J.: Detecting community structure in networks. Eur. Phys. J. B 38(2), 321–330 (2004). http://​www.​springerlink.​com/​content/​5gtdacx17bqv6cdc​/​CrossRef
12.
Mancoridis, S., Mitchell, B.S., Rorres, C., Chen, Y., Gansner, E.R.: Using automatic clustering to produce high-level system organizations of source code. Paper presented at the 6th international workshop on program comprehension, Washington, DC (1998)
13.
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101(9), 2658–2663 (2004). doi:DOI 10.1073/pnas.0400054101CrossRef
14.
Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)CrossRef
15.
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Statistical properties of community structure in large social and information networks. In: Proceeding of the 17th International Conference on World Wide Web, Beijing, pp. 695–704 (2008)
16.
17.
Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006)MathSciNetCrossRef
18.
Lambiotte, R., Delvenne, J.-C., Barahona, M.: Laplacian dynamics and multiscale modular structure in networks. arXiv:0812.1770v3 [physics.soc-ph] (2009)
19.
Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004)CrossRef
20.
Schuetz, P., Caflisch, A.: Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement. Phys. Rev. E 77(4), 046112 (2008)CrossRef
21.
Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. 10, P10008 (2008)CrossRef
22.
Wakita, K., Tsurumi, T.: Finding community structure in mega-scale social networks. arXiv:cs/0702048v1 [cs.CY] (2007)
23.
Guimerà, R., Sales-Pardo, M., Amaral, L.A.N.: Modularity from fluctuations in random graphs and complex networks. Phys. Rev. E 70(2), 025101 (2004)CrossRef
24.
Agarwal, G., Kempe, D.: Modularity-maximizing graph communities via mathematical programming. Eur. Phys. J. B 66(3), 409–418 (2008)MathSciNetMATHCrossRef
25.
Fortunato, S., Barthelemy, M.: Resolution limit in community detection. Proc. Natl. Acad. Sci. USA 104(1), 36–41 (2007)CrossRef
26.
Gleich, D.: Hierarchical Directed Spectral Graph Partitioning. Information Networks, Stanford University (2006)
27.
28.
Leicht, E.A., Newman, M.E.J.: Community structure in directed networks. Phys. Rev. Lett. 100(11), 118703 (2008)CrossRef
29.
Hanneman, R.A., Riddle, M.: Introduction to Social Network Methods. University of California, Riverside (2005). Available at http://​faculty.​ucr.​edu/​~hanneman
30.
Luce, R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2), 169–190 (1950)MathSciNetCrossRef
31.
32.
33.
Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13, 161–173 (1979)CrossRef
34.
Palla, G., Farkas, I.J., Pollner, P., Derenyi, I., Vicsek, T.: Directed network modules. New J. Phys. 9, 186 (2007). doi:Artn 186 Doi 10.1088/1367–2630/9/6/186 Doi 10.1088/1367–2630/9/6/186 Pii S1367–2630(07)44249–5CrossRef
35.
Fouss, F., Pirotte, A., Renders, J.-M., Saerens, M.: Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans. Knowl. Data Eng. 19(3), 355–369 (2007)CrossRef
36.
Gan, G., Ma, C., Wu, J.: Data Clustering: Theory, Algorithms, and Applications. ASA-SIAM Series on Statistics and Applied Probability. Society for Industrial and Applied Mathematics, Philadelphia (2007)MATHCrossRef
37.
Kaufman, L., Rousseeuw, P.J.: Finding Groups in Data: An Introduction to Cluster Analysis. Wiley, New York (1990)CrossRef
38.
Jaccard, P.: Étude comparative de la distribution florale dans une portion des Alpes et des Jura. Bulletin de la Société Vaudoise des Sciences Naturelles 37, 547–579 (1901)
39.
Guimerà, R., Amaral, L.A.N.: Functional cartography of complex metabolic networks. Nature 433, 895–900 (2005)CrossRef
40.
Zhou, H.: Network landscape from a Brownian particle’s perspective. Phys. Rev. E 67(4), 041908 (2003)CrossRef
41.
Saerens, M., Fouss, F., Yen, L., Dupont, P.: The principal component analysis of a graph and its relationships to spectral clustering. In: European Conference on Machine Learning, Pisa, 2004
42.
Pons, P., Latapy, M.: Computing communities in large networks using random walks. Lect. Notes Comput. Sci. 3733, 284–293 (2005)CrossRef
43.
Tong, H., Faloutsos, C., Pan, J.-Y.: Random walk with restart: fast solutions and applications. Knowl. Inf. Syst. 14(3), 327–346 (2008)MATHCrossRef
44.
Handcock, M.S., Raftery, A.E., Tantrum, J.M.: Model-based clustering for social networks. J. Roy. Stat. Soc. A 170, 301–322 (2007)MathSciNetCrossRef
45.
Tyler, R., Wilkinson, D.M., Huberman, B.A.: Email as spectroscopy: automated discovery of community structure within organizations. In: Deventer, B.V. (ed.) Communities and Technologies, pp. 81–96. Kluwer, Dordrecht (2003)
46.
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99(12), 7821–7826 (2002). doi:DOI 10.1073/pnas.1226539799 MathSciNetMATHCrossRef
47.
Wu, F., Huberman, B.A.: Finding communities in linear time: a physics approach. Eur. Phys. J. B 38(2), 331–338 (2004). doi:DOI 10.1140/epjb/e2004-00125-xCrossRef
48.
Castellano, C., Cecconi, F., Loreto, V., Parisi, D., Radicchi, F.: Self-contained algorithms to detect communities in networks. Eur. Phys. J. B 38(2), 311–319 (2004)CrossRef
49.
Rosvall, M., Bergstrom, C.T.: An information-theoretic framework for resolving community structure in complex networks. Proc. Natl. Acad. Sci. USA 104(18), 7327–7331 (2007). doi:DOI 10.1073/pnas.0611034104 CrossRef
50.
Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. USA 105(4), 1118 (2008)CrossRef
51.
52.
van Dongen, S.: Graph clustering via a discrete uncoupling process. SIAM J. Matrix Anal. Appl. 30(1), 121–141 (2008). doi:Doi 10.1137/040608635MathSciNetMATHCrossRef
53.
Hofman, J.M., Wiggins, C.H.: Bayesian approach to network modularity. Phys. Rev. Lett. 100(25), 258701 (2008)CrossRef
54.
Rosvall, M., Bergstrom, C.T.: Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PLoS One 6(4), e18209 (2011). doi:10.1371/journal.pone.0018209
55.
Aldecoa, R., Marin, I.: Jerarca: efficient analysis of complex networks using hierarchical clustering. PLoS One 5(7), e11585 (2010)CrossRef
56.
Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJ. Complex Syst. 1695 (2006). http://​www.​interjournal.​org/​manuscript_​abstract.​php?​361100992
57.
O’Madadhain, J., Fisher, D., Smyth, P., White, S., Boey, Y.-B.: Analysis and visualization of network data using. J. Stat. Softw. 10, 1–35 (2005)
58.
Bastian, M., Heymann, S., Jacomy, M.: Gephi: an open source software for exploring and manipulating networks. Paper presented at the international AAAI conference on weblogs and social media, 2009
59.
Donetti, L., Munoz, M.A.: Improved spectral algorithm for the detection of network communities. arXiv:physics/0504059v1 [physics.soc-ph] (2005)
60.
Palla, G., Derenyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005). doi:Doi 10.1038/Nature03607CrossRef
61.
Rand, W.M.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846–850 (1971)CrossRef
62.
Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2(1), 193–218 (1985)CrossRef
63.
da Fontura Costa, L., Rodrigues, F.A., Travieso, G., Villas Boas, P.R.: Characterization of complex networks: a survey of measurements. Adv. Phys. 56(1), 167–242 (2007)CrossRef
64.
Lancichinetti, A., Radicchi, F., Ramasco, J.J.: Statistical significance of communities in networks. Phys. Rev. E 81(4), 046110 (2010)MathSciNetCrossRef
65.
Decaudin, J.M.: La communication Marketing, Concepts, Techniques, Stratégies. Economica, Paris (2003)
66.
Watts, D.C., Dodds, P.S.: Influentials, networks and public opinion formation. J. Consum. Res. 34, 441–458 (2007)CrossRef
67.
Kotler, P., Keller, K.L.: Marketing Management: Analysis, planning, implementation and control, 12th edn. Prentice Hall International Editions, Upper Saddle River (2006)
68.
69.
Evrard, Y., Pras, B., Roux, E.: MARKET: Etudes et recherches en Marketing. Dunod, Paris (2000)
70.
Norusis, M.: SPSS 17.0 Guide to Data Analysis. Prentice Hall, Inc., Upper Saddle River (2008)
71.
Goodman, L.A., Kruskal, W.H.: Measures of association for cross classification. J. Am. Stat. Assoc. 49, 732–764 (1954)MATH
72.
73.
Bianconi, G., Pin, P., Marsili, M.: Assessing the relevance of node features for network structure. Proc. Natl. Acad. Sci. USA 106(28), 11433–11438 (2009)CrossRef
74.
Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques. Data Management Systems, 2nd edn. Morgan Kaufmann, Amsterdam (2005)MATH
Metadaten
Titel
Detection and Interpretation of Communities in Complex Networks: Practical Methods and Application
verfasst von
Vincent Labatut
Jean-Michel Balasque
Copyright-Jahr
2012
Verlag
Springer London
Buch
Computational Social Networks

Print ISBN: 978-1-4471-4047-4

Electronic ISBN: 978-1-4471-4048-1

Copyright-Jahr: 2012

DOI
https://doi.org/10.1007/978-1-4471-4048-1_4

Premium Partner

    Bildnachweise