DETERMINING INFLUENCE IN A NETWORK

• US 20140095689A1
• Filed: 09/28/2012
• Published: 04/03/2014
• Est. Priority Date: 09/28/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Borgs, Christian Herwarth, Chayes, Jennifer Tour, Brautbar, Michael Avraham, Lucier, Brendan James
• Granted Patent: US 9,367,879 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 10/06395 Quality analysis or management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

An influence maximization process efficiently identifies an influential set of nodes with which to seed a diffusion process using the transposition of a graph representing the network. This approach offers an acceptable tradeoff between runtime complexity and accurate approximation. In addition, using an approximation condition, the influence maximization process may be further tuned to dramatically reduce the computational complexity even more in certain circumstances while allowing a fallback to the unturned influence maximization process if the approximation condition is not satisfied.

Claims

1. A method comprising:

identifying influential nodes in a network based on degrees of individual nodes selected from a hypergraph generated from a transpose graph representing the network, wherein the transpose graph is a transposition of the directed edge-weighted graph of the network.

2. The method of claim 1 further comprising:

generating the hypergraph from the transpose graph by performing one or more randomized depth-first traversals through the transpose graph.

3. The method of claim 2 further comprising:

identifying a number of nodes visited during the one or more randomized depth-first traversals; and

terminating the depth-first traversals responsive to the number of nodes visited satisfying a traversal termination condition.

4. The method of claim 2 wherein the identified nodes are added to an edge set defining the generated hypergraph.

5. The method of claim 2 further comprising:

traversing the generated hypergraph; and

selecting from the generated hypergraph the node having the greatest degree as compared to other nodes in the generated hypergraph.

6. The method of claim 5 further comprising:

removing the selected node and incident edges of the selected node from the generated hypergraph.

7. The method of claim 6 further comprising:

outputting the removed nodes as the influential nodes of the network.

8. The method of claim 6 further comprising:

limiting the number of output nodes according to hypergraph node selection condition.

9. One or more computer-readable storage media encoding computer-executable instructions for executing on a computer system a computer process, the computer process comprising:

identifying influential nodes in a network based on degrees of individual nodes selected from a hypergraph generated from a transpose graph representing the network.

10. The one or more computer-readable storage media of claim 9 wherein the computer process further comprises:

generating a directed edge-weighted graph of the network, wherein the transpose graph is a transposition of the directed edge-weighted graph of the network.

11. The one or more computer-readable storage media of claim 9 wherein the computer process further comprises:

generating the hypergraph from the transpose graph by performing one or more randomized depth-first traversals through the transpose graph.

12. The one or more computer-readable storage media of claim 11 wherein the computer process further comprises:

identifying a number of nodes visited during the one or more randomized depth-first traversals; and

terminating the depth-first traversals responsive to the number of nodes visited satisfying a traversal termination condition.

13. The one or more computer-readable storage media of claim 11 wherein the identified nodes are added to an edge set defining the generated hypergraph.

14. The one or more computer-readable storage media of claim 11 wherein the computer process further comprises:

traversing the generated hypergraph; and

selecting from the generated hypergraph the node having the greatest degree as compared to other nodes in the generated hypergraph.

15. The one or more computer-readable storage media of claim 14 wherein the computer process further comprises:

removing the selected node and incident edges of the selected node from the generated hypergraph.

16. The one or more computer-readable storage media of claim 15 wherein the computer process further comprises:

outputting the removed nodes as the influential nodes of the network.

17. The one or more computer-readable storage media of claim 16 wherein the computer process further comprises:

limiting the number of output nodes according to hypergraph node selection condition.

18. A system comprising:

an influence evaluation system configured to identify influential nodes in a network based on degrees of individual nodes selected from a hypergraph generated from a transpose graph representing the network.

19. The system of claim 18 further comprising:

a hypergraph builder configured to generate the hypergraph from the transpose graph by performing one or more randomized depth-first traversals through the transpose graph.

20. The system of claim 18 further comprising:

a seed set builder configured to select from the generated hypergraph nodes having the greatest degree as compared to other nodes in the generated hypergraph, the selected nodes being designated as influential nodes in the network.