We introduce a new centrality measure that characterizes the participation of each node in all subgraphs in a network. Smaller subgraphs are given more weight than larger ones, which makes this measure appropriate for characterizing network motifs. We show that the subgraph centrality [$C_S\left(i\right)$] can be obtained mathematically from the spectra of the adjacency matrix of the network. This measure is better able to discriminate the nodes of a network than alternate measures such as degree, closeness, betweenness, and eigenvector centralities. We study eight real-world networks for which $C_S\left(i\right)$ displays useful and desirable properties, such as clear ranking of nodes and scale-free characteristics. Compared with the number of links per node, the ranking introduced by $C_S\left(i\right)$ (for the nodes in the protein interaction network of S. cereviciae) is more highly correlated with the lethality of individual proteins removed from the proteome.

We propose a new measure of the communicability of a complex network, which is a broad generalization of the concept of the shortest path. According to the new measure, most of the real-world networks display the largest communicability between the most connected (popular) nodes of the network (assortative communicability). There are also several networks with the disassortative communicability, where the most “popular” nodes communicate very poorly to each other. Using this information we classify a diverse set of real-world complex systems into a small number of universality classes based on their structure-dynamic correlation. In addition, the new communicability measure is able to distinguish finer structures of networks, such as communities into which a network is divided. A community is unambiguously defined here as a set of nodes displaying larger communicability among them than to the rest of the nodes in the network.

This book is devoted to the analysis of the structure of complex networks by combining results from algebraic, topological, and extremal graph theory with statistical and molecular physics, as well as with contributions from mathematical chemistry, biology, and social sciences. It is divided into two parts consisting of twelve chapters dedicated to the development of theoretic tools for the structural analysis of networks, and seven chapters illustrating, in a critical way, applications of these tools to real-world scenarios. The first chapters provide detailed coverage of adjacency, metric, and topological properties of networks, followed by chapters devoted to the analysis of fragment-based and global invariants in complex networks. Then, there are chapters that analyse the concepts of communicability, centrality, bipartivity, expansibility, and communities in networks, as well as the study of random networks of different types. The second part of the book starts with an analysis of the study of gene regulation and transcription networks, followed by a chapter dedicated to the study of protein residue networks and another on protein–protein interaction networks. Then, the study of reaction networks is critically presented in three main sections devoted to man-made organic reactions, the chemical reactions in planetary atmospheres, and metabolic networks. This part of the book continues with the study of anatomical networks, which include intercellular, vascular, and brain networks. Another chapter studies the use of complex networks in ecological scenarios by examining not only food webs, but also mutualistic webs and landscape networks. The final chapter of the book is devoted to the study of both social and economic networks.

The emerging field of network science deals with the tasks of modeling, comparing, and summarizing large data sets that describe complex interactions. Because pairwise affinity data can be stored in a two-dimensional array, graph theory and applied linear algebra provide extremely useful tools. Here, we focus on the general concepts of centrality, communicability, and betweenness, each of which quantifies important features in a network. Some recent work in the mathematical physics literature has shown that the exponential of a network's adjacency matrix can be used as the basis for defining and computing specific versions of these measures. We introduce here a general class of measures based on matrix functions, and show that a particular case involving a matrix resolvent arises naturally from graph-theoretic arguments. We also point out connections between these measures and the quantities typically computed when spectral methods are used for data mining tasks such as clustering and ordering. We finish ...