Hung Quoc Vo
email: vqhung@simula.no

Olav Lysne
email: olav.lysne@simula.no

Amund Kvalbein
email: amundk@simula.no

Permutation Routing for Increased Robustness in IP Networks

Keywords: IP networks, Multipath Routing, Resilience, Fault-tolerant

We present Permutation Routing 1 as a method for increased robustness in IP networks with traditional hop-by-hop forwarding. Permutation Routing treats routers involved in traffic forwarding as a sequence of resources, and creates permutations of these resources that give several forwarding options. We introduce Permutation Routing as a concept, and use it to create routings where we seek to maximize single link fault coverage. Analogous to the IETF standardized Loop-Free Alternate (LFA), Permutation Routing can easily be implemented for OSPF or IS-IS networks to augment existing ECMP forwarding with additional loop-free forwarding entries for improved load balancing or fault tolerance. Our evaluations show that Permutation Routing can increase single link fault coverage by up to 28% compared to LFA in inferred network topologies.

Introduction

The last few years have witnessed the adoption of the Internet as the preferred transport medium for services of critical importance for business and individuals. In particular, an increasing number of time-critical services such as trading systems, remote monitoring and control systems, telephony and video conferencing place strong demands on timely recovery from failures. For these applications, even short outages in the order of a few seconds will cause severe problems or impede the user experience. This has fostered the development of a number of proposals for more robust routing protocols, which are able to continue packet forwarding immediately after a component failure, without the need for a protocol re-convergence. Such solutions add robustness either by changing the routing protocol so that it installs more than one next-hop towards a destination in the forwarding table [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF][2] [START_REF] Nelakuditi | Fast local rerouting for handling transient link failures[END_REF], or by adding backup next-hops a posteriori to the forwarding entries found by a standard shortest path routing protocol [START_REF] Atlas | RFC5286: Basic Specification for IP Fast Reroute: Loop-Free Alternates[END_REF][5] [START_REF] Kvalbein | Multiple routing configurations for fast IP network recovery[END_REF]. Unfortunately, few of these solutions have seen widespread deployment, due to added complexity or incompatibility with existing routing protocols.

Installing more than one route to a destination has obvious advantages with respect to increased robustness. First, it provides alternative routes that are readily available after a link failure. Second, it provides several paths for loadbalancing, which can be used to absorb short-lived spikes in traffic demand and thus avoid congestion. Deployed intradomain routing protocols such as OSPF and IS-IS have traditionally installed only a single shortest path to each destination, or multiple equal-cost shortest paths with the ECMP extension. ECMP allows some degree of multipath routing, but can only give more than one forwarding next-hop to a limited subset of all source-destination (S-D) pairs in a network. Recently, a mechanism called Loop-Free Alternates (LFA) [START_REF] Atlas | RFC5286: Basic Specification for IP Fast Reroute: Loop-Free Alternates[END_REF] has become available in some routers. LFA allows routers to install alternate forwarding entries that can be used as backup if the primary next-hop fails. LFA improves robustness compared to ECMP, but there will still be many S-D pairs with only a single path (next-hop) available [START_REF] Francois | LFA applicability in SP networks[END_REF].

This paper presents Permutation Routing as a novel and flexible approach for calculating multiple loop-free next-hops in networks with traditional hop-byhop forwarding. Permutation Routing is based on the observation that routing in any network consists of using a set of resources (links and nodes) in sequence. A routing strategy can therefore be expressed as a permutation of the nodes that are involved in traffic forwarding to a destination. Routing will be loopfree as long as traffic can only be forwarded in one direction with respect to the node ordering in this permutation. The main focus in this paper is to use Permutation Routing to create a routing that maximizes the single link fault coverage. Other routing strategies based on permutations of links in networks with interface-specific forwarding [START_REF] Nelakuditi | Fast local rerouting for handling transient link failures[END_REF] can also be developed.

In this paper, we provide a simple backtracking algorithm that constructs a permutation of routers for each destination, and a simple forwarding rule that allows us to generate forwarding tables based on the permutations. The properties of the resulting routing are determined by the constraints used at each step in the permutation construction. The input to the construction algorithm is the topology information that is collected by a link state routing protocol, and hence no new control plane signalling is needed with Permutation Routing. Importantly, Permutation Routing can easily be integrated with existing intradomain routing protocols, and can be used to augment the shortest path routing tables with additional forwarding entries. We show how the constraints in the permutation construction can be designed so that the resulting routing is compatible with normal shortest path routing, while still offering significantly more forwarding options than the existing LFA. With multiple loop-free alternates for a given primary next-hop, OSPF or IS-IS may employ some of them as unequal-cost primary paths and the rest as back-up paths. In the case of multiple primary paths, packets can be distributed evenly among paths or with more intelligent load balancing methods [11][12]. In this paper we focus on finding a set of loop-free paths, and leave the important topic of load-balancing across these paths for future work.

The rest of the paper is organized as follows. Section 2 introduces the notion of Next-Hop Optimal Routing (NHOR), which we will use as our main design objective. Section 3 introduces Permutation Routing and the relationship between a permutation of routers and the corresponding routing graph. Section 4 describes a generic algorithm to construct permutations. Section 5 describes a specific construction algorithm that approximates NHOR, and a modified version that is also compatible with standard shortest path routing. Section 6 shows simulation results evaluating the path diversity and the computational complexity of Permutation Routing. Section 7 reviews related work. Section 8 concludes the paper.

Next-Hop Optimal Routing

Before introducing Next-Hop Optimal Routing as our objective function for robust routing, let us introduce some vocabulary that we will use in the rest of this paper. By a routing, we refer to the assignment of a set of next-hops for each destination node in each source node. We do not distinguish traffic from different sources, and hence traffic transiting a node is treated in the same way as traffic originated at the node. We require that a routing must be loop-free, and hence a given routing corresponds to a Directed Acyclic Graph (DAG) rooted at each destination node consisting of the links and nodes involved in packet forwarding. With multipath routing, each node may have several outgoing links in the DAG for a destination. A routing where all links are included in each DAG is referred to as a full connectivity routing. With a given network topology, many different high or full connectivity routings can normally be constructed. However, they will have different properties with respect to failure recovery and load balancing. routing graphs, where all links can be used for packet forwarding. They differ, however, in their distributions of next-hops. In DAG-2, there are three nodes (a, e and f ) that have only a single next-hop towards d. DAG-3 on the other hand, has only two such nodes (a and e). DAG-2 and DAG-3 are both compatible with shortest path routing, because they contain all directed links of DAG-1. DAG-4 is not compatible with shortest path routing: by changing the direction of the link (c, e), the number of nodes with a single next-hop has been reduced to one (the minimum value).

To maximize the single link fault coverage and load-balancing capabilities of a network, it is important that there is more than one next-hop available for as many S-D pairs as possible. This leads us to the following optimization criterion for Next-Hop Optimal Routing (NHOR): Definition 1. An NHOR is a full-connectivity routing that maximizes number of S-D pairs that have at least two next-hops towards a destination. As illustrated by the example above, an NHOR will not always be compatible with shortest path routing. For that reason, we also define the Shortest-Path compatible NHOR (NHOR-SP): Definition 2. An NHOR-SP is a full-connectivity routing that maximizes number of S-D pairs that have at least two next-hops while containing the DAG calculated by a shortest path algorithm.

Permutation Routing

We consider a network modeled as a connected graph G = (V, E) where V is a set of nodes and E ⊆ V × V is the set of links (edges) and its topology. A connected link from node i to node j is denoted by (i, j).

Without loss of generality, we look at the assignment of next-hops for each destination individually. For a destination d ∈ V , let R d = (V, E d ) be a routing function for packets destined to destination d, where E d is a set of directed links constructed on E. In R d , node j is called a next-hop of node i if there exists a directed link between node i and node j, denoted by (i → j). For a loop-free routing, R d must be a DAG rooted at destination d.

The routing function R d contains all valid paths to d, and each path can be considered as a sequence of nodes from a specific source to d. At each node, packet forwarding is the process of sending packets to a next-hop in such a sequence. In the rest of this section, we describe how Permutation Routing can be used as a tool to find such sequences with the goal of realizing NHOR. Definition 3. For a given network topology G = (V, E), a permutation P of nodes is an arrangement of all nodes in V into a particular order.

We write j < i to denote that j occurs before i in P . Our goal is to construct permutations that realize a certain routing strategy. Definition 4. A permutation P is a routing permutation for R d if and only if all next-hops of each node occur before it in P :

∀(i → j) ∈ E d : j < i.
According to this definition, the destination node d will always be the first node in a routing permutation for R d . Nodes further out in the routing permutation will be topologically farther from the destination.

Lemma 1. Any loop-free routing function R d can always be represented by a routing permutation in which d is at the left-most position.

Proof. A loop-free routing function R d = (V, E d ) is a DAG, rooted at d. Let arrange i ∈ V into a sequence such that if E d contains a directed link (i → j),
then j appears before i in that sequence. Such an arrangement can be calculated by a topological sort algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. Destination d ∈ V is the only node that does not have any outgoing link. Following the above ordering, node d, hence, has been placed at the left-most position of the sequence.

In general, there can be more than one routing permutation for one routing function R d . Starting with a routing permutation P , another routing permutation P can be generated by swapping two consecutive nodes that are not connected by a directed link to each other. For instance, both permutations {d a b e c f } and {d b a e c f } are routing permutations for DAG-1 according to Def. 4.

In the reverse process, routing tables can be generated from a routing permutation, given a forwarding rule that defines the relationship between neighboring nodes. For now, we consider a greedy forwarding rule for constructing the routing table, in which all topological neighbors of a node that occur before it in the routing permutation are installed as next-hops. Note that this forwarding rule will result in a full connectivity routing, where all links in the topology are potentially used for traffic forwarding to all destinations. This will maximize the potential for load balancing and failure recovery. More restrictive forwarding rules could also be considered, which would result in a sparser DAG. This can sometimes be beneficial in order to avoid excessively long paths, or to limit the number of next-hops for a particular destination.

With the given forwarding rule, different routing permutations will result in routing functions with different robustness characteristics. Our goal is to find a routing permutation that can realize NHOR. This problem is believed to be NP-hard. In the next section, we present an algorithm that produces routing permutations that approximate NHOR.

Generating Routing Permutations

This section introduces a generic method for constructing routing permutations. The construction method is based on a backtracking algorithm, and can be used to construct routing permutations with different optimization objectives. In the next section, we specify the constraints that are used to approximate NHOR.

We reconsider a topology G = (V, E) of N nodes (|V | = N ), all of which are uniquely identified by a number from 1 to N . Let P = {p 1 , p 2 , . . . , p N } be a set of N variables in a fixed order from p 1 to p N , with respective domains D = {D 1 , D 2 , . . . , D N }. We refer to D i as the candidate set for each variable p i . A candidate set consists of the nodes that can be assigned to variable p i . Fig. 2: Basic assignment procedure for variable p i+1 Fig. 3: Search space for routing permutation problem A routing permutation P is constructed by successively assigning a node u ∈ D i to each variable p i ∈ P . Such assignment is said to be valid if it satisfies a specific constraint function C(u) which is defined to realize the selected routing objective. Fig. 2 illustrates the basic assignment procedure for variable p i+1 in which two key functions Update and Select work as filters to control the assignment. In the figure, each pair p i , u i represents an assignment of the node u i to variable p i . The assignment of nodes to a subset of variables {p 1 , p 2 , . . . , p i } ⊆ P given by { p 1 , u 1 , . . . , p i , u i } is called partial routing permutation with i nodes. For simplicity, we abbreviate it to p i . This basic assignment procedure has been embedded into the well-known backtracking algorithm to obtain the routing permutation P . The algorithm calls function Select (with built-in constraint function C(u)) which goes through D i to find a valid node for the current variable p i . If Select succeeds in finding a valid assignment, the algorithm calls function Update to generate domain D i+1 and proceeds to next variable p i+1 . Otherwise, a backtrack step will be executed to revisit the variable p i-1 . The algorithm terminates if a routing permutation P of N nodes, also denoted by p N , is found or a failure notification returns if all backtracks are examined but no solution is found under C(u).

If the constraint function C allows it, the backtracking algorithm will find one routing permutation P among all possible solutions by searching through the search space shaped by the number of variables in P and their domains of values. In a naïve implementation, the domain for variable p i+1 consists of (N -i) nodes that have not been placed in p i . Based on that observation, the search space S of the permutation assignment problem has a form of a tree of depth N rooted at the initial state p 1 , d as illustrated in Fig. 3. Solutions p N are located at its leaves. Two connected states in the search space refer to two instances of p i and p i+1 . Assume that t operations are needed on average to move from state p i to state p i+1 . The complexity in the best case when we do not need any backtrack step (backtrack-free) is O(t × N ). In other extreme, if there is only one solution and we always make the "wrong" choice, the complexity would be O(t × N !).

The naïve implementation described above results in high computational complexity, and is only feasible for small topologies. Hence, it is important to guide the search to avoid exploring the entire search space. In the next section, we use two main mechanisms to reduce the search space:

1. C(u) should be simple to reduce the computational complexity. 2. Domain D i can be limited by taking C(u) into account.

Next-hop Optimal Routings

Next, we apply the framework described above to construct two high robustness routings that approximate NHOR and NHOR-SP as defined in Section 2. We call them Approximate NHOR and Approximate NHOR-SP.

Approximate NHOR (ANHOR)

With Permutation Routing using greedy forwarding, a node in p i (i > 2) has at least two next-hops if it has at least two topological neighbors that occur before it in the routing permutation. The aim of the ANHOR algorithm is to maximize the number of nodes where this is the case.

The partial routing permutation p i represents a loop-free routing sub-graph towards destination d, denoted by

R i d = (V ( p i ), E d ( p i ))
where V ( p i ) is the set of i nodes in p i and E d ( p i ) is the set of directed edges formed by applying the greedy forwarding rule defined in section 3 on p i . To achieve a high robustness routing, the node selected for variable p i+1 to form the partial routing permutation p i+1 should be the node with the maximum number of topological neighbors already placed in p i . Correspondingly, the number of directed edges of the routing sub-graph formed by the partial routing permutation p i+1 , resulted from the assignment p i+1 , u , must be maximized:

|E d ( p i+1 )| = max ∀u∈Di+1 |E d ( p i , p i+1 , u )| (1)
For a more efficient implementation, we maintain a counter c[u] for each node u. This counter denotes the number of outgoing links from u to p i . In other words, c[u] corresponds to the number of next-hops node u will have if it is selected as the next assignment in the routing permutation. We derive the constraint function C AN HOR (u) to realize the expression (1) as follow:

C AN HOR (u) = True if c[u] = max ∀v∈Di+1 c[v] False otherwise
The constraint function C AN HOR (u) implies that the domain D i+1 includes all nodes that have at least one topological neighbor in p i . The domain is, therefore, updated following the recursive relation:

D i+1 = D i ∪ { v ∈ V | (u, v) ∈ E} \ {u} (2)
where u is the node that has been assigned to variable p i in the i-th assignment. The computational complexity of ANHOR is the product of the average number of operations to make a move between two successive states and the total number of states visited in the search space.

Proposition 1. Constraint function C AN HOR (u) gives a backtrack-free algorithm for all connected input topologies.

Proof. The proof is by contradiction. Assume that the algorithm with the constraint function C AN HOR (u) is not backtrack-free. This means that constraint function returns False for all u ∈ D i+1 at some iteration. That can not happen because D i+1 can never be empty in a connected topology before all nodes have been placed in the permutation and all nodes in domain D i+1 always have at least one next-hop in p i .

Given the backtrack-free property of our algorithm, the complexity of calculating a permutation for each destination is O(|E| + N × |D|), where |D| denotes the average size of the domain. Typically, |D| depends solely on the average node degree of the network topology. In dense topologies, the total complexity of calculating routing permutations for all destinations can approach O(N 3 ). The backtrack-free property also gives a low memory consumption because it does not need to store temporary partial routing permutations.

Approximate NHOR-SP (ANHOR-SP)

Let R SP The construction of such a routing permutation P is based on the assignment procedure described in Fig. 2. To this end, the shortest path compatibility constraint is implemented in function Update to limit the size of domain D i+1 for variable p i+1 and the connectivity constraint will be formalized by a constraint function C AN HOR-SP (u) and realized in function Select. Clearly, the constraint function C AN HOR-SP (u) is identical to C AN HOR (u).

The next node in routing permutation P is selected among nodes that have all their shortest path next hops towards d already placed in p i . Formally, let

R SP,i d = (V ( p i ), E SP d ( p i )) be the shortest path tree of V ( p i ) nodes and R SP,i d ⊆ R SP d .
The domain D i+1 for variable p i+1 includes all nodes u such that the assignment p i+1 , u , resulting in p i+1 , fulfills:

R SP,i+1 d ⊆ R SP d Let c sp [v]
be the number of shortest path next-hops placed in p i and n sp [v] be the total number of shortest path next-hop that can be calculated from R SP d of node v. The domain D i+1 for variable p i+1 follows the recursive relation:

D i+1 = D i ∪ { v ∈ V | c sp [v] = n sp [v] } \ {u} ( 3
)
where u is the node that has been assigned to variable p i .

Proposition 2. Constraint function C AN HOR-SP (u) gives backtrack-free algorithm for all connected input topologies.

Proof. According to Proposition 1, constraint function C AN HOR-SP (u) always returns True unless D i is empty. We show here that D i can never be empty before all nodes have been placed in the permutation. If D i is empty, there is no node that have all its shortest path descendants in p i . In other words, we can follow the shortest path DAG R SP d from any node that has not been placed and always find a next-hop node that is not placed in p i . But this is impossible: since R SP d is connected and loop-free, any path along the shortest path DAG will eventually reach the destination, which is the first node that was placed in the permutation.

The computational complexity of ANHOR-SP towards one destination includes two parts: the shortest path calculation using Dijkstra's algorithm and routing permutation construction. Due to the property of backtrack-freedom, with sparse topologies the complexity of second part towards one destination would be O(|E|

+ |E SP d | + N × |D|)
where |D| denotes the average size of the domain. In dense topologies, the total complexity of calculating routing permutations for all destinations can approach O(N 3 ).

With a low computational complexity, ANHOR-SP can be implemented on a per-router basis in OSPF or IS-IS networks. To ensure a consistent permutation routing in the entire network, constraint function C AN HOR-SP (u) must return the same node in each assignment among possible selections. We can break that tie by letting the highest router ID2 be picked.

Performance Evaluation

We evaluate the performance of the proposed algorithms by measuring how well they realize NHOR as defined in Def. 1. Since multipath routing leads to path inflation, we also measure the path length distribution. ANHOR and ANHOR-SP are compared to standard shortest path routing with ECMP, and to LFA. Comparisons to other robust routing methods [3][6] are less relevant, because of their different objectives and implementation costs.

Evaluation Setup

We select six representative network topologies from the Rocketfuel project [START_REF]Rocketfuel topology mapping[END_REF] for our evaluations. The topologies are listed in Table 1 in increasing order of their average node degrees. The results for ECMP and LFA depend heavily on the link weight settings used in the topologies. To obtain realistic link weight settings, we run local search heuristic with link load objective function proposed in [START_REF] Fortz | Internet traffic engineering by optimizing OSPF weights[END_REF], using a traffic matrix generated by the gravity model [START_REF] Nccui | IGP link weight assignment for operational Tier-1 backbones[END_REF]. For AS1239, we use unit link weights, because the local search heuristic described in [START_REF] Fortz | Internet traffic engineering by optimizing OSPF weights[END_REF] does not scale to a topology of this size. Note that Permutation Routing will work with any link weight settings. We use this approach to show the performance with "typical" link weights.

Robustness Evaluation

Maximizing multipath capability Fig. 4 shows the fraction of nodes with at least two next-hops with the different routing methods. For reference, Fig. 4 also shows the fraction of nodes in each topology with a node degree larger than 1. Obviously, nodes with a degree of 1 can not have more than 1 next-hop to any destination. We observe that the multipath capability varies strongly between topologies; it is generally higher in more well-connected networks. ANHOR achieves a significant improvement over ECMP and LFA in all networks.

Note that the number of next-hops achieved with ANHOR is independent of link weight settings, while ANHOR-SP is constrained to including the shortest paths in the routing. ANHOR-SP performance is close to ANHOR, and gives a clear improvement over LFA (by up to 28% in AS1239). This shows that Permutation Routing can give a significant gain compared to existing solutions, while being compatible with shortest path routing with realistic link weight settings.

Next-hop distribution Fig. 5 shows the mean and variance for the number of next-hops at each router in our 6 topologies. For increased robustness and load-balancing, it is generally good to have a high mean and a low variance in the number of next-hops. If this variance is high, it means that a few nodes have a high number of next-hops, while others might be left with only one.

Both ANHOR and ANHOR-SP produce full connectivity routings, which means that the mean number of next-hops across all S-D pairs will be equal to half the average node degree in the topology. The mean is somewhat lower for LFA and ECMP, meaning that some links are not used for packet forwarding. The variance, however, is lower with ANHOR than with ANHOR-SP and LFA. This shows how ANHOR achieved a better (more uniform) next-hop distribution than the other routings. In practice, there are good reasons to limit the number of next-hops that are installed in the forwarding table for a particular destination. Installing more than a few next-hops will not give much benefit with respect to robustness or load-balancing. It will, however, require more fast memory in the forwarding table, and may lead to the unnecessary inclusion of paths that are much longer than the shortest path.

Hence, we look at an approach where the number of next-hops for a particular destination is limited to at most K. We define a Routing Efficiency coefficient, which denotes the fraction of bidirectional links that are used for traffic forwarding with a given K.

RE = 2 × |E d (K)| / |E| (4)
where |E d (K)| is the number of directed links in the routing DAG when each node can have at most K next-hops and |E| is the number of bidirectional links in the network topology. According to this definition, 0 ≤ RE ≤ 1. Note that a high RE is desirable, and corresponds to a low variance in the number of next-hops achieved.

Table 2 shows the RE values for three values of K in the selected topologies. The given value is the average over all S-D pairs. We see that for all routing methods, a higher K gives a higher RE value. ANHOR and ANHOR-SP give the highest RE values, sometimes with a significant improvement over ECMP and LFA even for K = 2. The RE values in more well-connected topologies (AS1239) are lower than in sparse topologies. Such topologies contain a high number of nodes with a very high degree (39% nodes has their degrees greater than 15 in AS1239), and a low K will hence exclude many valid (but often unnecessary) paths. Path Stretch High path diversity increases robustness and allows for more load balancing. However, it has a cost in terms of path inflation. Next, we look at the distribution of path lengths. We focus on path lengths in terms of hop counts, since this metric is independent of the link weight settings. Fig. 6 shows the average path stretch for K = 3 with different routings, where the length of each valid path has been normalized with the shortest path length for that S-D pair. We observe that the superior path diversity in ANHOR and ANHOR-SP comes at the cost of some path inflation, but that the average path lengths are still comparable to those of shortest path routing. The path inflation introduced with multipath routing can be ameliorated with more intelligent load balancing methods [11][12]. Running time and memory consumption The complexity of our proposed algorithms depends on the number of nodes, links and on how efficiently the size of the candidate set can be reduced. The average size of candidate set turns out to be approximately 5 times (AS1755) to 12 times (AS1239) higher than their corresponding average node degrees in our tested topologies. Fig. 7 shows the relative running time of each routing method to ECMP across six topologies. The AS topologies are listed in an increasing order of number of nodes. The results are achieved with an Intel Core 2 CPU 6300 @ 1.86 GHz machine. ANHOR has a low running time that is comparable to a normal ECMP routing computation. For all destinations, the total time difference is less than 10% for all topologies. As for ANHOR-SP, calculating routing permutations for all destinations take less than four times of ECMP. Across all topologies, the memory consumption never exceeds 6 MB.

Related Work

This paper presents Permutation Routing as a method for increased robustness in IP networks with traditional hop-by-hop forwarding. The proposed method can be used to generate routings that give a significant boost in number of nodes that have at at least two forwarding options to a destination. Our proposal shares the same principle with many existing solutions that aim at adding robustness either by changing routing protocols to adopt more than one next-hop towards a destination in the routing table such as DUAL [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF], MDVA [START_REF] Vutukury | MDVA: A Distance-Vector Multipath Routing Protocol[END_REF], FIR [START_REF] Nelakuditi | Fast local rerouting for handling transient link failures[END_REF] or adding backup next-hops a posteriori to the forwarding entries found by a standard shortest path routing protocol such as LFA [START_REF] Atlas | RFC5286: Basic Specification for IP Fast Reroute: Loop-Free Alternates[END_REF], Not-via [START_REF] Shand | IP Fast Reroute Using Not-via Addresses[END_REF], MRC [START_REF] Kvalbein | Multiple routing configurations for fast IP network recovery[END_REF], SPT-DAG [START_REF] Elhourani | Enhancing Shortest Path Routing for Resilience and Load Balancing[END_REF]. Unlike DUAL and MDVA, Permutation Routing bases its construction solely on readily available topology information and hence no new control plane signalling is required. In addition, Permutation Routing outperforms LFA and does not introduce overhead bits as MRC and SPT-DAG.

Recent solutions focus on centralized routing that can provide added flexibility by improving path diversity that meets different requirements. Examples are O2 [START_REF] Schollmeier | Improving the resilience in IP networks[END_REF] and Protection Routing [START_REF] Kwong | On the feasibility and efficacy of protection routing in IP networks[END_REF]. O2 routing has a similar routing objective to Permutation Routing, but limits itself to finding only two next-hops for each node. Permutation Routing, on the other hand, allows a tunable K ≥ 1 while still being compatible with traditional link-state routing protocols. In the same category, Protection Routing presents a two-phase heuristic to produce a routing for a given traffic demand in a centralized routing system. In phase 1, the heuristic seeks to minimize number of unprotected nodes towards a destination while minimizing the cost function given in [START_REF] Fortz | Internet traffic engineering by optimizing OSPF weights[END_REF]. Although Routing Permutations share the goal of minimizing the number of nodes with only one forwarding option, we prefer to evenly distribute next-hops among nodes rather than performing traffic optimization for a specific traffic demand. We believe that finding a routing that optimizes for a given load function is less important in current Internet where traffic matrix elements vary significantly with time. Instead, we aim at maximizing the available forwarding options for more intelligent load balancing methods such as [11] [12] that are more responsive to traffic variation.

Similar to our method, MARA [START_REF] Ohara | MARA: Maximum Alternative Routing Algorithm[END_REF] employed the concept of permutations to generate routings that can maximize alternates. MARA, however, uses a different objective function seeking to maximize the minimum number of next-hops towards a destination. It can easily be shown that in networks without parallel links between nodes, this minimum must always be 1.

Conclusion

We have presented Permutation Routing as an approach for calculating more robust routing while being compatible with existing links state routing protocols. The paper proposed a generic algorithm to construct routing permutations. Routings that optimize different objectives can be implemented by modifying the selection criteria that are used in the construction algorithm. The goal of Permutation Routing is to maximize the survivability in a network with traditional hop-by-hop forwarding.

We have evaluated Permutation Routing with simulations on six ISP topologies. The results show that permutation routings outperform existing multipath approaches such as ECMP and LFA in terms of robustness and path diversity. We also showed that the complexity of calculating routing permutations is comparable to that of standard link state routing.

Fig. 1 :

 1 Fig. 1: A network topology with different DAGs

d

  = (V, E SP d ) denote the shortest path tree towards destination d. A routing permutation P whose routing function R d = (V, E d ) is an ANHOR-SP if R d satisfies two constraints in following order: 1. R d contains R SP d , meaning all routing choices for any node in R SP d are also valid routing choices for the same node in R d . 2. ANHOR-SP uses the same selection criterion as ANHOR in order to maximize the number of S-D pairs with at least two next-hops.

Fig. 4 :

 4 Fig. 4: Fraction of S-D pairs with at least two next-hops.

Fig. 5 :

 5 Fig. 5: Means and variances of next-hop distributions

Fig. 6 : 3 Fig. 7 :

 637 Fig. 6: Average hop-count path stretch with K = 3

Table 1 :

 1 Network topologies

	AS	Name	Nodes Links Avg. Degree
	1221	Telstra(au) 104 151	2.90
	1755	Ebone(eu)	87	161	3.70
	3967 Exodus(us)	79	147	3.72
	3257	Tiscali(eu)	161 328	4.07
	6461 Abovenet(us) 138 372	5.40
	1239	Sprint(us)	315 972	6.17

Table 2 :

 2 Routing Efficiency coefficient

			AS1221 AS1755 AS3967 AS3257 AS6461 AS1239
		ECMP	0.74	0.61	0.61	0.54	0.43	0.49
	K = 2	LFA ANHOR-SP	0.80 0.86	0.79 0.84	0.77 0.85	0.77 0.76	0.62 0.67	0.49 0.58
		ANHOR	0.94	0.90	0.95	0.81	0.81	0.60
		ECMP	0.76	0.62	0.62	0.54	0.46	0.56
	K = 3	LFA ANHOR-SP	0.86 0.92	0.90 0.95	0.87 0.94	0.82 0.88	0.77 0.85	0.57 0.75
		ANHOR	0.98	0.99	1.00	0.95	0.95	0.80
		ECMP	0.77	0.62	0.63	0.54	0.47	0.60
	K = 4	LFA ANHOR-SP	0.90 0.96	0.94 0.99	0.91 0.97	0.88 0.93	0.85 0.93	0.61 0.85
		ANHOR	1.00	1.00	1.00	0.99	0.99	0.92

Permutation Routing term is used in the literature with slightly different meanings, all related to the act of rearranging network objects (e.g. network devices or network devices and theirs associated radio channels) on which packets are routed from a source to a destination[START_REF] Nakano | Energy-efficient permutation routing in radio networks[END_REF] [START_REF] Liang | X: Permutation Routing in All-Optical Product Networks[END_REF].

The highest router ID means the biggest number numerically. For instance, 192.168.1.2 would be higher than 172.16.3.2, and 172.16.3.2 would also be higher than 172.16.2.1


Cong Li

Huijuan Wang

Piet Van Mieghem
email: vanmieghem@tudelft.nl

H Li

P F A Wang

Degree and Principal Eigenvectors in Complex Networks

Keywords: networks, spectral radius, principal eigenvector, degree, assortativity

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Dynamic phenomena occurring on networks are a¤ected by the structure of networks, e.g., the absence of epidemic thresholds in large scale free networks [START_REF] Barthélemy | Velocity and Hierarchical Spread of Epidemic Outbreaks in Scale-Free Networks[END_REF][3] [START_REF] May | Infection dynamics on scale-free networks[END_REF], the e¤ect of the degree correlations on the percolation of networks [START_REF] Newman | Assortative Mixing in Networks[END_REF]. The largest eigenvalue 1 (A) of the adjacency matrix A, called the spectral radius of the graph, has been shown to play an important role in dynamic processes on graphs, such as SIS (susceptible-infected-susceptible) virus spread [START_REF] Van Mieghem | Virus spread in networks[END_REF] and the Kuramoto type of synchronization process of coupled oscillators [START_REF] Restrepo | Onset of synchronization in large networks of coupled oscillators[END_REF] on a given network topology. For instance, in a SIS spreading model, the epidemic threshold c ' 1 1(A) separates two di¤erent phases of a dynamic process on a network: if the spreading rate is above the threshold, the infection spreads and becomes persistent in time; where < c , the infection dies out exponentially fast [START_REF] Pastor-Satorras | Epidemic dynamics and endemic states in complex networks[END_REF] [START_REF] Van Mieghem | Virus spread in networks[END_REF]. In the past decade, researches have focused on how topological changes, such as link (or node) removal, may alter the spectral radius. Milanese et al. [START_REF] Milanese | Approximating spectral impact of structural perturbations in large networks[END_REF] studied the dynamical importance of the structural perturbation by removing one node or link. Van Mieghem et al. [START_REF] Van Mieghem | Optimally decreasing the spectral radius of a graph by link removals[END_REF] have proved that to minimize the largest eigenvalue by removing a set of links or nodes is a NP-hard problem and have shown that the best strategy so far is based on the components of the principal eigenvector x 1 , which underlines the importance of the principal eigenvalue in characterizing the in ‡uence of link/node removal on the spectral radius. Our main objective is to investigate the topological meaning of x 1 , which has been rarely studied. Especially, we aim to understand the relation between x 1 and the degree vector/sequence 1 d, the computationally simplest and mostly studied property of a network.

The degree correlation, also called the assortativity D is computed as the linear correlation coe¢ cient of the degree of nodes connected by a link. It describes the tendency of network nodes to connect preferentially to other nodes with either similar (when D > 0) or opposite (when D < 0) properties i.e. degree [START_REF] Newman | Mixing patterns in networks[END_REF]. The assortativity was widely studied after it was realized that the degree distribution alone provides an insu¢ cient characterization of complex networks. Networks with the same degree distribution may still di¤er signi…cantly in various topological features. Degree-preserving rewiring [START_REF] Van Mieghem | In ‡uence of assortativity and degree-presreving rewiring on the spectra of networks[END_REF] allows us to either increase or decrease the assortativity of a network without changing the degree of each node. The relation between the principal eigenvector and the degree vector is systematically investigated in networks with various degree distributions and degree correlations.

Section 2 illustrates the importance of the principal eigenvector in characterizing the in ‡uence of link/node removal on the spectral radius by two key theories developed in our early work and further simulations. Subsequently, we explore the properties of the principal eigenvector and the relation between the (normalized) degree vector and the principal eigenvector in networks with di¤erent degree correlation and with the degree distribution derived from the Erdös-Rényi random graphs 2 [START_REF] Erdös | On Random Graphs. I[END_REF], the Bárabasi-Albert graphs 3 [START_REF] Barabasi | Emergency of Scaling in Random Networks[END_REF], and real-world networks (see Section 3). Our major contributions are: (a) the average of the components in the principal eigenvector E[x 1 ] is shown and explained to decrease with the assortativity D ; (b) the di¤erence between the principal eigenvector and the degree vector is proved to be the smallest, when 1 = N2 N1 , where N k is the total number of walks with k hops in a network and (c) the correlation between principal eigenvector and the degree vector decreases as the assortativity D is decreased. These …nds provide essential inspiration on when the degree vector well approximates the principal eigenvector. Finally, we illustrate the possibility to approximate the principal eigenvector based strategy to minimize the largest 1 The degree vector/sequence is composed of the degree of each node, following the same ordering as the principal eigenvector. 2 An Erd½ os-Rényi random graph can be generated from a set of N nodes by randomly assigning a link with probability p to each pair of nodes. 3 A Bárabasi-Albert graph starts with m nodes. At every time step, we add a new node with m links that connect the new node to m di¤erent nodes already present in the graph. The probability that a new node will be connected to node i in step t is proportional to the degree di(t) of that node. This is referred to as preferential attachment.

eigenvalue by removing links/nodes by its corresponding degree based strategy (see Section 4), which can be well explained by the …ndings in early sections.

The decrease of the spectral radius

We consider a network as a graph G = (N , L), where N is the set of nodes and L is the set of links. The number of nodes is denoted by N = jN j and the number of links is represented by L = jLj. The graph G can be represented by the N N adjacency matrix A, consisting of elements a ij that are either one or zero depending on whether there is a link between nodes i and j. The eigenvalues of the adjacency matrix are ordered as N N 1

1 , where 1 is the spectral radius and the corresponding eigenvector x 1 is called the principal eigenvector. Let L m (or N m ) denote the set of the m links (or nodes) that are removed from G, and G m (L) = GnL m (or G m (N ) = GnN m ) is the resulting graph after the removal of m links (or nodes) from G. We denote the adjacency matrix of G m (L) (or G m (N )) by A m (L) (or A m (N )), which is still a symmetric matrix.

Theorem 1. For any graph G and graph G m (L) = GnL m , by removing m links from G, it holds that

2 X l2Lm (w 1 ) l + (w 1 ) l 1 (A) 1 (A m (L)) 2 X l2Lm (x 1 ) l + (x 1 ) l (1)
where x 1 and w 1 are the principal eigenvectors of A and A m (L) corresponding to the largest eigenvalues 1 (A) and 1 (A m (L)), respectively, and where a link l joins the nodes l + and l .

Proof. [START_REF] Van Mieghem | Optimally decreasing the spectral radius of a graph by link removals[END_REF] The decrease of the largest eigenvalue 1 (A) 1 (A m (L)) tends to be larger if the upper bound 2 P l2Lm (x 1 ) l + (x 1 ) l is larger. This motivates the principal eigenvector strategy to minimize the largest eigenvalue: removing the set of links that maximizes 2 P l2Lm (x 1 ) l + (x 1 ) l . Moreover, when only one link is removed, removing the link with the maximum (x 1 ) l + (x 1 ) l , maximizes not only the upper bound of (1), but likely the lower bound as well, since w 1 is close to x 1 in this case. This eigenvector strategy performs almost optimally in this situation.

Theorem 2. For any graph G and graph G m (N ) = GnN m , by removing m nodes from G, it holds that

0 1 (A) 1 (A m (N )) 2 X n2Nm (x 1 ) 2 n 1 (A) X j2Nm X i2Nm a ij (x 1 ) i (x 1 ) j (2)
where x 1 is the principal eigenvectors of A corresponding to the largest eigenvalues 1 (A). In particular, if m = 1, then

0 1 (A) 1 (A 1 (N )) 2 (x 1 ) 2 n 1 (A) ( 3
)
where n is the node removed.

Proof. [START_REF] Li | Bounds for the spectral radius of a graph when nodes are removed, accepted[END_REF] Theorem 2 implies that the decrease of spectral radius by removing a node or a set of nodes is strongly related to the principal eigenvector components corresponding to the removed nodes. Motivated by Theorem 2, the eigenvector based one node removal strategy to minimize the largest eigenvalue simply removes the node with the largest principal eigenvector component (x 1 ) n . We perform further simulations to illustrate the importance of the principal eigenvector components in characterizing the in ‡uence of the link/node removal on 1 . We deduce networks with di¤erent assortativities but with a given degree vector, which may follow a binomial or power-law degree distribution. Upon each network, we try all possible one link (or node) removal and examine the largest eigenvalue 1 (Gn(l)) (or 1 (Gn(n))) after removing one link (or node) as a function of (x 1 ) l + (x 1 ) l (or (x 1 ) 2 n ) corresponding to the link (or node) removed. By the Perron-Frobenius theorem [START_REF] Van Mieghem | Graph Spectra for Complex Networks[END_REF], all components of x 1 and w 1 are non-negative (positive if the corresponding graph is connected). Interestingly, 1 (Gn(l)) (or

1 (Gn(n))) decreases linearly as a function of increasing (x 1 ) l + (x 1 ) l (or (x 1 ) 2 n ),
as shown in Fig. 1. In other words, the spectral radius will be decreased more if the link (or node) removed has a larger (x 1 ) l + (x 1 ) l (or (x 1 )

2 n ).
3 Relation between the principal eigenvector and the degree vector

In view of the importance of the principal eigenvector in characterizing the in- ‡uence of link/node on the spectral radius, in this section, we explore how the average E[x 1 ] as well the variance of x 1 changes with the assortativity D when the degree vector, which may follow the degree distribution of network models or of real-world networks, remains the same. Moreover, we explore the di¤erence and the linear correlation coe¢ cient between the principal eigenvector and the degree vector, the simplest and mostly studies network metric, which as well provides important insights on under which condition the degree vector/sequence well approximates the principal eigenvector.

Properties of the principal eigenvector

Two types of degree distributions have been so far widely studied: the binomial and power-law degree distribution. The binomial degree distribution is a characteristic of an Erd½ os-Rényi random graph G p (N ), which has N nodes and any two nodes are connected independently with a probability p. Such a random construction leads to a zero assortativity as proved in [START_REF] Van Mieghem | In ‡uence of assortativity and degree-presreving rewiring on the spectra of networks[END_REF]. However, the class of graphs G(N; p) with the same binomial degree distribution

Pr[D G = k] = N 1 k p k (1 p) N 1 k
as Erd½ os-Rényi random graphs G p (N ) and obtained, for instance, by degree-preserving rewiring feature an assortativity that may vary within a wide range. The power-law degree distribution Pr[D = k] = ck , where c = 1=

P N 1 k=1 k has been widely observed in realworld networks. Similarly, graphs with a given power-law degree distribution, for example, generated by the Barabási-Albert power model [START_REF] Barabasi | Emergency of Scaling in Random Networks[END_REF] can be altered by the degree-preserving rewiring to obtain di¤erent assortativity.

We explore the principal eigenvector components (see Figure 2) as well as its average E[x 1 ] (see Figure 3) in graphs with the same degree distribution (i.e. binomial or power-law) but with di¤erent assortativities D obtained by degree-preserving rewiring. Figure 2 shows that the variance of the principal eigenvector increases with assortativity D . Furthermore, as shown in Figure 3,E[x 1 ] decreases with the increase of assortativity D . Similarly, we consider a set of 11 real-world networks. We apply degree-preserving rewiring to each realworld network to derive network instances with di¤erent assortativity. In other words, we derive a class of networks that possess the same degree distribution as a real-world network but di¤erent assortativities. Interestingly, we observe the same, E[x 1 ] decreases with increasing assortativity (see Figure 3(b)).

The decrease of E[x 1 ] and the increase of the variance of the principal eigenvector components with increasing assortativity can be qualitatively explained as follows. As de…ned, the principal eigenvector x 1 corresponds to the largest eigenvalue 1 follows

1 (x 1 ) j = N X q=1 a jq (x 1 ) q , ( 4
)
where a jq = 1 if q is a neighbor of node j, or else a jq = 0: The j-th component of the principal eigenvector (x 1 ) j tends to be large if node j has a large degree (number of neighbors) or if the components corresponding to its neighbors are large. When D is large, high degree nodes prefer to link with other high degree nodes. In this case, a high degree node possesses a large number of neighbors, whose corresponding eigenvector components are again likely to be large, whereas a low degree node connects to a small number of neighbors, whose corresponding components tend to be small. Both a large variance in degree and a large assortativity D contribute to a large variance V ar[x 1 ] of the principal eigenvector x 1 . This explains why variance V ar[x 1 ] of x 1 increases with D and with a given assortativity, the power-law graphs have a larger V ar[x 1 ] than the binomial graphs (see Figure 2). Furthermore, since V ar

[X] = E[X 2 ] (E[X]) 2 and x T 1 x 1 = 1, E[x 1 ] = r 1 N V ar[x 1 ], (5)
Correspondingly, both a large variance in degree and a large assortativity D contribute to a small E[x 1 ] of the principal eigenvector x 1 . Hence, E[x 1 ] decreases with increasing D and tends to be smaller when the degree variance is larger. Moreover, considering Eq. ( 5), we can deduce the upper bound

E[x 1 ] 1 p N .

Relation between degree vector and principal eigenvector

In this section, we investigate the relation between the principal eigenvector and the degree vector by their di¤erence and linear correlation coe¢ cient. The degree vector has to be …rst normalized to quantify its di¤erence with the principal eigenvector. We propose two scalings of the degree vector d = d

p d T d
and e d = 1 d, where is a constant. The corresponding di¤ erence vector between x 1 and the scaled degree vector is w = x 1

d p d T d
and y = x 1 1 d, respectively. The overall di¤erence can be quanti…ed by either the relative di¤erence u T w (or u T y) or the absolute di¤erence w T w (or y T y), actually, the square sum or the sum of the components in the di¤erence vector respectively. The …rst scaling of the degree

vector d = d p d T d
aims to obtain the same norm for the the degree vector and the principal eigenvector:

p d T d = p x T 1 x 1 = 1. The other e d = 1 d is motivated by (x 1 ) j = 1 1 P N r=1 a jr (x 1 ) r di
1 and the constant is determined (see Theorem

3) as the one minimize the absolute di¤erence y T y. Note that both linear scalings of the degree vector will not change the linear correlation coe¢ cient between the principal eigenvector and the degree vector.

Theorem 3. The absolute di¤ erence w T w (or y T y) between the principal eigenvector and the degree vector is the smallest (w T w = 0 or y T y = 0) when the spectral radius follows 1 = N2 N1 , where N k is the total number of k hop walks between any two nodes which can be the same.

Proof. The absolute di¤erence

w T w = (x 1 d p d T d ) T (x 1 d p d T d ) = x T 1 x 1 2 d T x 1 p d T d + d T d p d T d 2 = 2 2 d T x 1 p d T d .
(6) Moreover, the generalized form of ( 4) for the k-th largest eigenvalue k and the corresponding eigenvector

x k follow (x k ) j = 1 k P N r=1 a jr (x k ) r = dj k 1 k P N r=1 a jr ( (x k ) r
), we will determine so that y k = x k k d has minimum norm. Hence,

y T k y k = x k k d T x k k d = 1 2 k d T x k + 2 2 k d T d, (7)
is minimized with respect to if

2 k d T x k + 2 2 k d T d = 0 or k = d T x k d T d . Let y = y 1 , we obtain y T y = 1 (d T x 1 ) 2 d T d , (8)
using the derived in the last step. In both Eq. ( 6) and Eq. ( 8), w T w = 0 and y T y = 0 if d T x 1 = p d T d. In other words, when the principal eigenvector is proportion to degree vector, w = 0 (or y = 0). Since Ax

1 = 1 x 1 , d T x k = 1 u T x 1 . The condition d T x 1 = p d T d implies 1 u T x 1 = p d T d = p N 2
where

N 2 = d T d. Since x 1 = d p d T d
, and u T d = N 1 , Lemma 3 follows.

Notice that in some approximate mean-…eld models for virus spreading [START_REF] Pastor-Satorras | Epidemic dynamics and endemic states in complex networks[END_REF],

c N1 N2 = 1 1 . Furthermore, w T w = 0 (or y T y = 0) is a special case of u T y k = 0, when 1 = N2 N1 . The relative di¤erence w T u = u T x 1 d T u p d T d
(y T u) is zero when the absolute di¤erence is zero. We explore the relative di¤erence in general cases by considering the binomial graphs as an example. The sum of the principal eigenvector u T x 1 and the relative di¤erence w T u as a function of the assortativity are shown in Figure 4 to follow exactly the same trend, since the degree of each node, thus, rewiring. When the assortativity D = 0, the binomial graphs are actually Erd½ os-Rényi random graphs, for which 1 ' N2 N1 when the network size is large [START_REF] Van Mieghem | Graph Spectra for Complex Networks[END_REF]. Hence, both the absolute and relative di¤erence are zero when the assortativity is around zero. The sum of the principal eigenvector u T x 1 decreases with the assortativity D , as explained in Subsection 3.1.

Correlation between the principal eigenvector and the degree vector

Recall that so far the best strategy to minimize the spectral radius by links/nodes removal is based on the principal eigenvector. When the correlation (x 1 ; d) between the principal eigenvector and the degree vector is positively strong, we may use the degree vector instead of the principal eigenvector to determine which links/nodes to remove, which will be further illustrated in Section 4. Here, we investigate the linear correlation coe¢ cient (x 1 ; d) between the principal eigenvector and the degree vector as a function of D . Linear scaling of the degree vector will not change the linear correlation coe¢ cient. Hence, we consider the original degree vector. When the absolute di¤erence between the principal eigenvector and the scaled degree vector is zero, the principal eigenvector is proportion to degree vector. In this case, (x 1 ; d) = 1, which seldom occurs in real-world networks. A strong positive correlation, not necessarily to be one, is already interesting with respect to approximate the eigenvector strategy by the corresponding degree vector strategy in minimizing the spectral radius. Figure 5(a) depicts that (x 1 ; d) is mostly positively strong in the Erdös-Rényi random graphs and Bárabasi-Albert graphs. However, (x 1 ; d) decreases dramatically when the assortativity is decreased, actually around the minimal assortativity. Similarly, we derive networks with di¤erent assortativities by applying degree preserving rewiring to each of the 11 real-world networks. As in Figure 5 of both network models and real-world networks, the most evident decrease is observed in networks with a power-law degree distribution such as the C. elegans neural network, the Gnutella 3 network and the WordAdj network. These observations can be explained similarly as we explain the average/variance of the principal eigenvector versus assortativity in Section 3.1. In general, if a node has a large degree, its corresponding principal eigenvector component tends to be large even when the assortativity is zero, due to (4). A large positive assortativity implying large (or small) degree nodes tend to connect to other large (or small) degree nodes, further enforces a large degree node to have more likely a even larger principal eigenvector component compared to a small assortativity. Hence, a negative assortativity will weaken the correlation (x 1 ; d). Note that the correlation coe¢ cient is not necessarily the maximum at the maximal assortativity as shown in Figure 5, because here we examine the linear correlation coe¢ cient but not the rank correlation.

4 Application: degree vs. principal eigenvector strategy in minimizing the spectral radius

In this section, we illustrate the possibility to replace the principal eigenvector strategy by the degree vector in minimizing the spectral radius 1 via an example of node removal in power-law networks with di¤erent assortativities. As mentioned in Section 2, so far the best node removal strategy removes the node with the largest principal eigenvector component (x 1 ) j . A widely applied strategy to minimize 1 by removing m nodes (a) removes the set of m nodes with the highest component in the principal eigenvector of the original graph. The corresponding degree vector strategy (b) removes the set of m nodes with the highest degree in the original graph. We compare these two strategies in remov-ing m 2 [1; 200] nodes in graphs with positive, zero and negative assortativity (see Fig. 6) but with the same power-law degree distribution as in Fig. 5(a). Figure 6 shows that the decreases of 1 by removing nodes with strategy (a) and (b) are almost same when D is large. The eigenvector strategy (a) decreases the spectral radius more thus performs better than the degree vector strategy (b) when the assortativity is small. When the assortativity is large, the degree vector is positively and strongly correlated with the principal eigenvector. In such a case, the degree vector strategy, the simplest to compute, well approximates the principal eigenvector strategy in minimizing the spectral radius.

Conclusions

The principal eigenvector is essential in characterizing the in ‡uence of link/node on the spectral radius, whereas its topological meaning is far from well understood. This work, via both theoretical analysis and systematic simulations, contributes to the following aspects: (a) the average E[x 1 ] (or variance) of the principal eigenvector is shown and explained to decrease (or increase) with the assortativity D ; (b) the di¤erence between the principal eigenvector and the degree vector is proved to be the smallest, when 1 = N2 N1 and (c) we illustrate and explain why the correlation between principal eigenvector and the degree vector decreases as D is decreased. In general, both a large variance (heterogeneity) in nodal degree and a large degree correlation (homogeneity in connection) contribute to a large average and a small variance of the principal eigenvector and a strong correlation between the degree and the principal eigenvector. As a straightforward application of these …nds, we illustrate that when the assortativity is large, we could approximate the well performance principal eigenvector based strategy (to minimize 1 by removing links/nodes) by the corresponding degree vector, which is the simplest network property to compute.

Fig. 1 .

 1 Fig. 1. The spectral radius of graphs by removing a link (or node) as a function of corresponding components in principal eigenvector (a), (b)in Binomial graphs,(c), (d) in power-law graphs.

NFig. 2 .

 2 Fig. 2. The components of the principal eigenvector in increasing order. Images (a) (linear) (b) (semilogarithmic) are binomial graphs with di¤erent assortativity. Images (c) (linear) (d) (semilogarithmic) are power-law graphs with di¤erent assortativity.

Fig. 3 .

 3 Fig. 3. The average of the components of the principal eigenvector versus the assortativity. (a) in binomial and power-law graphs (b) in network instances derived from real-world networks via degree-preserving rewirings.

Figure 2

 2 compares as well the principal eigenvector x 1 with the normalized degree vector d = d p d T d in binomial graphs and power-law graphs (N = 500, L = 1984) with di¤erent assortativities. The components of x 1 and d are plotted in the order of increasing magnitude. The di¤erence between x 1 and d is a¤ected by D , which will be further explored in the following part.

Fig. 4 .

 4 Fig.[START_REF] Erdös | On Random Graphs. I[END_REF]. The di¤erence between the principal eigenvector and degree vector as a function of the assortativity D .

Fig. 5 .

 5 Fig.5. The linear correlation coe¢ cient between the degree vector and the principal eigenvector as a function of the assortativity (a) in both binomial graphs (red marks and line) and power-law graphs(blue marks and line); (b) in network instances derived from real-world networks via degree-preserving rewirings.

Fig. 6 .

 6 Fig. 6. The decrease of the spectral radius by successively removing m nodes in powerlaw networks. The square and circle dot dash lines show the decrease of the spectral radius by strategies (a) and (b) separately.

D in real-world networks. Figure5(b) illustrates that, the correlation (x 1 ; d) creases as the assortativity is decreased, especially around the minimal assortativity, which is the same as observed in network models. In the simulations