规模受限的影响力社区搜索

杜明; 宋嘉祎; 周军锋

doi:10.12263/DZXB.20220538

您当前的位置：

首页 >

文章列表页 >

规模受限的影响力社区搜索

学术论文 | 更新时间：2025-12-08

- 规模受限的影响力社区搜索
- Size-Constrained Influential Community Search
- 电子学报 2023年51卷第5期页码：1207-1214
- 作者机构：
  
  东华大学计算机科学与技术学院，上海 201620
- 作者简介：
  
  [ "杜明　男，黑龙江鸡西人，博士，东华大学副教授，主要研究方向为图数据处理技术，自然语言处理等. E-mail: duming@dhu.edu.cn" ]
  [ "宋嘉祎　男，1997年9月出生于上海市.东华大学计算机科学与技术学院硕士研究生，主要研究方向为社区挖掘技术.E-mail: sshin_song@163.com" ]
  [ "周军锋（通讯作者）　男，陕西西安人，博士，东华大学教授，博士生导师，主要研究方向为图数据处理技术、推荐系统关键技术等." ]
- 基金信息：
  
  上海市自然基金项目(20ZR1402700);国家自然基金项目(61472339;61873337)
- DOI：10.12263/DZXB.20220538
  中图分类号： O157.5;TP301
- 收稿：2022-08-29，
  
  修回：2022-09-29，
  
  纸质出版：2023-05-25
- 稿件说明：
移动端阅览
杜明,宋嘉祎,周军锋.规模受限的影响力社区搜索[J].电子学报,2023,51(05):1207-1214.

DU Ming,SONG Jia-yi,ZHOU Jun-feng.Size-Constrained Influential Community Search[J].ACTA ELECTRONICA SINICA,2023,51(05):1207-1214.
杜明,宋嘉祎,周军锋.规模受限的影响力社区搜索[J].电子学报,2023,51(05):1207-1214. DOI： 10.12263/DZXB.20220538.

DU Ming,SONG Jia-yi,ZHOU Jun-feng.Size-Constrained Influential Community Search[J].ACTA ELECTRONICA SINICA,2023,51(05):1207-1214. DOI： 10.12263/DZXB.20220538.

摘要

社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前，大部分已有社区搜索方法主要关注社区的结构，没有考虑到特定应用中资源受限的情况，且忽略了社区的属性特征，无法满足用户对社区搜索的个性化要求.针对该问题，本文提出了规模受限的影响力社区搜索（Size-Constrained Influential Community search，SCIC），设计了基于深度优先搜索的基础算法，在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法，用于减少冗余计算，加速枚举过程.在10个不同规模的数据集上进行实验，实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法，同时，本文提出的优化算法能够显著提升搜索效率，将响应时间缩减至基础算法的1%.

Abstract

Community search is used to find a densely connected subgraph containing the given query vertex. Currently

most existing community search approaches do not consider the resource constraints and the attributes of the community

and they mainly focus on the structure of the community and cannot meet the personalized demands for users' community search. For this problem

we propose size-constrained influential community search (SCIC). We design a baseline enumeration algorithm based on depth-first search. Further

we show three optimization techniques to reduce the redundant computation and accelerate the enumeration procedure

including node preprocessing

pruning rules and greedy strategies. The experimental results on 10 real datasets with different sizes demonstrate that comparing with the existing algorithms

our baseline enumeration algorithm has better performance on community size and influence score. At the same time

the experimental results also show that our optimized algorithm can significantly improve the search efficiency and shorten the response time to 1% comparing with the baseline enumeration algorithm.

关键词

Keywords

references

MAURO S , ARISTIDES G . The community-search problem and how to plan a successful cocktail party [C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York : ACM , 2010 : 939 - 948 .

MA Y , YUAN Y , ZHU F , et al . Who should be invited to my party: A size-constrained k -core problem in social networks [J]. Journal of Computer Science and Technology , 2019 , 34 ( 1 ): 170 - 184 .

FANG Y , HUANG X , QIN L , et al . A survey of community search over big graphs [J]. The VLDB Journal , 2020 , 29 ( 1 ): 353 - 392 .

WU Y , ZHAO J , SUN R , et al . Efficient personalized influential community search in large networks [J]. Data Science and Engineering , 2021 , 6 ( 3 ): 310 - 322 .

LUO W , ZHOU X , YANG J , et al . Efficient approaches to top- r influential community search [J]. IEEE Internet of Things Journal , 2021 , 8 ( 16 ): 12650 - 12657 .

FANG Y , YANG Y , ZHANG W , et al . Effective and efficient community search over large heterogeneous information networks [J]. Proceedings of the VLDB Endowment , 2020 , 13 ( 6 ): 854 - 867 .

AL-BAGHDADI A , LIAN X . Topic-based community search over spatial-social networks [J]. Proceedings of the VLDB Endowment , 2020 , 13 ( 12 ): 2104 - 2117 .

LIU B , ZHANG F , ZHANG W , et al . Efficient community search with size constraint [C]// 2021 IEEE 37th International Conference on Data Engineering (ICDE) . Piscataway : IEEE , 2021 : 97 - 108 .

YAO K , CHANG L . Efficient size-bounded community search over large networks [J]. Proceedings of the VLDB Endowment , 2021 , 14 ( 8 ): 1441 - 1453 .

FANG Y , CHENG R , LUO S , et al . Effective community search for large attributed graphs [J]. Proceedings of the VLDB Endowment , 2016 , 9 ( 12 ): 1233 - 1244 .

CHEN C , ZHANG M , SUN R , et al . Locating pivotal connections: The K-truss minimization and maximization problems [J]. World Wide Web , 2022 , 25 ( 2 ): 899 - 926 .

LI C , ZHANG F , ZHANG Y , et al . Efficient progressive minimum k -core search [J]. Proceedings of the VLDB Endowment , 2019 , 13 ( 3 ): 362 - 375 .

BATAGELJ V , ZAVERSNIK M . An O ( m ) algorithm for cores decomposition of networks [J/OL]. CoRR , 2003 . http://arxiv.org/abs/cs.DS/0310049 http://arxiv.org/abs/cs.DS/0310049 .

LI R , QIN L , YU J , et al . Influential community search in large networks [J]. Proceedings of the VLDB Endowment , 2015 , 8 ( 5 ): 509 - 520 .

LIU Q , ZHU Y , ZHAO M , et al . VAC: Vertex-centric attributed community search [C]// 2020 IEEE 36th International Conference on Data Engineering(ICDE) . Dallas : IEEE , 2020 : 937 - 948 .

XIE X , SONG M , LIU C , et al . Effective influential community search on attributed graph [J]. Neurocomputing , 2021 , 444 : 111 - 125 .

ERDŐS P , PACH J , POLLACK R , et al . Radius, diameter, and minimum degree [J]. Journal of Combinatorial Theory , Series B, 1989 , 47 ( 1 ): 73 - 79 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于图组合优化的高效社区搜索

属性网络中结合用户偏好的社区搜索和离群点检测

属性网络中相似性增强随机游走的多社区搜索