Determining connections of a network between source and target nodes in a database

Abstract

In an embodiment of the invention, a system determines connections between source and target nodes in a network by determining edges with common nodes between the source and target nodes within the network for each of one or more hops. Each determined edge links a pair of nodes in a network path between the source and target nodes. The system removes certain edges from the determined edges to produce a resulting set of edges. In particular, each removed edge is an edge that includes a node within a loop in the network or is an edge that is unconnected to another edge. The system determines connections between the source and target nodes based on the resulting set of edges. Embodiments of the present invention further include a method and computer program product for determining connections between source and target nodes in a network in substantially the same manners described above.

What is claimed is: 
     
       1. A computer-implemented method of determining connections between a source node and a target node in a network comprising:
 repeatedly determining edges with common in a network path between the source node and the target node for a predetermined number of hops, the predetermined number of hops being initially set to one hop and iteratively increased until a path connecting the source node to the target node is discovered while an early exit is requested; 
 producing a resulting set of edges by removing each edge including a node within a loop in the network and each edge that is unconnected to another edge; and 
 determining connections between the source node and the target node based on the resulting set of edges, wherein: 
 while the early exit is requested, the determining of connections determines only paths connecting the source node and the target node that have the predetermined number of hops, 
 when the early exit is not requested, the determining of connections determines all paths connecting the source node and the target node that have a number of hops that is less than or equal to a hop limit, and 
 the early exit is indicated as being requested when a hop limit parameter is set to a value less than one, the hop limit parameter indicating a value for the hop limit when the hop limit parameter is set to a value that is not less than one. 
 
     
     
       2. The computer-implemented method of  claim 1 , wherein the repeatedly determining edges further comprises:
 determining edges with common nodes between the source node and the target node within the network and including a desired date range for a connection. 
 
     
     
       3. The computer-implemented method of  claim 1 , wherein a topography of the network for determining the connections is stored in a relational database residing on hard disk storage and accessed by one or more SQL statements. 
     
     
       4. The computer-implemented method of  claim 1 , wherein the network includes a social network, and the connections between the source node and the target node represent relationships between entities within the social network. 
     
     
       5. The computer-implemented method of  claim 1 , wherein the repeatedly determining edges further comprises:
 finding all qualified edges forming a path from the source node and having the predetermined number of hops; 
 when one of a first additional condition and a second additional condition is satisfied, the first additional condition being an indication that the early exit is not requested and the predetermined number of hops is not equal to the hop limit, and the second additional condition being the indication that the early exit is requested and no discovery of a path connecting the source node to the target node, then performing: 
 finding all qualified edges forming a path from the target node and having the predetermined number of hops. 
 
     
     
       6. The computer-implemented method of  claim 1 , wherein the determining connections further comprises:
 determining second common nodes included in respective first paths from the source node formed by first edges from the resulting set of edges and included in respective second paths from the target node formed by second edges from the resulting set of edges. 
 
     
     
       7. The computer-implemented method of  claim 1 , further comprising:
 forming a set of edges that appear in at least one simple path between the source node and the target node; and 
 storing the set of edges in a table of a relational database environment, wherein 
 the producing the resulting set of edges further comprises:
 creating a list of edges to be removed, and 
 selecting edges from the set of edges that are absent from the list of edges to be removed, the selected edges being selected into a new table of the resulting set of edges. 
 
 
     
     
       8. A system of determining connections between a source node and a target node in a network comprising:
 at least one memory including a module to determine connections between the source node and the target node; and 
 at least one processor, the system being configured to:
 repeatedly determine edges with common nodes in a network path between the source node and the target node for a predetermined number of hops, the predetermined number of hops being initially set to one hop and iteratively increased until a path connecting the source node to the target node is discovered while an early exit is requested; 
 produce a resulting set of edges by removing each edge including a node within a loop in the network and each edge that is unconnected to another edge; and 
 
 determine connections between the source node and the target node based on the resulting set of edges, wherein: 
 while the early exit is requested, the determining of connections determines only paths connecting the source node and the target node that have the predetermined number of hops, 
 when the early exit is not requested, the determining of connections determines all paths connecting the source node and the target node that have a number of hops that is less than or equal to a hop limit, and 
 the early exit is indicated as being requested when a hop limit parameter is set to a value less than one, the hop limit parameter indicating a value for the hop limit when the hop limit parameter is set to a value that is not less than one. 
 
     
     
       9. The system of  claim 8 , wherein the determining edges further comprises:
 determining edges with common nodes between the source node and the target node within the network and including a desired date range for a connection. 
 
     
     
       10. The system of  claim 8 , wherein a topography of the network for determining the connections is stored in a relational database residing on hard disk storage and accessed by one or more SQL statements. 
     
     
       11. The system of  claim 8 , wherein the network includes a social network, and the connections between the source node and the target node represent relationships between entities within the social network. 
     
     
       12. The system of  claim 8 , wherein the system being configured to repeatedly determine edges further comprises the system being configured to:
 find all qualified edges forming a path from the source node and having the predetermined number of hops; 
 when one of a first additional condition and a second additional condition is satisfied, the first additional condition being an indication that the early exit is not requested and the predetermined number of hops being not equal to the hop limit, and the second additional condition being the indication that the early exit is requested and no discovery of a path connecting the source node to the target node, then:
 find all qualified edges forming a path from the target node and having the predetermined number of hops. 
 
 
     
     
       13. The system of  claim 8 , wherein the determining connections further comprises:
 determining second common nodes included in respective first paths from the source node formed by first edges from the resulting set of edges and included in respective second paths from the target node formed by second edges from the resulting set of edges. 
 
     
     
       14. The system of  claim 8 , wherein the system is further configured to:
 form a set of edges that appear in at least one simple path between the source node and the target node; and 
 store the set of edges in a table of a relational database environment, wherein 
 the system being configured to produce the resulting set of edges further comprises the system being configured to:
 create a list of edges to be removed, and 
 select edges from the resulting set of edges that are absent from the list of edges to be removed, the selected edges being selected into a new table of the resulting set of edges. 
 
 
     
     
       15. A computer program product for determining connections between a source node and a target node in a network comprising:
 a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
 repeatedly determine edges with common nodes in a network path between the source node and the target node for a predetermined number of hops, the predetermined number of hops being initially set to one hop and iteratively increased until a path connecting the source node to the target node is discovered while an early exit is requested; 
 produce a resulting set of edges by removing each edge including a node within a loop in the network and each edge that is unconnected to another edge; and 
 determine connections between the source node and the target node based on the resulting set of edges, wherein: 
 
 while the early exit is requested, the determining of connections determines only paths connecting the source node and the target node that have the predetermined number of hops, 
 when the early exit is not requested, the determining of connections determines all paths connecting the source node and the target node that have a number of hops that is less than or equal to a hop limit, and 
 the early exit is indicated as being requested when a hop limit parameter is set to a value less than one, the hop limit parameter indicating a value for the hop limit when the hop limit parameter is set to a value that is not less than one. 
 
     
     
       16. The computer program product of  claim 15 , wherein the repeatedly determining edges further comprises:
 determining edges with the common in the network path between the source node and the target node and including a desired date range for a connection. 
 
     
     
       17. The computer program product of  claim 15 , wherein the network includes a social network, and the connections between the source node and the target node represent relationships between entities within the social network. 
     
     
       18. The computer program product of  claim 15 , wherein the repeatedly determining edges further comprises:
 finding all qualified edges forming a path from the source node and having the predetermined number of hops; 
 when one of a first additional condition and a second additional condition is satisfied, the first additional condition being an indication that the early exit is not requested and the predetermined number of hops being not equal to the hop limit, and the second additional condition being the indication that the early exit is requested and no discovery of a path connecting the source node to the target node, then performing: 
 finding all qualified edges forming a path from the target node and having the predetermined number of hops. 
 
     
     
       19. The computer program product of  claim 15 , wherein the determining connections further comprises:
 determining second common nodes included in respective first paths from the source node formed by first edges from the resulting set of edges and included in respective second paths from the target node formed by second edges from the resulting set of edges. 
 
     
     
       20. The computer program product of  claim 15 , wherein the program instructions are further executable by the processor to cause the processor to:
 form a set of edges that appear in at least one simple path between the source node and the target node; and 
 store the set of edges in a table of a relational database environment, wherein 
 the producing the resulting set of edges further comprises:
 creating a list of edges to be removed, and 
 selecting edges from the set of edges that are absent from the list of edges to be removed, the selected edges being selected into a new table of the resulting set of edges.