Research On Approximate Community Search Algorithms Based On Attributed Heterogeneous Information Network

Attributed heterogeneous information networks widely exist in real life,such as large-scale academic networks,biological information networks,social networks,etc.How to mine communities with closely related relationships in attributed heterogeneous information networks,that is,the community search,can effectively support various upper-level applications,has attracted extensive attention from the academic community.Most of the existing community search work is carried out on homogeneous networks,while the community search work for attributed heterogeneous information networks has just started,and faces the following two challenges: 1)In view of the difference in network structure,the community search algorithm for homogeneous network cannot be directly applied to attributed heterogeneous information network.In addition,the closeness of communities in attributed heterogeneous information networks is often constrained by both structural and attribute closeness.It is urgent to design a community search problem in attributed heterogeneous information networks that considers structure and attribute closeness.2)The precise algorithm for attributed heterogeneous information network takes a long time and has low query efficiency,which is difficult to apply in real scenarios.It is urgent to propose an approximate community search algorithm,which can improve query efficiency while ensuring community query accuracy.In response to the above two challenges,we takes the attributed heterogeneous information network as the research object,comprehensively considers the constraints of attribute compactness and structure compactness,and carries out research work on community search.The main research contents include the following four aspects:(1)The definition and precise algorithm of community search problem in attributed heterogeneous information network.Aiming at challenge 1,the community search problem in attributed heterogeneous information networks considering two constraints of structural compactness and attribute compactness is firstly proposed,and its computational complexity is analyzed and proved to be NP-hard.Then,an exact algorithm is proposed to find the global optimal solution,which can provide an experimental baseline for subsequent research on approximate query algorithms.(2)Approximate community search algorithm for attributed heterogeneous information network.To address challenge 2,we first propose a greedy search-based approximate community serch algorithm framework to optimize query performance by reducing the state search space in the exact algorithm.Under this framework,a community search algorithm based on the deletion strategy of minimizing node contribution is proposed to obtain approximate community search results.Then,a community search algorithm based on batch deletion strategy and a community serch algorithm with protection batch deletion strategy are proposed to further optimize the query performance.(3)Efficient community query algorithm based on proximity graph-based index(PG-Index)..a proximity graph-based index based on community closeness is designed and applied to the above approximate community query algorithm.The initial community is constructed by returning candidate nodes with similar attributes to greatly reduce the community search space and further improve query efficiency.(4)A community serch system for attributed heterogeneous information networks.According to the above research results,a community search system oriented to attributed heterogeneous information networks is developed and implemented,which is mainly divided into three modules: data preprocessing module,index building module and online query module.Through the above research,the community search on the attributed heterogeneous information network can be made more efficient,and it can be better applied to scenarios such as event planning and social marketing.