Generalized Erdős numbers for network analysis

Abstract

The identification of relationships in complex networks is critical in a variety of scientific contexts. This includes the identification of globally central nodes and analysing the importance of pairwise relationships between nodes. In this paper, we consider the concept of topological proximity (or ‘closeness’) between nodes in a weighted network using the generalized Erdős numbers (GENs). This measure satisfies a number of desirable properties for networks with nodes that share a finite resource. These include: (i) real-valuedness, (ii) non-locality and (iii) asymmetry. We show that they can be used to define a personalized measure of the importance of nodes in a network with a natural interpretation that leads to new methods to measure centrality. We show that the square of the leading eigenvector of an importance matrix defined using the GENs is strongly correlated with well-known measures such as PageRank, and define a personalized measure of centrality that is also well correlated with other existing measures. The utility of this measure of topological proximity is demonstrated by showing the asymmetries in both the dynamics of random walks and the mean infection time in epidemic spreading are better predicted by the topological definition of closeness provided by the GENs than they are by other measures.

Keywords

• network science
• centrality
• epidemic spreading