Efficient egonet computation in a weighted directed graph

• US 8,694,979 B2
• Filed: 06/26/2012
• Issued: 04/08/2014
• Est. Priority Date: 06/26/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rosu, Marcel C., Tong, Hanghang
• Primary Examiner(s): Nguyen, Phillip H
• Application Number:
  US13/533,697
• Publication Number:
  US 20140067873A1
• Time in Patent Office: 651 Days
• Field of Search: 717/144, 717/156, 717/157
• US Class Current: 717/156
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

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.

Claims

1. A method 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, and the method comprises the steps of:

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;

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;

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;

placing all the forward, reverse and indirect edges that have the same particular node as their respective key nodes into a group; and

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.

2. The method of claim 1, wherein:

the forward edge corresponding to an edge has a specified source node and a specified destination node, and the reverse edge corresponding to the same edge has a source node comprising said specified destination node, and a destination node comprising said source node, of the forward edge.

3. The method of claim 1, wherein:

each forward edge and reverse edge comprises a direct edge, and each edge component of an indirect edge comprises one of said direct edges, wherein the two direct edges of a given indirect edge have a node that is common to them.

4. The method of claim 1, wherein:

each edge component of an indirect graph is selected from a set of edge components that includes forward-forward edges, forward-reverse edges, reverse-reverse edges, and reverse-forward edges, respectively.

5. The method of claim 1, wherein:

each forward edge and reverse edge comprises a direct edge, and each of said direct edges is compared with a succession of indirect edges, in order to identify edges that comprise triangle edges, incoming edges, and outgoing edges, respectively, of the particular egonet.

6. The method of claim 5, wherein:

a given edge comprises a triangle edge, if and only if it extends between two nodes that are both neighbor nodes to the egonode of the particular egonet.

7. The method of claim 1, wherein:

two map-reduce operations, each comprising a mapper and a reducer, are configured together as a first stage and a second stage, and the first stage mapper is operable to generate the forward edge and reverse edge that correspond to each graph edge.

8. The method of claim 7, wherein:

the first stage reducer is operable to generate each of the indirect edges from the forward and reverse edges.

9. The method of claim 8, wherein:

the second stage reducer computes respective edges of the particular egonet, from information pertaining to the forward, reverse and indirect edges which is supplied by the first stage reducer.

10. The method of claim 1, wherein:

said group comprises one of multiple groups of edges, wherein each group is associated with a different key node, and the edges of different groups are received by different processing components of a plurality of processing components, each processing component being operable to compute an egonet for each group of edges received thereby.

11. The method of claim 1, wherein:

computation of a k-degree egonet for a particular node, wherein K is greater than 1, includes generating a pseudo-node representing the (k−

1) degree egonet of the particular node.