Search Results

The previous chapters looked at different types of natural and man-made networks and techniques for determining their structure, the mathematics used to represent networks formally, and the measures and metrics used to quantify network structure. This chapter combines what have been learned so far, applying theoretical ideas and measures to empirical network data to get a picture of what networks look like in the real world. It shows that there are a number of common recurring patterns seen in network structures, patterns that can have a profound effect on the way networked systems work. Among other things, the chapter discusses component sizes, path lengths and the small-world effect, degree distributions and power laws, and clustering coefficients. Exercises are provided at the end of the chapter.

This chapter looks at the algorithms used to perform network calculations. It starts with some simple algorithms for calculating quantities such as degrees, degree distributions, and clustering before moving on to more sophisticated algorithms for shortest paths, betweenness, maximum flows, and other non-local quantities. Exercises are provided at the end of the chapter.

This chapter introduces the basic characteristics and notions of graph theory and the science of networks: degree, degree distribution, clustering coefficient, the average length of the shortest path between two nodes in a network, the size of a giant connected component, and others. The classical random graphs and their characteristics are introduced and explained. The contrasting types of degree distributions are discussed: namely, Poisson and scale-free distributions.

This chapter discusses the basic mathematics of the random graph G(n, p), focusing particularly on the degree distribution and component sizes, which are two of the model's most illuminating characteristics. The techniques developed in this chapter prove useful for some of the more complex models examined later in the book. Exercises are provided at the end of the chapter.

This chapter describes the measures and metrics that are used to quantify network structure. The chapter starts with a discussion of centrality measures, which are used to identify central or important nodes in networks. Measures discussed include degree centrality, eigenvector centrality, PageRank, closeness, and betweenness. This is followed by a discussion of groupings of nodes like cliques and components, transitivity measures including the clustering coefficient, structural balance in networks, similarity measures, and assortative mixing.

This chapter brings together the ideas and techniques developed in previous chapters, applying them to a range of real-world networks to describe and understand the structure of those networks. Topics discussed include the observed component structure of networks, average path lengths between nodes and the small-world effect, degree distributions including power-law distributions and scale-free networks, clustering and transitivity, and assortative mixing.

In this chapter the basic structural properties of multilayer networks are given. This chapter reveals that on multilayer networks the most basic structural properties of a network such as the degree or the clustering coefficient are also significantly modified. Therefore, it is necessary to define the multiplex degree and the multiplex degree distribution, the multilayer degree and the multilayer degree distribution, and the multilayer clustering coefficients. The chapter also discusses the relation between the properties of multiplex and multi-slice networks and the corresponding properties of their aggregated network. Finally, the chapter introduces multilayer distance-dependent measures, including generalization of the betweenness centrality (interdependence, cross-betweenness) and of the closeness centrality.

A discussion of the most fundamental of network models, the configuration model, which is a random graph model of a network with a specified degree sequence. Following a definition of the model a number of basic properties are derived, including the probability of an edge, the expected number of multiedges, the excess degree distribution, the friendship paradox, and the clustering coefficient. This is followed by derivations of some more advanced properties including the condition for the existence of a giant component, the size of the giant component, the average size of a small component, and the expected diameter. Generating function methods for network models are also introduced and used to perform some more advanced calculations, such as the calculation of the distribution of the number of second neighbors of a node and the complete distribution of sizes of small components. The chapter ends with a brief discussion of extensions of the configuration model to directed networks, bipartite networks, networks with degree correlations, networks with high clustering, and networks with community structure, among other possibilities.

An introduction to the mathematics of the Poisson random graph, the simplest model of a random network. The chapter starts with a definition of the model, followed by derivations of basic properties like the mean degree, degree distribution, and clustering coefficient. This is followed with a detailed derivation of the large-scale structural properties of random graphs, including the position of the phase transition at which a giant component appears, the size of the giant component, the average size of the small components, and the expected diameter of the network. The chapter ends with a discussion of some of the shortcomings of the random graph model.

At the present time, the most commonly accepted definition of a complex system is that of a system containing many interdependent constituents which interact nonlinearly. Therefore, when we want to model a complex system, the first issue has to do with the connectivity properties of its network, the architecture of the wirings between the constituents. In fact, we have recently learned that the network structure can be as important as the nonlinear interactions between elements, and an accurate description of the coupling architecture and a characterization of the structural properties of the network can be of fundamental importance also in understanding the dynamics of the system. In the last few years the research on networks has taken different directions producing rather unexpected and important results. Researchers have: (1) proposed various global variables to describe and characterize the properties of realworld networks and (2) developed different models to simulate the formation and the growth of networks such as the ones found in the real world. The results obtained can be summed up by saying that statistical physics has been able to capture the structure of many diverse systems within a few common frameworks, though these common frameworks are very different from the regular array, or capture the random connectivity, previously used to model the network of a complex system. Here we present a list of some of the global quantities introduced to characterize a network: the characteristic path length L, the clustering coefficient C, the global efficiency E_glob, the local efficiency E_loc, the cost Cost, and the degree distribution P(k). We also review two classes of networks proposed: smallworld and scale-free networks. We conclude with a possible application of the nonextensive thermodynamics formalism to describe scale-free networks. Watts and Strogatz [17] have shown that the connection topology of some biological, social, and technological networks is neither completely regular nor completely random. These networks, that are somehow in between regular and random networks, have been named small worlds in analogy with the smallworld phenomenon empirically observed in social systems more than 30 years ago [11, 12].