nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

5. Metrics and Models for Social Networks

verfasst von : Nicolás Ignacio Bersano-Méndez, Satu Elisa Schaeffer, Javier Bustos-Jiménez

Erschienen in: Computational Social Networks

Verlag: Springer London

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Social networks can be modeled and analyzed in terms of graph theory. This chapter provides an overview of the mathematical modeling of social networks with an overview of the metrics used to characterize them and the models used to artificially mimic the formation of such networks. We discuss metrics based on distances, degrees, and neighborhoods as well as the use of such metrics to detect change in the network structure. We also discuss the kind of structural differences that distinguish social networks from other types of natural networks together with the implications of these differences about the way in which these networks function.

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 Detection and Interpretation of Communities in Complex Networks: Practical Methods and Application

Nächstes Kapitel Structural Decompositions of Complex Networks

Another possible visualization (cf. [19]) is using a line that is thicker at the source and gradually becomes thinner before reaching the target vertex.

In general graph theory, also edges from a vertex to itself (called loops or reflexive edges) are of interest, but these are not usually present in graphs that represent social networks.

Whereas the number of vertices is called the order of the graph, the number of edges is often called its size.

The binomial coefficient is \(\left ({ n \atop k} \right ) = \frac{n!} {k!(n-k)!}\), where k! = 1 ⋅2 ⋅…(n − 1) ⋅n is the factorial.

A complete graph is one where all vertices are neighbors among themselves, that is, all possible edges are present.

A vertex set S ⊆ V is an independent set in G = (V, E) if none of its member vertices are adjacent in E.

A queue is a data structure where incoming data is appended at the end and removals are only done in the beginning of the structure.

Anghel, M., Toroczkai, Z., Bassler, K.E., Korniss, G.: Competition-driven network dynamics: emergence of a scale-free leadership structure and collective efficiency. Phys. Rev. Lett. 92, 058701 (2004)CrossRef

Arenas, A., Díaz-Guilera, A., Kurths, J., Moreno, Y., Zhou, C.: Synchronization in complex networks. Phys. Rep. 469, 93–153 (2008)

Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)MathSciNetCrossRef

Bollobás, B., Riordan, O.: Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks, pp. 1–34. Wiley, Weinheim (2005)

Bu, T., Towsley, D.: On distinguishing between internet power law topology generators. In: IEEE Infocom: The 21st Annual Joint Conference of the IEEE Computer and Communications Societies in New York, NY, USA. IEEE Computer Society, Los Alamitos (2002)

Bustos, J., Bersano, N., Schaeffer, S., Piquer, J., Iosup, A., Ciuffoletti, A.: Estimating the size of peer-to-peer networks using lamberts’s w function. In: Golatch, S., Fragopoulou, P., Priol, T. (eds.) Grid Computing – Achievements and Prospects, pp. 61–72. Springer, New York (2008)

Catanzaro, M., Caldarelli, G., Pietronero, L.: Assortative model for social networks. Phys. Rev. E 70(3), 037101 (2004)CrossRef

Dell’Amico, M., Roudier, Y.: A measurement of mixing time in social networks. In: Proceedings of the Fifth International Workshop on Security and Trust Management, Saint Malo (2009)

Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)

10.

Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of networks. Adv. Phys. 51(4), 1079–1187 (2002)CrossRef

11.

Du, H., Feldman, M.W., Li, S., Jin, X.: An algorithm for detecting community structure of social networks based on prior knowledge and modularity. Complexity 12(3), 53–60 (2007)MathSciNetCrossRef

12.

Eguíluz, V.M., Zimmermann, M., Cela-Conde, C., San Miguel, M.: Cooperation and the emergence of role differentiation in the dynamics of social networks. Am. J. Sociol. 110, 977–1008 (2005)

13.

Eubank, S., Vullikanti, A., Khan, M., Marathe, M., Barrett, C.: Beyond degree distributions: local to global structure of social contact graphs. In: Advances in Social Computing. Lecture Notes in Computer Science, vol. 6007 (2010)

14.

Franks, D.W., Noble, J., Kaufmann, P., Stagl, S.: Extremism propagation in social networks with hubs. Adapt. Behav. 16(4), 264–274 (2008)CrossRef

15.

Freeman, L.C.: A set of measures of centrality based upon betweenness. Sociometry 40(1), 35–41 (1977)CrossRef

16.

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

17.

Gjoka, M., Kurant, M., Butts, C.T., Markopoulou, A.: Walking in facebook: a case study of unbiased sampling of osns. In: Proceedins of the IEEE INFOCOM, p. 9. IEEE (2010)

18.

Goldenberg, A., Zheng, A.X., Fienberg, S.E., Airoldi, E.M.: A survey of statistical network models. Found. Trends Mach. Learn. 2(2), 117 (2009)

19.

Holten, D., van Wijk, J.J.: A user study on visualizing directed edges in graphs. In: Proceedings of the 27th International Conference on Human Factors in Computing Systems, pp. 2299–2308. ACM, New York (2009)

20.

Kim, H.J., Kim, J.M.: Cyclic topology in complex network. Phys. Rev. E 72(3), 036109 (2005)CrossRef

21.

Latora, V., Marchiori, M.: Efficient behavior of small-world networks. Phys. Rev. Lett. 87(19), 198701 (2001)CrossRef

22.

Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 251–262. ACM, New York (2005)

23.

Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Statistical properties of community structure in large social and information networks. In: Proceedings of the 17th International Conference on World Wide Web. ACM, New York (2008)

24.

Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanley, H.E., Aberg, Y.: The web of human sexual contacts. Nature 411, 907–908 (2001)CrossRef

25.

Mohaisen, A., Yun, A., Kim, Y.: Measuring the mixing time of social graphs. In: Proceedings of the 10th Annual Conference on Internet Measurement, pp. 383–389. ACM, New York (2010)

26.

Moore, C., Newman, M.E.J.: Epidemics and percolation in small-world networks. Phys. Rev. E 61(5), 5678–5682 (2000)CrossRef

27.

Newman, M.E.J.: Scientific collaboration networks: I. Network construction and fundamental results. Phys. Rev. E 64(1), 016131 (2001)

28.

Newman, M.E.: Assortative mixing in networks. Phys. Rev. Lett. 89, 208701 (2002)CrossRef

29.

Newman, M.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)MathSciNetMATHCrossRef

30.

Newman, M.E.J.: Detecting community structure in networks. Eur. Phys. J. B 38(2), 321–330 (2004)CrossRef

31.

Newman, M.E.J., Girvan, M.: Mixing patterns and community structure in networks. In: Pastor-Satorras, R., Rubi, M., Diaz-Guilera, A. (eds.) Statistical Mechanics of Complex Networks, Lecture Notes in Physics, vol. 625, pp. 66–87. Springer, Berlin (2003)CrossRef

32.

Newman, M., Strogatz, S., Watts, D.: Random graph models of social networks. Proc. Natl. Acad. Sci. USA 99, 2566–2572 (2002)MATHCrossRef

33.

Rong, Z., Yang, H.X., Wang, W.X.: Effect of clustering coefficient on cooperation in scale-free public goods game. In: Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pp. 405–408. IEEE (2010)

34.

Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007)MathSciNetCrossRef

35.

Schank, T.: Algorithmic aspects of triangle-based network analysis. Ph.D. thesis, Universität Fridericiana zu Karlsruhe (2007)

36.

Shannon, C.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423/ 623–656 (1948)

37.

Stephen, A.T., Toubia, O.: Explaining the power-law degree distribution in a social commerce network. Soc. Netw. 31(4), 262–270 (2009)CrossRef

38.

Toivonen, R., Onnela, J.P., Saramäki, J., Hyvönen, J., Kaski, K.: A model for social networks. Physica A 371, 851–860 (2006)CrossRef

39.

Virtanen, S.E.: Properties of nonuniform random graph models. In: Research Report A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo (2003)

40.

Vullikanti, A., Eubank, S., Kumar, V.A., Marathe, M., Srinivasan, A., Wang, N.: Structure of social contact networks, and their impact on epidemics. In: AMS-DIMACS Special Issue on Epidemiology, pp. 181–213. AMS (2006)

41.

Wang, B., Tang, H., Guo, C., Xiu, Z.: Entropy optimization of scale-free networks robustness to random failures. Physica A 363(2), 591–596 (2006)CrossRef

42.

Watts, D.J.: Small Worlds. Princeton University Press, Princeton (1999)

43.

Watts, D., Strogatz, S.: Collective dynamics of ’small world’ networks. Nature 393, 440–442 (1998)CrossRef

44.

White, D.R., Houseman, M.: The navigability of strong ties: small worlds, tie strength, and network topology. Complexity 8(1), 72–81 (2002)CrossRef

45.

Wu, Y., Yang, Y., Wu, H., Wang, G.: Modeling and simulation on information propagation on instant messaging network based on two-layer scale-free networks with tunable clustering. In: IEEE International Conference on Systems, Man and Cybernetics, San Antonio, pp. 5184–5188 (2009)

46.

Wua, X., Liu, Z.: How community structure influences epidemic spread in social networks. Phys. A 387(2–3), 623–630 (2008)

47.

Zhou, S., Cox, I., Hansen, L.K.: Second-order assortative mixing in social networks. Techical Report 0903.0687, arXiv.org (2009)

Titel: Metrics and Models for Social Networks
verfasst von: Nicolás Ignacio Bersano-Méndez
Satu Elisa Schaeffer
Javier Bustos-Jiménez
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_5

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"

Premium Partner