Subgraph centrality in complex networks

Abstract

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.