有向图上的影响力社区搜索

杜明; 胡欣雨; 周军锋

doi:10.11959/j.issn.1000-436x.2024189

您当前的位置：

首页 >

文章列表页 >

有向图上的影响力社区搜索

学术论文 | 更新时间：2024-12-24

- 有向图上的影响力社区搜索
- Influence community search on directed graphs
- 通信学报 2024年45卷第11期页码：157-173
- 作者机构：
  
  东华大学计算机科学与技术学院，上海 201620
- 作者简介：
  
  [ "杜明（1975- ），男，黑龙江鸡西人，博士，东华大学教授，主要研究方向为图数据处理技术、自然语言处理等。" ]
  [ "胡欣雨（1998- ），女，上海人，东华大学硕士生，主要研究方向为社区搜索算法。" ]
  [ "周军锋（1977- ），男，陕西西安人，博士，东华大学教授、博士生导师，主要研究方向为大图数据的查询处理技术、推荐系统关键技术等。" ]
- 基金信息：
  
  国家自然科学基金资助项目(62372101;61873337;62272097)
- DOI：10.11959/j.issn.1000-436x.2024189
  中图分类号： TP311
- 收稿日期：2024-07-12，
  
  修回日期：2024-10-10，
  
  纸质出版日期：2024-11-25
- 稿件说明：
移动端阅览
杜明,胡欣雨,周军锋.有向图上的影响力社区搜索[J].通信学报,2024,45(11):157-173.

DU Ming,HU Xinyu,ZHOU Junfeng.Influence community search on directed graphs[J].Journal on Communications,2024,45(11):157-173.
杜明,胡欣雨,周军锋.有向图上的影响力社区搜索[J].通信学报,2024,45(11):157-173. DOI： 10.11959/j.issn.1000-436x.2024189.

DU Ming,HU Xinyu,ZHOU Junfeng.Influence community search on directed graphs[J].Journal on Communications,2024,45(11):157-173. DOI： 10.11959/j.issn.1000-436x.2024189.

摘要

现有社区搜索方法用于从无向图中挖掘满足内聚性和影响力要求的社区，没有考虑有向图中边的方向对社区的影响，导致有向图上社区挖掘的结果出现影响力和内聚性不足的问题。基于此，提出有向图上的影响力社区搜索问题，并设计相应的在线搜索算法；为进一步提升社区挖掘的效率，提出有向图上基于索引的影响力搜索方法及其优化策略。此外，提出一种基于并行思想的索引构建方法，加速索引的构建过程。最后，基于8个真实数据集进行验证，实验结果验证了所提算法的有效性和高效性。

Abstract

Existing community search methods are used to explore communities in undirected graphs that meet cohesion and influence requirements

without considering the impact of edge direction in directed graphs. This oversight leads to insufficient influence and cohesion in the results of community detection on directed graphs. The problem of influence community search on directed graphs was proposed

and a corresponding online search algorithm was designed. To further enhance the efficiency of community mining

an index-based influence search method on directed graphs and its optimization strategies were proposed. In addition

a parallel-based index construction method was proposed to accelerate the index building process. Finally

based on eight real-world datasets

validation is conducted

and the experimental results confirm the effectiveness and efficiency of the proposed algorithm.

关键词

Keywords

references

ZHOU Y L , FANG Y X , LUO W S , et al . Influential community search over large heterogeneous information networks [J ] . Proceedings of the VLDB Endowment , 2023 , 16 ( 8 ): 2047 - 2060 .

ZHANG F , GUO H C , OUYANG D , et al . Size-constrained community search on large networks: an effective and efficient solution [J ] . IEEE Transactions on Knowledge and Data Engineering , 2024 , 36 ( 1 ): 356 - 371 .

LI Q Q , MA H F , LI Z X , et al . Multiresolution local spectral attributed community search [J ] . ACM Transactions on the Web , 2024 , 18 ( 1 ): 1 - 28 .

MALLIAROS F D , GIATSIDIS C , PAPADOPOULOS A N , et al . The core decomposition of networks: theory, algorithms and applications [J ] . The VLDB Journal , 2020 , 29 ( 1 ): 61 - 92 .

ZONG C Y , GONG P C , ZHANG X , et al . Efficient size-constrained (k, d)-truss community search [C ] // International Conference on Advanced Data Mining and Applications . Berlin : Springer , 2023 : 405 - 420 .

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 .

TAKAGUCHI T , YOSHIDA Y . Cycle and flow trusses in directed networks [J ] . Royal Society Open Science , 2016 , 3 ( 11 ): 160270 .

LIU Q , ZHAO M J , HUANG X , et al . Truss-based community search over large directed graphs [C ] // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . New York : ACM Press , 2020 : 2183 - 2197 .

TIAN A X , ZHOU A , WANG Y , et al . Maximal D-truss search in dynamic directed graphs [J ] . Proceedings of the VLDB Endowment , 2023 , 16 ( 9 ): 2199 - 2211 .

HAJIBABAEI H , SEYDI V , KOOCHARI A . Community detection in weighted networks using probabilistic generative model [J ] . Journal of Intelligent Information Systems , 2023 , 60 ( 1 ): 119 - 136 .

KOSMANOS K , KALNIS P , PAPADOPOULOS A . Incremental influential community detection in large networks [C ] // Proceedings of the 34th International Conference on Scientific and Statistical Database Management . New York : ACM Press , 2022 : 1 - 12 .

YU D X , ZHANG L F , LUO Q , et al . Maximal clique search in weighted graphs [J ] . IEEE Transactions on Knowledge and Data Engineering , 2023 , 35 ( 9 ): 9421 - 9432 .

ZHOU W , HUANG H , HUA Q S , et al . Core decomposition and maintenance in weighted graph [J ] . World Wide Web , 2021 , 24 ( 2 ): 541 - 561 .

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

杜明 , 宋嘉祎 , 周军锋 . 规模受限的影响力社区搜索 [J ] . 电子学报 , 2023 , 51 ( 5 ): 1207 - 1214 .

DU M , SONG J Y , ZHOU J F . Size-constrained influential community search [J ] . Acta Electronica Sinica , 2023 , 51 ( 5 ): 1207 - 1214 .

DORANTES-GILARDI R , GARCÍA-CORTÉS D , HERNÁNDEZ-LEMUS E , et al . K-core genes underpin structural features of breast cancer [J ] . Scientific Reports , 2021 , 11 ( 1 ): 16284 .

WILLIAMS H T P , MCMURRAY J R , KURZ T , et al . Network analysis reveals open forums and echo chambers in social media discussions of climate change [J ] . Global Environmental Change , 2015 , 32 : 126 - 138 .

KIM J , GUO T , FENG K Y , et al . Densely connected user community and location cluster search in location-based social networks [C ] // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . New York : ACM Press , 2020 : 2199 - 2209 .

LI Q Y , ZHU Y Y , YE J H , et al . Skyline group queries in large road-social networks revisited [J ] . IEEE Transactions on Knowledge and Data Engineering , 2023 , 35 ( 3 ): 3115 - 3129 .

浏览量

下载量

CSCD

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

提交

工具集

关联资源

暂无数据