Size-Constrained Influential Community Search

DU Ming; SONG Jia-yi; ZHOU Jun-feng

doi:10.12263/DZXB.20220538

您当前的位置：

首页 >

文章列表页 >

Size-Constrained Influential Community Search

PAPERS | 更新时间：2025-12-08

- Size-Constrained Influential Community Search
- ACTA ELECTRONICA SINICA Vol. 51, Issue 5, Pages: 1207-1214(2023)
- 作者机构：
  
  东华大学计算机科学与技术学院，上海 201620
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of Shanghai(20ZR1402700);National Natural Science Foundation of China(61472339;61873337)
- DOI：10.12263/DZXB.20220538
  CLC： O157.5;TP301
- Received：29 August 2022，
  
  Revised：2022-09-29，
  
  Published：25 May 2023
- 稿件说明：
移动端阅览
杜明,宋嘉祎,周军锋.规模受限的影响力社区搜索[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization

Incorporating User Preference for Community Search and Outlier Detection in Attributed Network

Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks

Related Author

ZHOU Jun-feng

LI Li-bo

ZHAO Yu-han

WANG Xing-fen

ZHANG An-ran

LI Qing-qing

MA Hui-fang

LI Ju

Related Institution

Beijing Information Science and Technology University

Hong Kong Baptist University, Hongkong

College of Computer Science and Engineering, Northwest Normal University

Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Science and Technology

Guangxi Key Lab of Multi-Source Information Mining & Security, Guangxi Normal University

⁰