“Community search”的意思、由来-开放百科全书

Discovering communities in a network, known as community detection/discovery, is a fundamental problem in network science, which attracted much attention in the past several decades. In recent years, with the tremendous studies on big data, there is another related but different problem, called community search, which aims to find the most likely community that contains the query node, has attracted great attention from both academic and industry areas. It is a query-dependent variant of the community detection problem.

In recent years, there has been many interestings studies focusing on this novel research problem.^[1]^[2]^[3]^[4]^[5]^[6]^[7]

Main advantages

As pointed by the first work on community search^[1] published in SIGKDD'2010, many existing community detection/discovery methods consider the static community detection problem, where the graph needs to be partitioned a-priori with no reference to query nodes. While community search often focuses the most-likely communitie containing the query vertex. The main advantages of community search over community detection/discovery are listed as below:

For example, a recent work,^[8] which focuses on attributed graphs, where nodes are often associated with some attributes like keyword, and tries to find the communities, called attributed communities, which exhibit both strong structure and keyword cohesiveness. The query users are allowed to specify a query node and some other query conditions: (1) a value, k, the minimum degree for the expected communities; and (2) a set of keywords, which control the semantic of the expected communities. The communities returned can be easily interpreted by the keywords shared by all the community members. More details can be fround from.^[10]

Some recent studies^[3]^[8] have shown that, for million-scale graphs, community search often takes less than 1 second to find a well-defined community, which is generally much faster than many existing community detection/discovery methods. This also implies that, community search is more suitable for finding communities from big graphs.

Measures for community search

Community search often uses some well-defined, fundamental measures of graphs. The commonly used measures are

Note that, the minimum degree measure is also used for defining the k-core of a graph.

Among these measures, the minimum degree measure is the most popular one, and has been used in many recent studies.

References

1. ^¹²Mauro Sozio and Aristides Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '10). ACM, New York, NY, USA, 939-948. DOI=https://dx.doi.org/10.1145/1835804.1835923
2. ^¹²Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, and Wei Wang. 2013. Online search of overlapping communities. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13). ACM, New York, NY, USA, 277-288. DOI=https://dx.doi.org/10.1145/2463676.2463722
3. ^¹²Wanyun Cui, Yanghua Xiao, Haixun Wang, and Wei Wang. 2014. Local search of communities in large graphs. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD '14). ACM, New York, NY, USA, 991-1002. DOI=https://dx.doi.org/10.1145/2588555.2612179
4. ^¹Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD '14). ACM, New York, NY, USA, 1311-1322. DOI=https://dx.doi.org/10.1145/2588555.2610495
5. ^¹Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao. 2015. Influential community search in large networks. Proc. VLDB Endow. 8, 5 (January 2015), 509-520. DOI=https://dx.doi.org/10.14778/2735479.2735484
6. ^¹Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and Francesco Gullo. 2015. Efficient and effective community search. Data Min. Knowl. Discov. 29, 5 (September 2015), 1406-1433. DOI=https://dx.doi.org/10.1007/s10618-015-0422-1
7. ^¹Xin Huang, Laks V. S. Lakshmanan, Jeffrey Xu Yu, and Hong Cheng. 2015. Approximate closest community search in networks. Proc. VLDB Endow. 9, 4 (December 2015), 276-287. DOI=https://dx.doi.org/10.14778/2856318.2856323
8. ^¹²³⁴Yixiang Fang, Reynold Cheng, Siqiang Luo, Jiafeng Hu. 2016. Effective community search for large attributed graphs. Proc. VLDB Endow. 9, 12, 1233-1244.
9. ^¹Yixiang Fang, Reynold Cheng, Xiaodong Li, Siqiang Luo, Jiafeng Hu. 2017. Effective community search over large spatial graphs. Proc. VLDB Endow. 10, 6, 709-720.
10. ^¹http://i.cs.hku.hk/~yxfang/acq.html
11. ^Lijun Chang, Xuemin Lin, Lu Qin, Jeffrey Xu Yu, and Wenjie Zhang. "Index-based optimal algorithms for computing Steiner components with maximum connectivity." In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 459-474. ACM, 2015.
12. ^Jiafeng Hu, Xiaowei Wu, Reynold Cheng, Siqiang Luo, and Yixiang Fang. On minimal steiner maximum-connected subgraph queries. IEEE Transactions on Knowledge and Data Engineering 29, no. 11 (2017): 2455-2469.