USING SPECTRAL RADIUS RATIO FOR NODE DEGREE
TO ANALYZE THE EVOLUTION OF COMPLEX NETWORKS
Natarajan Meghanathan
Jackson State University, 1400 Lynch St, Jackson, MS, USA
ABSTRACT
In this paper, we show that the spectral radius ratio for node degree could be used to analyze the variation of node degree during the evolution of complex networks. We focus on three commonly studied models of complex networks: random networks, scale-free networks and small-world networks. The spectral radius ratio for node degree is defined as the ratio of the principal (largest) eigenvalue of the adjacency matrix of a network graph to that of the average node degree. During the evolution of each of the above three categories of networks (using the appropriate evolution model for each category), we observe the spectral radius ratio for node degree to exhibit high-very high positive correlation (0.75 or above) to that of the
coefficient of variation of node degree (ratio of the standard deviation of node degree and average node degree). We show that the spectral radius ratio for node degree could be used as the basis to tune the operating parameters of the evolution models for each of the three categories of complex networks as well as analyze the impact of specific operating parameters for each model.
KEYWORDS
Eigenvalue, Spectral radius, Random network, Scale-free network, Small-world network, Node degree
1.INTRODUCTION
Network analysis and visualization of large complex real-world networks, ranging anywhere from social networks [1][2], co-authorship networks [3], Internet [4], World wide web [4] to biological networks [5] and etc is an actively researched area in recent years. The strength of network analysis is to abstract the complex relationships between the members of the system in the form of a graph with nodes (comprising of the constituent members) and edges (weighted or unitweight as well as directed or undirected, depending on the nature of the interactions) and study the characteristics of the graph with respect to one or more metrics (like node degree, diameter, clustering coefficient and etc). The adjacency matrix A(G) of the network graph G essentially captures the presence of edges between any two vertices. For any two vertices i and j in graph G, the entry in the ith row and jth column of A(G) is 1 if there is an edge from vertex i to vertex j and 0 otherwise. This paper focuses on undirected graphs (edge i-j exists in both the directions: i–>j as well as from j–>i) and node degree as the metric under study. Spectral decomposition is a method of projecting the characteristics of a network graph in ndimensions
or directions (that are mutually perpendicular) where n is the number of vertices in the graph. The projection in each direction is represented in the form of a scalar value (called the eigenvalue) and its corresponding vector with entries for each vertex (called the eigenvector). Though the number of dimensions in the spectrum is the number of vertices in the graph, most of the variations could be captured in the first few dimensions of the coordinate system represented by the eigenvalues and the eigenvectors. The largest eigenvalue of the projection is called the principal eigenvalue and the corresponding eigenvector is called the principal eigenvector (could be determined by executing the power iteration algorithm [6] on the adjacency matrix of a network graph). The principal eigenvalue and its corresponding eigenvector capture maximum amount of variability in the data (in the case of a network graph, the data are the edges connecting the vertices). In this paper, we make use of the principal eigenvalue (also called the spectral radius) of the adjacency matrix of complex network graphs to analyze the variations in node degree and correlate with the coefficient of variation of node degree. We specifically use the spectral radius ratio for node degree as the basis to evaluate the evolution of three commonly studied complex network models, such as the random networks, scale-free networks and smallworld networks. To the best of our knowledge, we could not come across any related work that uses spectral radius as the basis to comprehensively analyze the evolution of all the above three categories of complex networks.
The rest of the paper is organized as follows: In Section 2, we introduce the power iteration method that was used in this research to calculate the spectral radius of a network graph. Sections 3, 4 and 5 validate our hypothesis on random networks, scale-free networks and small-world networks respectively. Section 6 concludes the paper.
2. POWER ITERATION METHOD TO CALCULATE SPECTRAL RADIUS
The power iteration method can be used to calculate the principal eigenvalue (i.e., spectral radius) and the corresponding principal eigenvector of a graph based on its adjacency matrix. The eigenvector Xi+1 of a network graph at the end of the (i+1)th iteration is given by: Xi+1 = AXi / ||AXi||, where ||AXi|| is the normalized value of the product of the adjacency matrix A of a given graph and the tentative eigenvector Xi at the end of iteration i. The initial value of Xi is [1, 1, …, 1], a column vector of all 1s, where the number of 1s correspond to the number of vertices in the graph. We continue the iterations until the normalized value ||AXi+1|| converges to that of the normalized value ||AXi||. The value of the column vector Xi at this juncture is declared the principal eigenvector of the network graph and the normalized value to which the iterations converge is the principal eigenvalue (i.e., the spectral radius). Figure 1 illustrates an example for computation of the spectral radius on a network graph. The converged normalized value of 2.21 is the spectral radius of the graph (denoted sp(G)). If kmin, kavg and kmax are the minimum, average and maximum node degrees, then, kmin kavg sp(G) kmax [7].
Figure 1: Example to illustrate the execution of the power iteration method to compute the spectral radius of a network graph
3. SIMULATION AND ANALYSIS OF RANDOM NETWORKS
A random network is a network wherein all the nodes have comparative degree and no single node has a degree that is significantly different from that of the other nodes. Ideally, for a random network, the standard deviation of the node degree should be 0; however, this is possible only if all nodes have the same degree. In real-world random networks and the random networks generated by evolutionary models (using simulations), the degrees of all the nodes lie close to the average degree of the nodes and the variation in the node degree is appreciably low. In this section, we discuss the well-known Erdos-Renoyi model [11] and its simulation to study the variation of node degrees during the evolution of random networks.
Initially, all the nodes in the network are uniform-randomly distributed; there could be links between any two nodes. Thus, if there are N nodes in the network, the maximum number of links in the network could be N(N-1)/2 and we store the set of all possible links in a set called the CandidateLinks. The Erdos-Renoyi model constructs a random network as follows: We randomly pick a node (say node u) among the nodes in the network and if there exists at least one link involving node u among the links in CandidateLinks, then we randomly pick a node (say node v) among these nodes with which u has link in the set CandidateLinks (if no such u-v link exists in the set CandidateLinks, then node u is not considered any more for link addition). We generate a random number from 0 to 1; if this random number is less than pER (pER is the probability that there can be a link between any two nodes in the network), then the link u-v is added to the network; otherwise, not. Either way, the link u-v is removed from the set CandidateLinks after being considered for possible inclusion in the network. We repeat the above procedure until the CandidateLinks set becomes empty. During this process of evolution, the network is not connected (i.e., not all nodes exist as a single component such that the nodes are reachable to each other either directly or through one or more intermediate nodes) for a while and we refer to this phase of the network evolution as the growth phase. During the growth phase, the network comprises of several components (subsets of the vertices) that are not reachable from each other. An interesting fact is that not all the components are of the same size; there exists a particular component called the giant component whose size increases with the addition of links in the network and the rest of the components are of relatively much smaller size. As the network evolves (with the addition of new links), the smaller components merge with the giant component and eventually, at the end of the growth phase, there exists only one connected component in the network. We refer to the phase of network evolution subsequent to the growth phase as the balancing phase – because, the further addition of links (i.e., after the emergence of a single connected component that encompasses all the vertices) reduces the variation in node degree and facilitates all nodes to have comparable degree. We observe the same in Tables 2 and 3 that list the values for the spectral radius ratio for node degree and the coefficient of variation of node degree at the time of emergence of the giant component as well as at the end of the network evolution.
We simulate the evolution of random networks according to the Erdos-Renoyi model by starting with a network of total of N nodes (we conduct simulations with N = 100 nodes and 200 nodes) and attempting to add one link at a time with a probability pER whose values are 0.05, 0.10, 0.20 and 0.30. For each value of pER, we run 200 instances of these simulations and average the results for the spectral radius ratio for node degree and the coefficient of variation of node degree observed for each possible value of the size of the giant component (the size of the giant component ranges from 2 nodes to the total number of nodes in the network). Figures 2 and 3 capture the distribution of the spectral radius ratio for node degree and coefficient of variation of node degree as a function of the size of the giant component during the growth phase for different values of pER for 100 and 200 nodes respectively. The interesting observations are that the distribution of the variation in node degrees in the giant component during the growth phase remains almost the same, irrespective of the probability of link between any two nodes (as long as pER is above the threshold value of 1/number of nodes). We observe a similar pattern of increase in the variation of node degree with respect to both the metrics as the giant component evolves; after the giant component reaches a size that is more than 85% of the nodes in the network, we start seeing a marginal decrease in the variation of node degree. We could thus say that the spectral radius ratio for node degree as well as the coefficient of variation in node degree exhibit a concave down pattern of increase with increase in the size of the giant component during the growth phase.
Figure 2: Distribution of the spectral radius ratio for node degree and the coefficient of variation of node degree during evolution of the giant component of a random network: Growth phase (Total Number of Nodes: 100)
International Journal of Computer Networks & Communications (IJCNC) 