# US 2015/0091909 A1 · Systems And Methods For Distance Approximation In Graphs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0091909 A1
- Document ID: US20150091909A1
- Status: Published application
- Kind: A1
- Application number: 14/041,210
- Filed: 2013-09-30
- Published: 2015-04-02
- Earliest claimed: 2013-09-30
- Assignees: Alcatel Lucent
- Applicants: Alcatel Lucent
- Inventors: Deepak Ajwani; William S. Kennedy; Alessandra Sala; Iraj Saniee
- Web page: https://patentgrep.com/patent/US20150091909A1

## CPC

- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- G06T 11/26: Drawing of charts or graphs
- H04L 45/484: using multiple routing trees
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Systems and methods are provided for constructing a collection of one or more tree sub-graph representations of a graph including multiple interconnected nodes, where the one or more tree sub-graph representations of the graph are used to estimate the shortest distance between any two nodes of a graph. One of the features of the systems and methods disclosed herein is a methodology for the selection or designation of root nodes for constructing the collection of the one or more tree sub-graph representations. Another feature of the present disclosure is a methodology of expanding the parent nodes in a given level of the tree sub-graph representations into one or more child nodes in a successive level of the tree-graph representations based on a descending order of degree of the parent nodes.

## Claims

### Claim 1

A computer-implemented method for constructing one or more tree sub-graphs for estimating a shortest distance between a given pair of nodes of a graph having multiple interconnected nodes, the method comprising:
selecting, using a processor, one or more root nodes from the multiple interconnected nodes of the graph;
constructing, for each of at least one of the one or more root nodes, a respective multi-level tree sub-graph representing the multiple interconnected nodes of the graph in a parent-child relationship in successive levels of the multi-level tree sub-graph starting with each of the at least one of the one or more root nodes,
at least one level of the multi-level tree sub-graph including a plurality of parent nodes having respective degrees, the degree of at least one parent node in the plurality of parent nodes being higher than the degree of another parent node in the plurality of parent nodes, and,
wherein constructing the multi-level tree sub-graph further includes expanding respective ones of the plurality of parent nodes of the at least one level of the tree sub-graph into one or more respective child nodes in a successive level of the tree sub-graph based on a descending order of the degrees of the plurality of parent nodes.

### Claim 2 (depends on 1)

The method of claim 1, wherein selecting, using the processor, the one or more root nodes from the multiple interconnected nodes of the graph further comprises:
determining a node u from the graph;
determining a node v from the graph, where node v is determined as the node of the graph that is farthest away from node u of the graph; and,
selecting node v as one of the one or more root nodes.

### Claim 3 (depends on 2)

The method of claim 2, wherein determining a node u from the graph further comprises selecting a random node from the graph.

### Claim 4 (depends on 1)

The method of claim 1, wherein selecting, using the processor, the one or more root nodes from the multiple interconnected nodes of the graph further comprises:
determining a node w from the graph, where node w is determined as the node of the graph that is farthest away from a node v of the graph; and,
selecting node w as one of the one or more root nodes.

### Claim 5 (depends on 1)

The method of claim 1, wherein selecting, using the processor, the one or more root nodes from the multiple interconnected nodes of the graph further comprises:
determining a shortest distance path between a node v of the graph and a node w of the graph; and,
determining a node x from the graph as the node of the graph that is close to midway on the shortest distance path between node v of the graph and node w of the graph; and,
selecting node x as one of the one or more roots nodes.

### Claim 6 (depends on 1)

The method of claim 1, wherein selecting, using the processor, the one or more root nodes from the multiple interconnected nodes of the graph further comprises:
determining a node y from the graph as the node of the graph that has the highest degree within a predetermined distance from a node x of the graph; and,
selecting node y as one of the one or more root nodes.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
determining a respective shortest distance for the given pair of nodes from each of at least one of the respective tree sub-graphs; and,
estimating the distance between the given pair of nodes of the graph as a minimum of the determined respective shortest distances.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
determining, based on a diameter of the graph, the number of root nodes that are selected from the multiple nodes of the graph or the number of respective tree sub-graphs that are constructed.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
computing a statistical expected value of error based on estimated distances determined between the given pair of nodes using the tree sub-graphs and actual distances between the given pair of nodes computed based on the graph; and,
using the statistical expected value of error to dynamically determine the number of root nodes that are selected from the multiple nodes of the graph or the number of respective tree sub-graphs that are constructed.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
selecting at least one of the one or more root nodes based on descending order of degrees of respective ones of the multiple interconnected nodes of the graph.

### Claim 11

An apparatus configured to construct one or more tree sub-graphs data structures for estimating a shortest distance between a given pair of nodes of a graph having multiple interconnected nodes, the method comprising:
a processor;
a memory communicatively connected to the processor, the memory configured to store the one or more tree sub-graph data structures and one or more executable instructions, which, upon execution by the processor, configure the processor to:
select one or more root nodes from the multiple interconnected nodes of the graph;
construct, for each of at least one of the one or more root nodes, a respective multi-level tree sub-graph data structure representing the multiple interconnected nodes of the graph in a parent-child relationship in successive levels of the multi-level tree sub-graph data structure starting with each of the at least one of the one or more root nodes,
wherein at least one level of the multi-level tree sub-graph data structure includes a plurality of parent nodes having respective degrees, the degree of at least one parent node in the plurality of parent nodes being higher than the degree of another parent node in the plurality of parent nodes, and,
wherein the processor is further configured to construct the multi-level tree sub-graph data structure by expanding respective ones of the plurality of parent nodes of the at least one level of the tree sub-graph data structure into one or more respective child nodes in a successive level of the tree sub-graph data structure based on a descending order of the degrees of the plurality of parent nodes.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to select the one or more root nodes from the multiple interconnected nodes of the graph by:
determining a node u from the graph;
determining a node v from the graph, where node v is determined as the node of the graph that is farthest away from node u of the graph; and,
selecting node v as one of the one or more root nodes.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the one or more executable instructions further configure the processor to determine node u from the graph by selecting a random node from the graph.

### Claim 14 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to select the one or more root nodes from the multiple interconnected nodes of the graph by:
determining a node w from the graph, where node w is determined as the node of the graph that is farthest away from a node v of the graph; and,
selecting node w as one of the one or more root nodes.

### Claim 15 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to select the one or more root nodes from the multiple interconnected nodes of the graph by:
determining a shortest distance path between a node v of the graph and a node w of the graph; and,
determining a node x from the graph as the node of the graph that is close to midway on the shortest distance path between node v of the graph and node w of the graph; and,
selecting node x as one of the one or more roots nodes.

### Claim 16 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to select the one or more root nodes from the multiple interconnected nodes of the graph by:
determining a node y from the graph as the node of the graph that has the highest degree within a predetermined distance from a node x of the graph; and,
selecting node y as one of the one or more root nodes.

### Claim 17 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to:
determine a respective shortest distance for the given pair of nodes from each of at least one of the respective tree sub-graphs data structures; and,
estimate the distance between the given pair of nodes of the graph as a minimum of the determined respective shortest distances.

### Claim 18 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to:
determine, based on a diameter of the graph, the number of root nodes that are selected from the multiple nodes of the graph or the number of respective tree sub-graphs that are constructed.

### Claim 19 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to:
compute a statistical expected value of error based on estimated distances determined between the given pair of nodes using the tree sub-graphs and actual distances between the given pair of nodes computed based on the graph; and,
use the statistical expected value of error to determine the number of root nodes that are selected from the multiple nodes of the graph or the number of respective tree sub-graphs that are constructed.

### Claim 20 (depends on 11)

The apparatus of claim 11, wherein the one or more executable instructions further configure the processor to:
select at least one of the one or more root nodes based on descending order of degrees of respective ones of the multiple interconnected nodes of the graph.
