基于位置的稀疏群体查询

doi:10.3778/j.issn.1673-9418.2008099

摘要/Abstract

摘要：

在基于位置的社交网络中，找到一个特殊的群体/社区是非常重要的。现在的研究都集中于寻找群体之间关系紧密的密集子图。相对于紧密的群体/子图，对于稀疏群的研究少之又少。虽然现有工作开始研究稀疏群体查询问题，但是还没有研究基于位置的稀疏群体查询问题，而基于位置的服务在现实生活中有很多需求。因此，研究基于位置的稀疏群查询的问题变得有研究价值。基于位置的稀疏群体查询是为了找到一群用户，不仅用户之间满足一定的稀疏性（即用户之间的社交距离大于[k]），且最小化用户到查询位置的距离和。针对这个问题，首先提出基于c-邻居的基本处理算法（简称baseline），其主要利用存储的c-邻居信息以及距离剪枝来帮助快速获得查询结果。但是baseline算法的空间消耗太大，且在稀疏阈值参数[k>c]时查询效率不高。为了解决这些问题，进一步提出基于c-邻居和反向c-邻居的查询优化算法（简称ICN），不仅利用存储的c-邻居且利用反向c-邻居信息来处理参数[k>c]的情况，从而快速获得查询结果。实验结果和理论表明，提出的两种查询处理方法是有效的和正确的。

关键词: 基于位置的社交网络图, 稀疏群, c-邻居, 距离剪枝

Abstract:

Compared with the dense group/subgraph, there are few studies on tenuous groups. Although the existing work has begun to study the tenuous population query, geo-socially tenuous group query has not been studied, and location-based services have a lot of demands in real life. Therefore, it becomes valuable to study the geo-socially tenuous group query. Geo-socially tenuous group query is to find a group of users, which not only satisfies a certain sparsity between users (i.e. the social distance between users is greater than [k]), but also minimizes the distance between users and the query location. To address this problem, this paper first proposes a basic processing algorithm based on c-neighbor (baseline), which uses stored c-neighbor information and distance pruning to help obtain query results quickly. However, the basic processing algorithm based on c-neighbor (baseline) uses too much space and the query efficiency is not high when parameter [k>c]. To solve these problems, a query optimization algorithm based on c-neighbor and reverse c-neighbor (ICN) is proposed, which not only utilizes stored c-neighbor information but also reverse c-neighbor information to effectively filter out invalid users and obtain query results quickly. The experimental results and theory show that the proposed two query processing methods are effective and correct.

Key words: location-based social network graph, tenuous group, c-neighbor, distance pruning

李娜，朱怀杰，刘威，印鉴. 基于位置的稀疏群体查询[J]. 计算机科学与探索, 2021, 15(11): 2151-2160.

LI Na, ZHU Huaijie, LIU Wei, YIN Jian. Geo-Socially Tenuous Group Query[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2151-2160.

参考文献

[1] XIE J R, KELLEY S, SZYMANSKI B K. Overlapping com-munity detection in networks: the state-of-the-art and com-parative study[J]. ACM Computing Surveys, 2013, 45(4): 1-35.
[2] ZHU Q J, HU H B, XU C, et al. Geo-social group queries with minimum acquaintance constraints[J]. The VLDB Jour-nal, 2017, 26(5): 709-727.
[3] SHUAI H H, YANG D N, YU P S, et al. Willingness optimi-zation for social group activity[J]. Proceedings of the VLDB Endowment, 2013, 7(4): 1035-1045.
[4] SHEN C Y, HUANG L H, YANG D N, et al. On finding socially tenuous groups for online social networks[C]//Pro-ceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, Aug 13-17, 2017. New York: ACM, 2017: 415-424.
[5] LI W T. Finding tenuous groups in social networks[C]//Pro-ceedings of the 2018 IEEE International Conference on Data Mining Workshops, Singapore, Nov 17-20, 2018. Piscataway: IEEE, 2018: 284-291.
[6] CHEN T L, SINGH P, BASSLER K E. Network community detection using modularity density measures[J]. Journal of Statistical Mechanics Theory and Experiment, 2018(5): 1-17.
[7] GUIMERA R, AMARAL L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028): 895-900.
[8] VINCENT D B, JEAN-LOUP G, RENAUD L, et al. Fast unfolding of communities in large networks[J]. Journal of Sta-tistical Mechanics: Theory and Experiment, 2008, 10: P1008.
[9] SHEN C Y, YANG D N, HUANG L H, et al. Socio-spatial group queries for impromptu activity planning[J]. IEEE Tran-sactions on Knowledge and Data Engineering, 2016, 28(1): 196-210.
[10] YANG D N, SHEN C Y, LEE W C, et al. On socio-spatial group query for location-based social networks[C]//Proceed-ings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, Aug 12-16, 2012. New York: ACM, 2012: 949-957.
[11] HUANG X, LAKSHMANAN L V S. Attribute truss com-munity search[J]. arXiv:1609.00090, 2016.
[12] FANG Y X, WANG Z R, CHENG R, et al. Effective and efficient community search over large directed graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(11): 2093-2107.
[13] HUANG X, CHENG H, QIN L, et al. Querying k-truss com-munity in large and dynamic graphs[C]//Proceedings of the 2014 International Conference on Management of Data, Snowbird, Jun 22-27, 2014. New York: ACM, 2014: 1311-1322.
[14] XIONG Y, ZHU Y Y. Abnormal group mining: framework and applications[J]. Big Data Research, 2015, 1(2): 58-69.
熊赟, 朱扬勇. 特异群组挖掘: 框架与应用[J]. 大数据, 2015, 1(2): 58-69.
[15] CHEN Y L, CHEN M S, YU P S. Ensemble of diverse spar-sifications for link prediction in large-scale networks[C]//Proceedings of the 2015 IEEE International Conference on Data Mining, Atlantic City, Nov 14-17, 2015. Washington:IEEE Computer Society, 2015: 51-60.
[16] JOHNSON D S, YANNAKAKIS M, PAPADIMITRIOU C H. On generating all maximal independent sets[J]. Information Processing Letters, 1988, 27(3): 119-123.