Local Community Detection Algorithm Based On Breadth-First Search

With the development of modern internet techno logy recently, more and more data are put into our mind with net structure, and community structure is an important aspect in net topology research. Find ing community structure in net is a hot topic nowadays, and many scholars have researched it. Traditional community detection methods focus on the whole net structure, which leads to high time complexity. Sometimes we need not know the who le net structure. For a core node in the net, we only want to know the coverage area, that we only want to find the local community of it. So this article puts forward a new local community detection algorithm.This article launches an algorithm which is based on max connective node, common friends count and Breadth-First Search.This new algorithm starts from original node, finds the max connective node relevant to the original node, uses breadth-first search based on nodes similarity to find local community. Finding the max connective node could avoid the situation that when the node is boundary node, which could not find the community, improves robustness. BFS could reduce time complexity to linear of edge count in the community.Put this new algorithm to four classical data-sets. The result shows that this method reduces time complexity without reducing precision, and also improves robustness.