Efficient egonet computation in a weighted directed graph
First Claim
1. A computer program product executable in a computer recordable storage medium for computing specified information pertaining to respective nodes of a weighted directed graph, wherein the graph comprises multiple nodes and edges, each edge extending between two nodes and having a weight, the computer program product comprising:
- instructions for selectively processing each edge of the directed graph to generate a forward edge and reverse edge that corresponds to each edge, wherein the forward edge and reverse edge corresponding to a given edge both extend between the same two nodes as the given edge;
instructions for selectively processing the forward edges and reverse edges to generate multiple indirect edges, wherein each indirect edge comprises two edge components, and has two ends respectively associated with different nodes;
instructions for specifying one node associated with each forward edge, one node associated with each reverse edge, and one node associated with each indirect edge to be the key node of its respective associated edge;
instructions for placing all the forward, reverse and indirect edges that have the same particular node as their respective key nodes into a group; and
instructions for selectively processing all the forward, reverse and indirect edges of the group to provide specified information pertaining to a particular egonet of the graph, wherein the particular node is the egonode of the particular egonet.
0 Assignments
0 Petitions
Accused Products
Abstract
An embodiment of the invention pertains to a weighted directed graph comprising multiple nodes and edges that each extends between two nodes. The embodiment includes processing edges to generate a forward and reverse edge corresponding to each edge. Forward and reverse edges are processed to generate indirect edges, each comprising two edge components, and extending between two nodes. One node associated with each forward edge, each reverse edge, and each indirect edge is selected to be the key node of its associated edge. All forward, reverse and indirect edges having a particular node as their respective key nodes are placed into a group. All edges of the group are then selectively processed to provide information pertaining to an egonet of the graph that has the particular node as its egonode.
19 Citations
9 Claims
-
1. A computer program product executable in a computer recordable storage medium for computing specified information pertaining to respective nodes of a weighted directed graph, wherein the graph comprises multiple nodes and edges, each edge extending between two nodes and having a weight, the computer program product comprising:
-
instructions for selectively processing each edge of the directed graph to generate a forward edge and reverse edge that corresponds to each edge, wherein the forward edge and reverse edge corresponding to a given edge both extend between the same two nodes as the given edge; instructions for selectively processing the forward edges and reverse edges to generate multiple indirect edges, wherein each indirect edge comprises two edge components, and has two ends respectively associated with different nodes; instructions for specifying one node associated with each forward edge, one node associated with each reverse edge, and one node associated with each indirect edge to be the key node of its respective associated edge; instructions for placing all the forward, reverse and indirect edges that have the same particular node as their respective key nodes into a group; and instructions for selectively processing all the forward, reverse and indirect edges of the group to provide specified information pertaining to a particular egonet of the graph, wherein the particular node is the egonode of the particular egonet. - View Dependent Claims (2, 3, 4, 5)
-
-
6. Apparatus for computing specified information pertaining to respective nodes of a weighted directed graph, wherein the graph comprises multiple nodes and graph edges, each graph edge extending between two nodes and having a weight, the apparatus comprising:
-
processing means for selectively processing each edge of the directed graph to generate a forward edge and reverse edge that corresponds to each edge, wherein the forward edge and reverse edge corresponding to a given edge both extend between the same two nodes as the given edge; processing means for selectively processing the forward edges and reverse edges to generate multiple indirect edges, wherein each indirect edge comprises two edge components, and has two ends respectively associated with different nodes; processing means for specifying one node associated with each forward edge, one node associated with each reverse edge, and one node associated with each indirect edge to be the key node of its respective associated edge; processing means for placing all the forward, reverse and indirect edges that have the same particular node as their respective key nodes into a group; and processing means for selectively processing all the forward, reverse and indirect edges of the group to provide specified information pertaining to a particular egonet of the graph, wherein the particular node is the egonode of the particular egonet. - View Dependent Claims (7, 8, 9)
-
Specification