属性公平的异质信息网络上的社区搜索算法

Community Search Algorithm on Heterogeneous Information Networks Based o n Attribute Fairness

近年来,异质信息网络上的社区搜索问题已经吸引了越来越多的关注,而且被广泛应用在图数据分析工作中.但是现有异质信息网络上的社区搜索问题都没有考虑子图上属性的公平性.将属性的公平性与异质信息网络上的kPcore挖掘问题相结合,提出了基于属性公平的异质信息网络上的极大core挖掘问题.针对该问题,首先提出了一个子图模型FkPcore.当对FkPcore进行枚举时,基础算法Basic-FkPcore遍历了所有路径实例,并枚举了大量k Pcore及其子图.为了提高算法效率,提出了Adv-FkPcore算法,以避免在枚举FkPcore时对所有的kPcore及其子图进行判断.另外,为了提高点的P_neighbor的获取效率,提出了结合点标记的遍历方法(traversalmethod with vertex sign, TMS),并基于TMS算法提出了FkPcore枚举算法Opt-FkPcore.在异质信息网络数据集上进行的大量实验证明了所提方法的有效性和效率.

In recent years, community search on heterogeneous information networks has attracted more and more attention and has been widely used in graph data analysis. Nevertheless, the existing community search problems on heterogeneous informatio n networks do not consider the fairness of attributes on subgraphs. This work combines attribute fairness with kPcore mining on heterogeneous i nformation networks and proposes a maximum core mining problem on heterogeneous information networks based on att ribute fairness. To solve this problem, a subgraph model called FkPcore is proposed. When enumerating FkPcore, the basic algorithm called Basic-FkPcore traverses all path instances and enumerates a large number of kPcores and their subgraphs. In order to i mprove the efficiency of the algorithm, an Adv-FkPcore algorithm is proposed to avoid judging all kPcores and their subgraphs when enumerating FkPcores. In addition, in ord er to improve the acquisition efficiency of P_neighbor, a traversal method with vert ex sign(TMS) and a FkPcore enumeration algorithm called Opt-FkPcore based on the TMS algorithm are proposed. A large number of experiments on heterogeneous information networks demonstrate the effectiveness and efficiency of the proposed method.