Methods and apparatus for distributed community finding

• US 8,838,605 B2
• Filed: 10/25/2012
• Issued: 09/16/2014
• Est. Priority Date: 05/10/2005
• Status: Active Grant

• Current Assignee: NetSeer, Inc. (Inuvo, Inc.)
• Original Assignee: NetSeer, Inc. (Inuvo, Inc.)
• Inventors: Muntz, Alice Hwei-Yuan Meng, Rezaei, Behnam Attaran
• Primary Examiner(s): Pulliam, Christyann
• Assistant Examiner(s): Mahmood, Rezwanul
• Application Number:
  US13/660,940
• Publication Number:
  US 20130046797A1
• Time in Patent Office: 691 Days
• Field of Search: 707/805, 707/923, 707/930, 707/736, 707/924, 707/937
• US Class Current: 707/737
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: Y10S 707/93 intellectual property analysis
• CPC Class Codes: Y10S 707/937 intellectual property searching
• CPC Class Codes: Y10S 707/959 Network

Abstract

Methods and apparatus for a new approach to the problem of finding communities in complex networks relating to a social definition of communities and percolation are disclosed. Instead of partitioning the graph into separate subgraphs from top to bottom a local algorithm (communities of each vertex) allows overlapping of communities. The performance of an algorithm on synthetic, randomly-generated graphs and real-world networks is used to benchmark this method against others. An heuristic is provided to generate a list of communities for networks using a local community finding algorithm. Unlike diffusion based algorithms, The provided algorithm finds overlapping communities and provides a means to measure confidence in community structure. It features locality and low complexity for exploring the communities for a subset of network nodes, without the need for exploring the whole graph.

Claims

1. A method comprising:

parsing patent data to generate a set of nodes;

selecting at least one node of the set of nodes;

determining initial links from meta data associated with the patent data for the at least one node;

creating links among the set of nodes based on the metadata;

identifying a set of seed nodes;

determining a community structure for the set of seed nodes, the community structure including a plurality of communities; and

assigning concepts to the plurality of communities,

wherein determining the community structure comprises;

initiating a percolation message from a source node of a linked network, the linked network comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

propagating the percolation message through the linked network, wherein propagating the percolation message through the linked network comprises;

transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

transmitting a response to the source node from each node that receives the percolation message;

collecting each response to the percolation message at the source node; and

storing a list of nodes that transmitted the response at the source node.

2. The method of claim 1, further comprising refining weights of the plurality of communities and modifying the community structure.

3. The method of claim 1, further comprising updating links and adding nodes to the set of nodes based on the community structure.

4. The method of claim 1, further comprising at least one of:

finding a patent landscape from the community structure;

identifying the patent landscape based on different node types and identifying gaps in the patent landscape;

monitoring the patent landscape over time; and

monitoring the patent landscape for competitors.

5. The method of claim 1, wherein the initial links are selected from the group consisting of links between patents, links between inventors, links between examiners, links between authors, links between corporations, and links to papers.

6. The method of claim 1, further comprising adding semantic links between papers and patents.

7. The method of claim 1, further comprising producing a report based on user requirements.

8. The method of claim 7, further comprising modifying the report by user input.

9. The method of claim 8, wherein the user input comprises Boolean filters.

10. The method of claim 1, wherein the set of seed nodes is selected from the group consisting of keywords, description, related patent numbers, a company, a person, prior art and topic.

12. The method of claim 1 further comprising:

specifying a weight for each link; and

determining a weight for each of the plurality of communities.

13. The method of claim 12, further comprising modifying the weight for each link, and determining a modified weight for each of the plurality of communities.

14. The method of claim 1 further comprising:

specifying a weight for each node; and

determining a weight for each of the plurality of communities.

15. The method of claim 14, further comprising modifying the weight for each node, and determining a modified weight for each of the plurality of communities.

11. A method comprising:

parsing patent data to generate a set of nodes;

selecting at least one node of the set of nodes;

determining initial links from metadata associated with the patent data for the at least one node;

creating links among the set of nodes based on the metadata;

identifying a set of seed nodes;

determining a community structure for the set of seed nodes, the community structure including a plurality of communities; and

assigning concepts to the plurality of communities,

wherein determining the community structure comprises;

initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes, wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

locating phase transition points in the plot; and

determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

16. A non-transitory program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method, the method comprising:

parsing patent data to generate a set of nodes;

selecting at least one node of the set of nodes;

determining initial links from meta data associated with the patent data for the at least one node;

creating links among the set of nodes based on the metadata;

identifying a set of seed nodes;

determining a community structure for the set of seed nodes, the community structure including a plurality of communities; and

assigning concepts to the plurality of communities,

wherein determining the community structure comprises;

initiating a percolation message from a source node of a linked network, the linked network comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

propagating the percolation message through the linked network, wherein propagating the percolation message through the linked network comprises;

transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

transmitting a response to the source node from each node that receives the percolation message;

collecting each response to the percolation message at the source node; and

storing a list of nodes that transmitted the response at the source node.

17. The program storage device of claim 16, further comprising refining weights of the plurality of communities and modifying the community structure.

18. The program storage device of claim 16, further comprising updating links and adding nodes to the set of nodes based on the community structure.

19. The program storage device of claim 16, further comprising at least one of:

finding a patent landscape from the community structure;

identifying the patent landscape based on different node types and identifying gaps in the patent landscape;

monitoring the patent landscape over time; and

monitoring the patent landscape for competitors.

20. The program storage device of claim 16, wherein the initial links are selected from the group consisting of links between patents, links between inventors, links between examiners, links between authors, links between corporations, and links to papers.

21. The program storage device of claim 16, further comprising adding semantic links between papers and patents.

22. The program storage device of claim 16, further comprising producing a report based on user requirements.

23. The program storage device of claim 22, further comprising modifying the report by user input.

24. The program storage device of claim 23, wherein the user input comprises Boolean filters.

25. The program storage device of claim 16, wherein the set of seed nodes is selected from the group consisting of keywords, description, related patent numbers, a company, a person, prior art and topic.

27. The program storage device of claim 16 further comprising:

specifying a weight for each link; and

determining a weight for each of the plurality of communities.

28. The program storage device of claim 27, further comprising modifying the weight for each link, and determining a modified weight for each of the plurality of communities.

29. The program storage device of claim 16 further comprising:

specifying a weight for each node; and

determining a weight for each of the plurality of communities.

30. The program storage device of claim 29, further comprising modifying the weight for each node, and determining a modified weight for each of the plurality of communities.

26. A non-transitory program device readable by a machine, embodying a program of instructions executable by the machine to perform a method, the method comprising:

parsing patent data to generate a set of nodes;

selecting at least one node of the set of nodes;

determining initial links from meta data associated with the patent data for the at least one node;

creating links among the set of nodes based on the metadata;

identifying a set of seed nodes;

determining a community structure for the set of seed nodes, the community structure including a plurality of communities; and

assigning concepts to the plurality of communities,

wherein determining the community structure comprises;

initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes, wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

locating phase transition points in the plot; and

determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

31. An apparatus comprising:

memory;

one or more computers configured to;

parse patent data to generate a set of nodes;

select at least one node of the set of nodes;

determine initial links from meta data associated with the patent data for the at least one node;

create links among the set of nodes based on the metadata;

identify a set of seed nodes;

determine a community structure for the set of seed nodes, the community structure including a plurality of communities; and

assign concepts to the plurality of communities,

wherein determining the community structure comprises;

initiating a percolation message from a source node of a linked network, the linked network comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

propagating the percolation message through the linked network, wherein propagating the percolation message through the linked network comprises;

transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

transmitting a response to the source node from each node that receives the percolation message;

collecting each response to the percolation message at the source node; and

storing a list of nodes that transmitted the response at the source node.

32. The apparatus of claim 31, wherein the one or more computers are further configured to refine weights of the plurality of communities and modifying the community structure.

33. The apparatus of claim 31, wherein the one or more computers are further configured to update links and add nodes to the set of nodes based on the community structure.

34. The apparatus of claim 31, wherein the one or more computers are further configured to:

find a patent landscape from the community structure;

identify the patent landscape based on different node types and identifying gaps in the patent landscape;

monitor the patent landscape over time; and

monitor the patent landscape for competitors.

35. The apparatus of claim 31, wherein the initial links are selected from the group consisting of links between patents, links between inventors, links between examiners, links between authors, links between corporations, and links to papers.

36. The apparatus of claim 31, wherein the one or more computers are further configured to add semantic links between papers and patents.

37. The apparatus of claim 31, wherein the one or more computers are further configured to produce a report based on user requirements.

38. The apparatus of claim 37, wherein the one or more computers are further configured to modify the report by user input.

39. The apparatus of claim 38, wherein the user input comprises Boolean filters.

40. The apparatus of claim 31, wherein the set of seed nodes is selected from the group consisting of keywords, description, related patent numbers, a company, a person, prior art and topic.

42. The apparatus of claim 31 wherein the one or more computers are further configured to:

specify a weight for each link; and

determine a weight for each of the plurality of communities.

43. The apparatus of claim 42, wherein the one or more computers are further configured to modify the weight for each link, and determine a modified weight for each of the plurality of communities.

44. The apparatus of claim 31 wherein the one or more computers are further configured to:

specify a weight for each node; and

determine a weight for each of the plurality of communities.

45. The apparatus of claim 44, wherein the one or more computers are further configured to modify the weight for each node, and determine a modified weight for each of the plurality of communities.

41. An apparatus comprising:

memory;

one or more computers configured to;

parse patent data to generate a set of nodes;

select at least one node of the set of nodes;

determine initial links from meta data associated with the patent data for the at least one node;

create links among the set of nodes based on the metadata;

identify a set of seed nodes;

determine a community structure for the set of seed nodes, the community structure including a plurality of communities; and

assign concepts to the plurality of communities,

wherein determining the community structure comprises;

initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes, wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

locating phase transition points in the plot; and

determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

46. An apparatus comprising:

means for parsing patent data to generate a set of nodes;

means for selecting at least one node of the set of nodes;

means for determining initial links from meta data associated with the patent data for the at least one node;

means for creating links among the set of nodes based on the metadata;

means for identifying a set of seed nodes;

means for determining a community structure for the set of seed nodes, the community structure including a plurality of communities; and

means for assigning concepts to the plurality of communities,

wherein the means for determining the community structure comprises;

means for initiating a percolation message from a source node of a linked network, the linked network comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

means for propagating the percolation message through the linked network, wherein propagating the percolation message through the linked network comprises;

means for transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

means for transmitting a response to the source node from each node that receives the percolation message;

means for collecting each response to the percolation message at the source node; and

means for storing a list of nodes that transmitted the response at the source node.

47. The apparatus of claim 46, further comprising means for refining weights of the plurality of communities and modifying the community structure.

48. The apparatus of claim 46, further comprising means for updating links and adding nodes to the set of nodes based on the community structure.

49. The apparatus of claim 46, further comprising at least one of:

means for finding a patent landscape from the community structure;

means for identifying the patent landscape based on different node types and identifying gaps in the patent landscape;

means for monitoring the patent landscape over time; and

means for monitoring the patent landscape for competitors.

50. The apparatus of claim 46, wherein the initial links are selected from the group consisting of links between patents, links between inventors, links between examiners, links between authors, links between corporations, and links to papers.

51. The apparatus of claim 46, further comprising means for adding semantic links between papers and patents.

52. The apparatus of claim 46, further comprising means for producing a report based on user requirements.

53. The apparatus of claim 52, further comprising means for modifying the report by user input.

54. The apparatus of claim 53, wherein the user input comprises Boolean filters.

55. The apparatus of claim 46, wherein the set of seed nodes is selected from the group consisting of keywords, description, related patent numbers, a company, a person, prior art and topic.

57. The apparatus of claim 46 further comprising:

means for specifying a weight for each link; and

means for determining a weight for each of the plurality of communities.

58. The apparatus of claim 57, further comprising means for modifying the weight for each link, and means for determining a modified weight for each of the plurality of communities.

59. The method of claim 46 further comprising:

means for specifying a weight for each node; and

means for determining a weight for each of the plurality of communities.

60. The apparatus of claim 59, further comprising means for modifying the weight for each node, and means for determining a modified weight for each of the plurality of communities.

56. An apparatus comprising:

means for parsing patent data to generate a set of nodes;

means for selecting at least one node of the set of nodes;

means for determining initial links from meta data associated with the patent data for the at least one node;

means for creating links among the set of nodes based on the metadata;

means for identifying a set of seed nodes;

means for determining a community structure for the set of seed nodes, the community structure including a plurality of communities; and

means for assigning concepts to the plurality of communities,

wherein determining the community structure comprises;

means for initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

means for determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

means for aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes, wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

means for plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

means for locating phase transition points in the plot; and

means for determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.