Arrangements for networks

• US 7,889,679 B2
• Filed: 02/02/2009
• Issued: 02/15/2011
• Est. Priority Date: 02/01/2008
• Status: Expired due to Fees

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Canright, Geoffrey, Engø-Monsen, Kenth, Ling, Richard Seyler, Bjelland, Johannes, Sundsøy, Pål Roe
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): Grey; Christopher P
• Application Number:
  US12/364,136
• Publication Number:
  US 20090252046A1
• Time in Patent Office: 743 Days
• Field of Search: 370/252, 370/254, 370/398, 370/395.21, 709220-226, 709238-244
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]

Abstract

A system for analyzing a network including a plurality of nodes associated and/or connected together by links. The system includes a processor coupled to a data memory. The processor is configured to access a first representation of the network and associated link weight measures w in the memory. Moreover, the system is configured to provide node values for the nodes and determine from the node values corresponding slope measures for links existing between the nodes, the slope measures being computed from a function of differences in node values and from the weight measures w for the links, the weight measures w being used for scaling the function of differences in nodes values; to select for at least some of the nodes one or more steepest ascent links having one or more greatest positive slope measures; and to generate a second representation corresponding to a steepest ascent graph of the network derived from information included in the steepest ascent links.

Claims

1. A system for analyzing a network including a plurality of nodes associated and/or connected together by links, the system including a processor coupled to a data memory, wherein the processor is configured to access a first representation of the network and associated link weight measures w in the memory, the system being configured:

(i) to provide node values for the nodes and determine from the node values corresponding slope measures for links existing between the nodes, the slope measures being computed from a function of differences in node values and from the weight measures w for the links, the weight measures w being used for scaling the function of differences in node values;

(ii) to select for at least some of the nodes one or more steepest ascent links having one or more greatest positive slope measures; and

(iii) to generate a second representation corresponding to a steepest ascent graph (SAG) of the network derived from information included in the steepest ascent links.

2. The system of claim 1, where said slope measures are computed from a difference in node values scaled by corresponding weight measures w for the links.

3. The system of claim 1, configured to subject the first representation to pre-filtering for eliminating from computations a sub-set of the nodes which do not contribute to the steepest ascent graph (SAG), for reducing a computational load on the processor.

4. The system of claim 1, configured to subject the steepest ascent graph (SAG) to post-filtering to remove links of the steepest ascent graph (SAG) which are irrelevant to determining operation of the network.

5. The system of claim 1, wherein said first representation is a matrix representation of the network and wherein said system is configured to compute the node values by calculating a principal Eigenvector of the matrix representation, the matrix representation including the link weight measures w.

6. The system of claim 1, wherein said processor is configured to determine the weight measures w for links in the network, and to map a topology of the network to an adjacency matrix A describing the network, wherein A_{i, j}=w(i, j) when a link exists between a node i and a node j, and wherein A_{i, j}=0 when no link exists between a node i and a node j.

7. The system of claim 6, configured to compute the node values by calculating a principal Eigenvector e of the matrix A, wherein e(i) is the Eigenvector centrality value of node i.

8. The system of claim 1, wherein said processor is configured to compute the node values as Eigenvector centrality values for the nodes, and to determine, for each node g in the network, a slope measure for each link from the node g to an adjacent node h, according to a slope from the node g to the node h being computed from (EVC(h)−

EVC(g))·

P[w(g, h)], wherein EVC(h) is the Eigenvector centrality value for the node h, EVC(g) is the Eigenvector centrality value for node g, and w(g, h) is the weight measure for the link between the node g and the node h, and P is a function.

9. The system of claim 1, configured, when generating said second representation, to set a pointer from each node i to its neighbor j having a steepest ascent link from the node i.

10. The system of claim 9, configured to generate said second representation by setting a pointer from each node i to itself if it has no positive slope to any of its neighboring nodes.

11. The system of claim 1, configured to generate said second representation by creating a matrix Ã

representing a steepest ascent graph (SAG) of the network, wherein entries of the matrix Ã

corresponding to the steepest ascent links are set to 1, and wherein the matrix element Ã

_i,i is set to 1 if the node i has no positive slope to any one of its neighboring nodes.

12. The system of claim 11, configured:

(a) to multiply a start vector s_i=i, wherein i is the node number, with the matrix Ã

;

(b) to repeat the multiplication in (a) until the start vector s converges to a stable vector s*; and

(c) to derive the region membership of each node from the stable vector s*.

13. The system of claim 12, configured:

(d) to identify nodes which are local maxima of the steepest ascent graph (SAG) as center nodes;

(e) to group the nodes into regions surrounding each identified center node;

(f) to remove the center nodes and the links to the center nodes from the steepest ascent graph (SAG);

(g) to identify neighboring nodes of the center nodes as head nodes; and

(h) to group nodes into sub-regions surrounding each identified head node, the nodes of a sub-region being linked to the head node of that sub-region in the steepest ascent graph (SAG).

14. The system of claim 13, configured:

(o) to identify neighboring nodes of the head nodes as sub-subregion head nodes; and

(p) to group nodes into sub-subregions surrounding each identified sub-subregion head node, the nodes of a sub-subregion being linked to the sub-subregion head node in the steepest ascent graph (SAG).

15. The system of claim 1, wherein the weight measure w is defined as 1/dist(g, h), where dist(g, h) is a distance measure between the nodes g and h.

16. The system of claim 8, wherein the function P is a monotonically increasing function in response to the weight w increasing.

17. The system of claim 1, wherein the processor is configured to generate a data product corresponding at least partially to said second representation of the network.

18. The system of claim 1, wherein the processor is configured to at least partially present said second representation of the network on a display.

19. The system of claim 1, wherein the processor is configured to apply said second representation for controlling operation of said network.

20. The system of claim 1, wherein the processor is configured to use said second representation for one or more of:

(a) defining and selecting groups of nodes, for which internal spreading is expected to be rapid;

(b) defining and selecting paths (sets of connected links) in the network, over which spreading is expected to be rapid;

(c) acting upon and/or modifying the said selected nodes and/or links so as to improve network performance;

(d) presenting in a display said selected nodes and/or links for informing and supporting human intervention in the network'"'"'s operation.

21. A method of analyzing a network including a plurality of nodes associated and/or connected together by links, the method employing a processor coupled to a data memory, wherein the processor is configured to access a first representation of said network and associated link weight measures w in said memory,

the method comprising steps of:

(i) providing node values for the nodes and determining from the node values corresponding slope measures for links existing between the nodes, the slope measures being computed from a function of differences in node values and from the weight measures w for the links, the weight measures w being used for scaling the function of differences in node values;

(ii) selecting for at least some of the nodes one or more steepest ascent links having one or more greatest positive slope measures; and

(iii) generating a second representation corresponding to a steepest ascent graph (SAG) of the network derived from information included in the steepest ascent links.

22. The method as claimed in claim 21, wherein said slope measure are computed from a difference in node values scaled by corresponding weight measures w for the links.

23. The method of claim 21, further comprising a step of subjecting the first representation to pre-filtering for eliminating from computations a sub-set of the nodes which do not contribute to the steepest ascent graph (SAG), for reducing a computational load on the processor.

24. The method of claim 21, further comprising a step of subjecting the steepest ascent graph (SAG) to post-filtering to remove links of the steepest ascent graph (SAG) which are irrelevant to determining operation of the network.

25. The method of claim 21, where said first representation is a matrix representation of the network, the method further comprising a step of computing the node values by calculating the principal Eigenvector of the matrix representation, the matrix representation including the link weight measures w.

26. The method of claim 21, further comprising steps of:

determining the weight measures w for links in the network, and

mapping a topology of the network to an adjacency matrix A describing the network, wherein A_{i, j}=w(i, j) when a link exists between a node i and a node j, and wherein A_{i, j}=0 when no link exists between a node i and a node j.

27. The method of claim 26, further comprising a step of computing the node values by calculating a principal Eigenvector e of the matrix A, wherein e(i) is the EVC of node i.

28. The method of claim 21, further comprising steps of:

computing the node values as Eigenvector centrality values for the nodes, and

determining, for each node g in the network, a slope measure for each link from the node g to an adjacent node h, according to a slope from the node g to the node h being computed from (EVC(h)−

EVC(g))·

P[w(g, h)], wherein EVC(h) is the Eigenvector centrality value for the node h, EVC(g) is the Eigenvector centrality value for node g, and w(g, h) is the weight measure for the link between the node g and the node h, and P is a function.

29. The method of claim 21, further comprising a step of generating in said processor said second representation to set a pointer from each node i to its neighbor j having a steepest ascent link from the node i.

30. The method of claim 29, further comprising a step of generating said second representation by setting a pointer from each node i to itself if it has no positive slope to any of its neighboring nodes.

31. The method of claim 21, further comprising a step of generating said second representation by creating a matrix Ã

representing a steepest ascent graph (SAG) of the network, wherein entries of the matrix Ã

corresponding to the steepest ascent links are set to 1, and wherein the matrix element Ã

_i,i is set to 1 if the node i has no positive slope to any one of its neighboring nodes.

32. The method of claim 31, further comprising steps of:

(a) multiplying a start vector s_i=i, wherein i is the node number, with the matrix Ã

;

(b) repeating the multiplication in (a) until the start vector s converges to a stable vector s*; and

(c) deriving the region membership of each node from the stable vector s*.

35. The method of claim 21, wherein the weight measure w is defined as 1/dist(g, h), where dist(g, h) is a distance measure between the nodes g and h.

36. The method of claim 28, wherein the function P is a monotonically increasing function in response to the weight w increasing.

37. The method of claim 21, further comprising the step of generating a data product corresponding at least partially to said second representation of the network.

38. The method of claim 21, further comprising the step of at least partially presenting said second representation of the network on a display.

39. The method of claim 21, further comprising the step of applying said second representation for controlling operation of said network.

40. The method of claim 21, further comprising the step of using said second representation for one or more of:

(a) defining and selecting groups of nodes, for which internal spreading is expected to be rapid;

(b) defining and selecting paths (sets of connected links) in the network, over which spreading is expected to be rapid;

(c) acting upon and/or modifying the said selected nodes and/or links so as to improve network performance;

(d) presenting in a display said selected nodes and/or links for informing and supporting human intervention in the network'"'"'s operation.

41. An article of manufacture, comprising:

a machine readable storage non-transitory medium; and

a program embodied on the storage non-transitory medium, configured for execution by a processor, the processor being coupled to a data memory and configured to generate, in said memory a first representation of a network including a plurality of nodes associated and/or connected together by links;

wherein execution of the program by the processor causes the processor to execute any one of the methods recited in claims 21 to 40.

33. The method of 32, further comprising steps of:

(d) identifying nodes which are local maxima of the steepest ascent graph (SAG) as center nodes;

(e) grouping the nodes into regions surrounding each identified center node;

(f) removing the center nodes and the links to the center nodes from the steepest ascent graph (SAG);

(g) identifying neighboring nodes of the center nodes as head nodes; and

(h) grouping nodes into sub-regions surrounding each identified head node, the nodes of a sub-region being linked to the head node of that sub-region in the steepest ascent graph (SAG).

34. The method of claim 33, further comprising steps of:

(o) identifying neighboring nodes of the head nodes as sub-subregion head nodes; and

(p) grouping nodes into sub-subregions surrounding each identified sub-subregion head node, the nodes of a sub-subregion being linked to the sub-subregion head node in the steepest ascent graph (SAG).