METHODS AND APPARATUS FOR DISTRIBUTED COMMUNITY FINDING
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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.
43 Citations
68 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A 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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. 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. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
-
-
52. 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. - View Dependent Claims (53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68)
-
Specification