COMMUNITY SEARCH ALGORITHM BASED ON K-KERNEL

摘要

A community search algorithm based on a k-kernel comprises: generating a maximum spanning tree (MST) for a map; preprocessing the maximum spanning tree (MST); finding a subtree connected to all query nodes from the maximum spanning tree (MST); and searching to obtain a subtree comprising the query nodes, and returning a maximum K-kernel. By means of the algorithm, the k-kernel comprising a designated node can be found in the time complexity O(T), the value of k is the maximum, and T is the size of a community to be searched for.