METHODS AND APPARATUS FOR DISTRIBUTED COMMUNITY FINDING
First Claim
1. A method comprising:
- maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and
analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community.
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.
219 Citations
44 Claims
-
1. A method comprising:
-
maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method, the method comprising:
-
maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. An apparatus comprising:
-
memory; one or more computers configured to; maintain a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and analyze an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
-
-
34. An apparatus comprising:
-
means for maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and means for analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community. - View Dependent Claims (35, 36, 37, 38, 39, 40, 41, 42, 43, 44)
-
Specification