发明名称 |
METHOD AND APPARATUS FOR DISTRIBUTED COMMUNITY FINDING |
摘要 |
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 presented. Instead of partitioning the graph into separate subgraphs from top to bottom we propose a local algorithm (communities of each vertex) to the top which allows overlapping of communities. The performance of an algorithm on synthetic randomly generated graphs and real-world networks is used to benchmark other methods. A 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. |
申请公布号 |
WO2006121575(B1) |
申请公布日期 |
2007.12.21 |
申请号 |
WO2006US14160 |
申请日期 |
2006.04.11 |
申请人 |
MUNTZ, ALICE;REZAEI, BEHNAM ATTARAN |
发明人 |
MUNTZ, ALICE;REZAEI, BEHNAM ATTARAN |
分类号 |
G06F7/00 |
主分类号 |
G06F7/00 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|