Method for managing networks by analyzing connectivity

• US 20070168533A1
• Filed: 12/29/2004
• Published: 07/19/2007
• Est. Priority Date: 12/30/2003
• Status: Active Grant

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Canright, Geoffrey, Engo-Monsen, Kenth, Weltzien, Asmund
• Granted Patent: US 7,610,367 B2
• Time in Patent Office: Days
• US Class Current: 709/230
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them

Abstract

A method is disclosed for determining the ability of a network to spread information or physical traffic. Said network includes a number of network nodes interconnected by links. The method comprises mapping the topology of a network, computing a value for link strength between the nodes, computing an Eigenvector Centrality index for all nodes, based on said link strength values identifying nodes which are local maxima of the Eigenvector Centrality index as centre nodes, grouping the nodes into regions surrounding each identified centre node, assigning a role to each node from its position in a region, as centre nodes, region member nodes, border nodes, bridge nodes, dangler nodes, and measuring the susceptibility of the network to spreading, based on the number of regions, their size, and how they are connected.

Claims

1. A method for determining the ability of a network to spread information or physical traffic, said network including a number of network nodes interconnected by links, the method being characterized in

mapping the topology of a network,

computing a value for link strength between the nodes,

computing an Eigenvector Centrality index for all nodes, based on said link strength values

identifying nodes which are local maxima of the Eigenvector Centrality index as centre nodes,

grouping the nodes into regions surrounding each identified centre node,

assigning a role to each node from its position in a region, as centre nodes, region member nodes, border nodes, bridge nodes, dangler nodes,

measuring the susceptibility of the network to spreading, based on the number of regions, their size, and how they are connected.

2. A method as claimed in claim 1,

characterized in computing said link strength value for any pair of nodes by assigning a value of 0 if no link exists and 1 if any link exists.

3. A method as claimed in claim 1, characterized in computing said link strength value by counting the number of different types of bonds any pair of nodes uses in their interaction, using the number of bonds as a measure for link strength.

4. A method as claimed in claim 1, characterized in computing said link strength value by measuring the traffic between any two nodes, using the measure of traffic as a measure for link strength.

5. A method as claimed in claim 1, characterized in computing said link strength value by measuring the traffic between each pair of nodes for each different type of bond, dividing the amount of traffic in each type of bond with the total traffic for that type of bond, using the sum of the resulting fractions as a measure for link strength.

6. A method as claimed in any of the claims 1-5, characterized in organizing said link strength values into a matrix, the adjacency matrix, and computing the Eigenvector Centrality index as the principal eigenvector of said adjacency matrix.

7. A method as claimed in claim 1, characterized in assigning the role of region member nodes in a given region to all nodes that have a unique association to the centre node of said region.

8. A method as claimed in claim 7, characterized in assigning the role of region member nodes in a given region to all nodes that are closer in number of hops to the centre node of said region than any other centre node.

9. A method as claimed in claim 7, characterized in assigning the role of region member nodes in a given region to all nodes for which the steepest ascent link path in the topology map terminates uniquely at the centre node of that region.

10. A method as claimed in claim 7, characterized in assigning the role of region member nodes in a given region to all nodes that are associated to the centre node in said region, if it is closer (in number of hops) to the centre node in said region than to any other centre node, and if its distance from the centre node in said region is not greater than a predefined number of hops.

11. A method as claimed in claim 1, characterized in assigning the role of border nodes to all nodes that have no unique association to any one centre node.

12. A method as claimed in claim 1, characterized in assigning the role of bridge nodes to all border nodes which lie on at least one non-self-retracing link path connecting two centre nodes.

13. A method as claimed in claim 1, characterized in assigning the role of dangler nodes to all border nodes, and lie on no non-self-retracing link path connecting two centre nodes.

14. Use of the method as claimed in any of the claims 1-13 for preventing the spreading of virus or harmful information in a network.

15. Use of the method as claimed in any of the claims 1-13 for improving the spreading of information in a network.

16. Use of the method as claimed in any of the claims 1-13 for planning the architecture of a network, in order to improve robustness and/or security and/or communication efficiency in said network.

17. Use of the method as claimed in any of the claims 1-13 for planning the architecture of a power network in order to improve the robustness of said network.

18. Use of the method as claimed in any of the claims 1-13 for planning a distribution network for goods.

19. Use of the method as claimed in any of the claims 1-13 for planning a transport network.