Top

Published in:

2019 | OriginalPaper | Chapter

2. Fundamentals of Complex Network Analysis

Authors : Miloš Savić, Mirjana Ivanović, Lakhmi C. Jain

Published in: Complex Networks in Software, Knowledge, and Social Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Complex network analysis is a collection of quantitative methods for studying the structure and dynamics of complex networked systems. This chapter presents the fundamentals of complex network analysis. We start out by presenting the basic concepts of complex networks and graph theory. Then, we focus on fundamental network analysis measures and algorithms related to node connectivity, distance, centrality, similarity and clustering. Finally, we discuss fundamental complex network models and their characteristics.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Introduction to Complex Networks

next chapter Analysis of Software Networks

Abbe, E.: Community detection and stochastic block models: recent developments (2017). arXiv:1703.10146

Adamic, L.A., Adar, E.: Friends and neighbors on the web. Soc. Netw. 25(3), 211–230 (2003). https://doi.org/10.1016/S0378-8733(03)00009-1CrossRef

Alba, R.D.: A graph theoretic definition of a sociometric clique. J Math Sociol. 3(1), 113–126 (1973). https://doi.org/10.1080/0022250X.1973.9989826MathSciNetCrossRefMATH

Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47–97 (2002). https://doi.org/10.1103/RevModPhys.74.47MathSciNetCrossRefMATH

Alvarez-Hamelin, J.I., Dall’Asta, L., Barrat, A., Vespignani, A.: K-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. Netw. Heterog. Media 3(2), 371–393 (2008). https://doi.org/10.3934/nhm.2008.3.371MathSciNetCrossRefMATH

Amaral, L.A.N., Scala, A., Barthlmy, M., Stanley, H.E.: Classes of small-world networks. Proc. Natl. Acad. Sci. 97(21), 11149–11152 (2000). https://doi.org/10.1073/pnas.200327197CrossRef

Barabasi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999). https://doi.org/10.1126/science.286.5439.509MathSciNetCrossRefMATH

Batagelj, V., Zaveršnik, M.: Fast algorithms for determining (generalized) core groups in social networks. Adv. Data Anal. Classif. 5(2), 129–145 (2011). https://doi.org/10.1007/s11634-010-0079-yMathSciNetCrossRefMATH

Bavelas, A.: Communication patterns in task-oriented groups. J. Acoust. Soc. Am. 22(6), 725–730 (1950). https://doi.org/10.1121/1.1906679CrossRef

10.

Beauchamp, M.A.: An improved index of centrality. Behav. Sci. 10(2), 161–163 (1965). https://doi.org/10.1002/bs.3830100205CrossRef

11.

Bender, E.A., Canfield, E.: The asymptotic number of labeled graphs with given degree sequences. J Comb. Theory Ser. A 24(3), 296–307 (1978). https://doi.org/10.1016/0097-3165(78)90059-6MathSciNetCrossRefMATH

12.

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

13.

Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.: Complex networks: structure and dynamics. Phys. Rep. 424(45), 175–308 (2006). https://doi.org/10.1016/j.physrep.2005.10.009MathSciNetCrossRefMATH

14.

Boldi, P., Vigna, S.: Axioms for centrality. Internet Math. 10(3–4), 222–262 (2014). https://doi.org/10.1080/15427951.2013.865686MathSciNetCrossRef

15.

Boldi, P., Rosa, M., Vigna, S.: Robustness of social and web graphs to node removal. Soc. Netw. Anal. Min. 3(4), 829–842 (2013). https://doi.org/10.1007/s13278-013-0096-xCrossRef

16.

Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Directed scale-free graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, Society for Industrial and Applied Mathematics. pp. 132–139, Philadelphia, PA, USA (2003). https://doi.org/10.1145/644108.644133

17.

Bollobás, B., Riordan, O.M.: Mathematical results on scale-free random graphs, pp. 1–34. Wiley-VCH Verlag GmbH & Co. KGaA (2005). https://doi.org/10.1002/3527602755.ch1

18.

Bollobás, B.: Random Graphs. Cambridge University Press (2001)

19.

Bonacich, P.: Factoring and weighting approaches to status scores and clique identification. J. Math. Sociol. 2(1), 113–120 (1972). https://doi.org/10.1080/0022250X.1972.9989806CrossRef

20.

Bonacich, P.: Power and centrality: a family of measures. Am. J. Sociol. 92(5), 1170–1182 (1987). https://doi.org/10.2307/2780000CrossRef

21.

Borgatti, S.P., Everett, M.G.: Models of core/periphery structures. Soc. Netw. 21(4), 375–395 (2000). https://doi.org/10.1016/S0378-8733(99)00019-2CrossRef

22.

Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163–177 (2001). https://doi.org/10.1080/0022250X.2001.9990249CrossRefMATH

23.

Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Soc. Netw. 30(2), 136–145 (2008). https://doi.org/10.1016/j.socnet.2007.11.001CrossRef

24.

Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., Wagner, D.: On modularity clustering. IEEE Trans. Knowl. Data Eng 20(2), 172–188 (2008). https://doi.org/10.1109/TKDE.2007.190689CrossRefMATH

25.

Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Comput. Netw. ISDN Syst 30(1–7), 107–117 (1998)CrossRef

26.

Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973). https://doi.org/10.1145/362342.362367CrossRefMATH

27.

Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004). https://doi.org/10.1103/PhysRevE.70.066111

28.

Clauset, A., Shalizi, C., Newman, M.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009). https://doi.org/10.1137/070710111MathSciNetCrossRefMATH

29.

Costa,.LdF, Oliveira, O., Travieso, G., Rodrigues, F.A., Villas Boas, P., Antiqueira, L., Viana, M.P., Correa Rocha, L.: Analyzing and modeling real-world phenomena with complex networks: a survey of applications. Adv. Phys. 60(3), 329–412 (2011). https://doi.org/10.1080/00018732.2011.572452CrossRef

30.

Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1(1), 269–271 (1959). https://doi.org/10.1007/BF01386390MathSciNetCrossRefMATH

31.

Dongen, S.V.: Graph clustering via a discrete uncoupling process. SIAM J. Matrix Anal. Appl. 30(1), 121–141 (2008). https://doi.org/10.1137/040608635MathSciNetCrossRefMATH

32.

Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N.: Structure of growing networks with preferential linking. Phys. Rev. Lett. 85, 4633–4636 (2000). https://doi.org/10.1103/PhysRevLett.85.4633CrossRef

33.

Eppstein, D., Strash, D.: Listing all maximal cliques in large sparse real-world graphs, pp. 364–375. Springer, Berlin (2011). https://doi.org/10.1007/978-3-642-20662-7_31CrossRef

34.

Erdős, P., Rényi, A.: On random graphs. I. Publ. Math. Debr. 6, 290–297 (1959)MATH

35.

Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61 (1960)MathSciNetMATH

36.

Flake, G.W., Lawrence, S., Giles, C.L., Coetzee, F.M.: Self-organization and identification of web communities. Computer 35(3), 66–71 (2002). https://doi.org/10.1109/2.989932CrossRef

37.

Fortunato, S., Latora, V., Marchiori, M.: Method to find community structures based on information centrality. Phys. Rev. E 70, 056104 (2004). https://doi.org/10.1103/PhysRevE.70.056104

38.

Fortunato, S.: Community detection in graphs. Phys. Rep. 486(35), 75–174 (2010). https://doi.org/10.1016/j.physrep.2009.11.002MathSciNetCrossRef

39.

Fortunato, S., Barthlemy, M.: Resolution limit in community detection. Proc. Natl. Acad. Sci. 104(1), 36–41 (2007). https://doi.org/10.1073/pnas.0605965104CrossRef

40.

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

41.

Freeman, L.C., Borgatti, S.P., White, D.R.: Centrality in valued graphs: a measure of betweenness based on network flow. Soc. Netw. 13(2), 141–154 (1991). https://doi.org/10.1016/0378-8733(91)90017-NMathSciNetCrossRef

42.

Garlaschelli, D., Loffredo, M.: Patterns of link reciprocity in directed networks. Phys. Rev. Lett. 93, 268701 (2004). https://doi.org/10.1103/PhysRevLett.93.268701

43.

Gilbert, E.N.: Random graphs. Ann. Math. Stat. 30(4), 1141–1144 (1959)CrossRef

44.

Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002). https://doi.org/10.1073/pnas.122653799MathSciNetCrossRefMATH

45.

Goldstein, M.L., Morris, S.A., Yen, G.G.: Problems with fitting to the power-law distribution. Eur. Phys. J. B - Condens. Matter Complex Syst. 41(2), 255–258 (2004). https://doi.org/10.1140/epjb/e2004-00316-5CrossRef

46.

Good, B.H., de Montjoye, Y.A., Clauset, A.: Performance of modularity maximization in practical contexts. Phys. Rev. E 81, 046106 (2010). https://doi.org/10.1103/PhysRevE.81.046106

47.

Guo, Q., Zhou, T., Liu, J.G., Bai, W.J., Wang, B.H., Zhao, M.: Growing scale-free small-world networks with tunable assortative coefficient. Phys. A Stat. Mech. Appl. 371(2), 814–822 (2006). https://doi.org/10.1016/j.physa.2006.03.055CrossRef

48.

Hasan, M.A., Zaki, M.J.: A survey of link prediction in social networks, pp. 243–275. Springer, Boston (2011). https://doi.org/10.1007/978-1-4419-8462-3_9CrossRef

49.

Holland, P.W., Laskey, K.B., Leinhardt, S.: Stochastic blockmodels: first steps. Soc. Netw. 5(2), 109–137 (1983). https://doi.org/10.1016/0378-8733(83)90021-7MathSciNetCrossRef

50.

Holme, P., Kim, B.J., Yoon, C.N., Han, S.K.: Attack vulnerability of complex networks. Phys. Rev. E 65, 056109 (2002). https://doi.org/10.1103/PhysRevE.65.056109

51.

Holme, P., Kim, B.J.: Growing scale-free networks with tunable clustering. Phys. Rev. E 65, 026107 (2002). https://doi.org/10.1103/PhysRevE.65.026107

52.

Jeh, G., Widom, J.: Simrank: A measure of structural-context similarity. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’02. pp. 538–543, ACM, New York, USA (2002). https://doi.org/10.1145/775047.775126

53.

Khaouid, W., Barsky, M., Srinivasan, V., Thomo, A.: K-core decomposition of large networks on a single PC. Proc. VLDB Endow. 9(1), 13–23 (2015). https://doi.org/10.14778/2850469.2850471CrossRef

54.

Kleinberg, J.M., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: The web as a graph: measurements, models, and methods. In: Asano, T., Imai, H., Lee, D., Nakano, S.i., Tokuyama, T. (eds.) Computing and Combinatorics. Lecture Notes in Computer Science, vol. 1627, pp. 1–17

55.

Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. J. ACM 46(5), 604–632 (1999). https://doi.org/10.1145/324133.324140MathSciNetCrossRefMATH

56.

Krapivsky, P.L., Redner, S.: Network growth by copying. Phys. Rev. E 71, 036118 (2005). https://doi.org/10.1103/PhysRevE.71.036118

57.

Krapivsky, P.L., Redner, S., Leyvraz, F.: Connectivity of growing random networks. Phys. Rev. Lett. 85, 4629–4632 (2000). https://doi.org/10.1103/PhysRevLett.85.4629CrossRef

58.

Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the Web graph. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS ’00, IEEE Computer Society. pp. 57–65, Washington, USA (2000). https://doi.org/10.1109/SFCS.2000.892065

59.

Leicht, E.A., Newman, M.E.J.: Community structure in directed networks. Phys. Rev. Lett. 100, 118703 (2008). https://doi.org/10.1103/PhysRevLett.100.118703

60.

Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1(1) (2007). https://doi.org/10.1145/1217299.1217301CrossRef

61.

Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009). https://doi.org/10.1080/15427951.2009.10129177MathSciNetCrossRefMATH

62.

Li, C., Maini, P.K.: An evolving network model with community structure. J. Phys. A Math. Gen. 38(45), 9741 (2005). https://doi.org/10.1088/0305-4470/38/45/002MathSciNetCrossRefMATH

63.

Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM ’03. pp. 556–559, ACM, New York, USA (2003). https://doi.org/10.1145/956863.956972

64.

Lichtenwalter, R.N., Lussier, J.T., Chawla, N.V.: New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10. pp. 243–252, ACM, New York, USA, (2010). https://doi.org/10.1145/1835804.1835837

65.

Lü, L., Zhou, T.: Link prediction in complex networks: a survey. Phys. A Stat. Mech. Appl. 390(6), 1150–1170 (2011). https://doi.org/10.1016/j.physa.2010.11.027CrossRef

66.

Martínez, V., Berzal, F., Cubero, J.C.: A survey of link prediction in complex networks. ACM Comput. Surv. 49(4), 69:1–69:33 (2016). https://doi.org/10.1145/3012704CrossRef

67.

Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13(2), 161–173 (1979). https://doi.org/10.1007/BF00139635CrossRef

68.

Nepusz, T., Petróczi, A., Négyessy, L., Bazsó, F.: Fuzzy communities and the concept of bridgeness in complex networks. Phys. Rev. E 77, 016,107 (2008). https://doi.org/10.1103/PhysRevE.77.016107

69.

Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004). https://doi.org/10.1103/PhysRevE.69.026113

70.

Newman, M.E.J.: Analysis of weighted networks. Phys. Rev. E 70, 056131 (2004). https://doi.org/10.1103/PhysRevE.70.056131

71.

Newman, M.E.J.: Assortative mixing in networks. Phys. Rev. Lett. 89, 208701 (2002). https://doi.org/10.1103/PhysRevLett.89.208701

72.

Newman, M.E.J.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 066133 (2004). https://doi.org/10.1103/PhysRevE.69.066133

73.

Newman, M.E.J.: Mixing patterns in networks. Phys. Rev. E 67, 026126 (2003). https://doi.org/10.1103/PhysRevE.67.026126

74.

Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45, 167–256 (2003). https://doi.org/10.1137/S003614450342480MathSciNetCrossRefMATH

75.

Newman, M.E.J.: Power laws, pareto distributions and Zipf’s law. Contemp. Phys. 46(5), 323–351 (2005). https://doi.org/10.1080/00107510500052444CrossRef

76.

Newman, M.: Networks: An Introduction. Oxford University Press Inc, New York (2010)CrossRef

77.

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

78.

Pastor-Satorras, R., Vázquez, A., Vespignani, A.: Dynamical and correlation properties of the internet. Phys. Rev. Lett. 87, 258701 (2001). https://doi.org/10.1103/PhysRevLett.87.258701

79.

Perra, N., Fortunato, S.: Spectral centrality measures in complex networks. Phys. Rev. E 78, 036107 (2008). https://doi.org/10.1103/PhysRevE.78.036107

80.

Pollner, P., Palla, G., Vicsek, T.: Preferential attachment of communities: the same principle, but a higher level. EPL (Europhys. Lett.) 73(3), 478 (2006). https://doi.org/10.1209/epl/i2005-10414-6MathSciNetCrossRef

81.

Pons, P., Latapy, M.: Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10(2), 191–218 (2006). https://doi.org/10.7155/jgaa.00124MathSciNetCrossRefMATH

82.

Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and identifying communities in networks. Proc. Natl. Acad. Sci. 101(9), 2658–2663 (2004). https://doi.org/10.1073/pnas.0400054101CrossRef

83.

Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 036106 (2007). https://doi.org/10.1103/PhysRevE.76.036106

84.

Rombach, M.P., Porter, M.A., Fowler, J.H., Mucha, P.J.: Core-periphery structure in networks. SIAM J. Appl. Math. 74(1), 167–190 (2014). https://doi.org/10.1137/120881683MathSciNetCrossRefMATH

85.

Rosvall, M., Bergstrom, C.T.: Maps of information flow reveal community structure in complex networks. Proc. Natl. Acad. Sci. U.S.A. 105, 1118–1123 (2007). https://doi.org/10.1073/pnas.0706851105CrossRef

86.

Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269–287 (1983). https://doi.org/10.1016/0378-8733(83)90028-XMathSciNetCrossRef

87.

Seidman, S.B., Foster, B.L.: A graphtheoretic generalization of the clique concept. J. Math. Sociol. 6(1), 139–154 (1978). https://doi.org/10.1080/0022250X.1978.9989883MathSciNetCrossRefMATH

88.

Shen, H., Cheng, X., Cai, K., Hu, M.B.: Detect overlapping and hierarchical community structure in networks. Phys. A Stat. Mech. Appl. 388(8), 1706–1712 (2009). https://doi.org/10.1016/j.physa.2008.12.021CrossRef

89.

Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972). https://doi.org/10.1137/0201010MathSciNetCrossRefMATH

90.

Watts, D.J., Strogatz, S.H.: Collective dynamics of’small-world’networks. Nature 393(6684), 409–10 (1998). https://doi.org/10.1038/30918CrossRef

91.

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), 43:1–43:35 (2013). https://doi.org/10.1145/2501654.2501657CrossRef

Title: Fundamentals of Complex Network Analysis
Authors: Miloš Savić
Mirjana Ivanović
Lakhmi C. Jain
Publisher: Springer International Publishing
Book: Complex Networks in Software, Knowledge, and Social Systems
Print ISBN: 978-3-319-91194-6

Electronic ISBN: 978-3-319-91196-0

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-319-91196-0_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner