Deriving a nested chain of densest subgraphs from a graph

Abstract

A nested chain of densest subgraphs is derived by a computer from a given graph that has multiple vertices and edges. The two ends of each edge are assigned with respective incident weights, and each vertex is given a vertex weight. A weight balancing process is carried out by the computer to iteratively go through the edges to adjust the incident weights of each edge and the vertex weights of the vertices connected by that edge to reduce a difference between the vertex weights of the two vertices. After the balancing, the vertex weights are put in an ordered sequence according to their values, and a nested chain of densest subgraphs is derived from the ordered sequence.

What is claimed is: 
     
       1. A method of analyzing a graph having multiple vertices and edges, comprising:
 assigning incident weights to first and second ends of each edge in the graph; 
 assigning a vertex weight to each vertex in the graph; 
 initializing the incident weights of the edges and the vertex weights of the vertices; 
 performing a weight-balancing operation on the edges and vertices, including iteratively going through the edges to adjust the incident weights of each edge and the vertex weights of two vertices connected by that edge to reduce a difference between the vertex weights of the two vertices connected by that edge; 
 after the balancing operation, outputting the vertex weights in a sequence ordered according to values of the vertex weights; and 
 deriving a nested chain of densest subgraphs from the ordered sequence based on a change of the vertex weights. 
 
     
     
       2. A method as in  claim 1 , wherein the vertex weight of each vertex in the graph is a sum of all incident weights of ends of edges incident to that vertex. 
     
     
       3. A method as in  claim 2 , wherein each edge in the graph has a weight, and wherein the step of initializing set the incident weights of the first and second ends of each edge to half of the weight of the edge. 
     
     
       4. A method as in  claim 3 , wherein the weights of edges in the graph are integers. 
     
     
       5. A method as in  claim 2 , wherein the weight-balancing operation reduces a difference between vertex weights of two vertices connected by each edge while keeping the incident weights of that edge not smaller than 0. 
     
     
       6. A method as in  claim 1 , wherein the step of deriving finds a densest subgraph by identifying a vertex weight in the sequence that is not equal to a next vertex weight in the sequence. 
     
     
       7. A method as in  claim 1 , wherein the vertices of the graph represent web pages. 
     
     
       8. A method as in  claim 1 , wherein the graph models a social network, and the vertices of the graph represent persons in the social network. 
     
     
       9. A non-transitory computer readable medium storing computer-executable instructions for analyzing a graph with multiple vertices and edges, the computer-executable instructions upon execution causing a system to perform steps of:
 assigning incident weights to first and second ends of each edge in the graph; 
 assigning a vertex weight to each vertex in the graph, the vertex weight of each vertex being a sum of all incident weights of ends of edges incident to that vertex; 
 initializing the incident weights of the edges and the vertex weights of the vertices; 
 performing a weight-balancing operation on the edges and vertices, including iteratively going through the edges to adjust the incident weights of each edge and the vertex weights of two vertices connected by that edge to reduce a difference between the vertex weights of the two vertices connected by that edge; 
 after the balancing operation, outputting the vertex weights in a sequence ordered according to values of the vertex weights; and 
 identifying a nested chain of densest subgraphs from the ordered sequence based on a change of the vertex weights. 
 
     
     
       10. A non-transitory computer readable medium as in  claim 9 , wherein each edge of the graph has a weight, and the step of initializing sets the incident weights of the first and second ends of each edge to half of the weight of the edge. 
     
     
       11. A non-transitory computer readable medium as in  claim 10 , wherein the weight-balancing operation reduces a difference between vertex weights of two vertices connected by each edge while keeping the incident weights of that edge not smaller than 0. 
     
     
       12. A non-transitory computer readable medium as in  claim 11 , wherein the weights of edges in the graph are integers. 
     
     
       13. A non-transitory computer readable medium as in  claim 9 , wherein the step of deriving finds a densest subgraph by identifying a vertex weight in the sequence that is not equal to a next vertex weight in the sequence. 
     
     
       14. A non-transitory computer readable medium as in  claim 9 , wherein the vertices of the graph represent web pages. 
     
     
       15. A non-transitory computer readable medium as in  claim 9 , wherein the graph models a social network, and the vertices of the graph represent persons in the social network.