Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (8): 16-26.doi: 10.11896/jsjkx.220600262

• Database & Big Data & Data Science • Previous Articles     Next Articles

Maximum Influential Community Search in Heterogeneous Information Network

DU Ming, YANG Wen, ZHOU Junfeng   

  1. School of Computer Science and Technology,Donghua University,Shanghai 201620,China
  • Received:2022-06-28 Revised:2022-11-17 Online:2023-08-15 Published:2023-08-02
  • About author:DU Ming,born in 1975,Ph.D,professor,is a member of China Computer Federation.His main research interests include natural language processing,information query and data analysis.
    ZHOU Junfeng,born in 1977,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include information retrieval technology,semi structured data,query processing and optimization of graphic data.
  • Supported by:
    Natural Science Foundation of Shanghai,China(20ZR1402700) and National Natural Science Foundation of China(61472339,61873337).

PDF (PC)

1785

Abstract: Heterogeneous information network can effectively model data systems,which have diverse object types and complex interactions.Research on community search based on heterogeneous information networks usually builds community models centered on vertex type,minimum degree and network structure,then the cohesive subgraph is queried.However,there are two pro-blems in the existing researches:1)the influence value,another natural attribute hidden in networks is not considered;2)the user'srequirement for the upper limit of the query result scale is ignored too,resulting in the query result do not match user's expectation.Therefore,this paper studies the heterogeneous information networks combined with influence value,and proposes a combined constraint model as a measure of community cohesion for such networks.To solve the community search problems based on the combined constraint model,this paper proposes two search algorithms optimized by preprocessing and pruning strategies.Finally,the effectiveness and efficiency of our method are verified on 8 real data sets.

Key words: Heterogeneous information network, Community search, Community cohesive model, Influence value

CLC Number: 

  • TP311
[1]SHI C,LI Y,ZHANG J,et al.A Survey of Heterogeneous Information Network Analysis[J].IEEE Transactions on Know-ledge and Data Engineering,2016,29(1):17-37.
[2]SUN Y,HAN J.Mining heterogeneous information networks:a structural analysis approach[J].ACM SIGKDD Explorations Newsletter,2013,14(2):20-28.
[3]FANG Y,WANG K,LIN X,et al.Cohesive Subgraph Searchover Big Heterogeneous Information Networks:Applications,Challenges,and Solutions[C]//SIGMOD Conference.2021:2829-2838.
[4]ZHOU A,WANG Y,CHEN L.Finding Large Diverse Communities on Networks:The Edge Maximum k*-Partite Clique[J].Proceedings of the VLDB Endowment(PVLDB),2020,3(11):2576-2589.
[5]ZHU R,ZOU Z,LI J.Diversified Coherent Core Search onMulti-Layer Graphs[C]//2018 IEEE 34th International Confe-rence on Data Engineering (ICDE).IEEE,2018:701-712.
[6]TORE G,IRNICH S,ZIMMERMANN H,et al.Finding all k-cliques in k-partite graphs,an application in textile engineering[J].Computers & Operations Research,2002,29(1):13-31.
[7]DOURISBOURE Y,GERACI F,PELLEGRIMI M.Extraction and classification of dense implicit communities in the Web graph[J].ACM Transactions on the Web,2009,3(2),7:1-7:36.
[8]PALLA G,DERANVI I,FARKAS I,et al.Uncovering theoverlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814.
[9]FANG Y,YANG Y,ZHANG W,et al.Effective and efficientcommunity search over large heterogeneous information networks[J].Proceedings of the VLDB Endowment,2020,13(6):854-867.
[10]YANG Y,FANG Y,LIN X,et al.Effective and Efficient Truss Computation over Large Heterogeneous Information Networks[C]//2020 IEEE 36th International Conference on Data Engineering(ICDE).IEEE,2020:901-912.
[11]JIAN X,WANG Y,CHEN L.Effective and efficient relational community detection and search in large dynamic heterogeneous information networks[J].Proceedings of the VLDB Endowment(PVLDB),2020,13(10):1723-1736.
[12]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.
[13]LIU Z,XIANG B,GUO W,et al.Overlapping Community De-tection Algorithm Based on Coarsening and Local Overlapping Modularity[J].IEEE Access,2019,7:57943-57955.
[14]LI R H,LU Q,XU J,et al.Influential Community Search inLarge Networks[J].Proceedings of the VLDB Endowment (PVLDB),2015,8(5):509-520.
[15]GANESH P,DINGLIWAL S,AGARVAL R.Literature Survey on Finding Influential Communities in Large Scale Networks[J].arXiv:1902.01629,2019.
[16]SOZIO M,GIONIS A.The community-search problem and how to plan a successful cocktail party[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.ACM,2010:939-948.
[17]YAO K,CAHNG L.Efficient size-bounded community searchover large networks[J].Proceedings of the VLDB Endowment(PVLDB),2021,14(8):1441-1453.
[18]FANG Y,YANG Y,ZHANG W,et al.Effectiveand efficientcommunity search over large heterogeneous information networks[C]//Proceedings of the VLDB Endowment.2020:854-867.
[19]YANG Y,FANG Y,LIN X,et al.Effective and Efficient Truss Computation over Large Heterogeneous Information Networks[C]//2020 IEEE 36th International Conference on Data Engineering (ICDE).IEEE,2020:901-912.
[1] WANG Huiyan, YU Minghe, YU Ge. Deep Learning-based Heterogeneous Information Network Representation:A Survey [J]. Computer Science, 2023, 50(5): 103-114.
[2] ZHOU Mingqiang, DAI Kailang, WU Quanwang, ZHU Qingsheng. Attention-aware Multi-channel Graph Convolutional Rating Prediction Model for Heterogeneous Information Networks [J]. Computer Science, 2023, 50(3): 129-138.
[3] LYU Xiao-feng, ZHAO Shu-liang, GAO Heng-da, WU Yong-liang, ZHANG Bao-qi. Short Texts Feautre Enrichment Method Based on Heterogeneous Information Network [J]. Computer Science, 2022, 49(9): 92-100.
[4] DU Hang-yuan, LI Duo, WANG Wen-jian. Method for Abnormal Users Detection Oriented to E-commerce Network [J]. Computer Science, 2022, 49(7): 170-178.
[5] TANG Qi-you, ZHANG Feng-li, WANG Rui-jin, WANG Xue-ting, ZHOU Zhi-yuan, HAN Ying-jun. Method of Attributed Heterogeneous Network Embedding with Multiple Features [J]. Computer Science, 2022, 49(12): 146-154.
[6] JIANG Zong-li, FAN Ke, ZHANG Jin-li. Generative Adversarial Network and Meta-path Based Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(1): 133-139.
[7] ZHENG Su-su, GUAN Dong-hai, YUAN Wei-wei. Heterogeneous Information Network Embedding with Incomplete Multi-view Fusion [J]. Computer Science, 2021, 48(9): 68-76.
[8] ZHAO Jin-long, ZHAO Zhong-ying. Recommendation Algorithm Based on Heterogeneous Information Network Embedding and Attention Neural Network [J]. Computer Science, 2021, 48(8): 72-79.
[9] GAO Chuang, LI Jian-hua, JI Xiu-yi, ZHU Cheng-long, LI Shi-liang, LI Hong-lin. Drug Target Interaction Prediction Method Based on Graph Convolutional Neural Network [J]. Computer Science, 2021, 48(10): 127-134.
[10] LIU Jun-liang, LI Xiao-guang. Techniques for Recommendation System:A Survey [J]. Computer Science, 2020, 47(7): 47-55.
[11] JIANG Zong-li, LI Miao-miao, ZHANG Jin-li. Graph Convolution of Fusion Meta-path Based Heterogeneous Network Representation Learning [J]. Computer Science, 2020, 47(7): 231-235.
[12] WANG Xu, PANG Wei, WANG Zhe. MetaStruct-CF:A Meta Structure Based Collaborative Filtering Algorithm in Heterogeneous Information Networks [J]. Computer Science, 2019, 46(6A): 397-401.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.