技术摘要: 本发明公开了异构网络社群检测方法、装置、计算机设备及存储介质。该方法包括预先设置通过三元组
表示异构网络G的类型约束s;然后根据用户的社群需求获取满足社群需求的类型约束集合S,以及节点类型集合LS;然后判断异构网络G中的每一个节点v的类型是否属于节 全部
背景技术:
在图数据挖掘中,社群检测是其中比较重要的一步,通过社群检测算法可以针对
某一种特定的社群结构进行查找,目前比较流行的是采用基于k-核的社群结构。
但在异构网络中,由于存在不同的类型节点,用户在进行社群检测中往往需要对
多个不同类型的邻居节点个数进行自定义的设置;而目前的基于k-核的社群结构只能满足
在同构网络中的社群检测,不能对多个不同类型的邻居节点个数进行自定义的设置。
k-核的社群结构定义如下:给定一个正整数k≥0,网络G的k-核为满足以下条件的
最大子图Hk:对于任意节点v∈Hk,节点v的节点度
图1是一个示例k-核社群,其中,子图{A,B,C ,D}是一个3-核社群,因为在该子图
中,每个节点都有至少三个邻居节点。图{A,B,C,D,E,F,G,H,I}是一个1-核社群,它由两个
连通子图组成:{A,B,C,D,E,F,G}和{H,I},在该子图中每个节点都至少有一个邻居节点。参
数k越大,所检测到的社群往往越小,同时,社群中的节点之间也更加紧密。
k-核社群是一种定义在同构网络的社群结构,并不能应用在异构网络中进行社群
检测,因为异构网络往往拥有不同类型的节点。在异构图中,并不能直接使用k-核的结构来
检测社群。同时,在异构网络中,由于不同类型节点的存在,用户往往需要针对不同类型的
邻居节点进行不同的设定,k-核社群的定义只有一个参数k,因此在这种情况下,并不能满
足实际应用的需求。
图2是一个示例学术网络,它包含了三种节点类型:A:作者,P:论文,V:会议。图中
的每个节点都标注了该节点的所属类型。此外,边A-P表示作者参与撰写了论文,边P-V表示
论文被发表在会议中。假设一个用户针对该异构网络进行数据挖掘的相关分析,并希望找
到有关作者和论文学术社群,满足在该社群中每个作者至少发了2篇论文,并且每个论文至
少有3个合作者。图3虚线的部分是该异构网络中满足用户查询需求的一个学术社群。然而,
目前基于k-核的社群结构并不能挖掘出这样的学术社群:当k=1时,k-核社群是整个异构
网络;当k=2时,其对应的k-核社群由图4的虚线部分所表示,当k=3时,其对应的k-核社群
为空集。因此目前基于k-核的社群结构并不能满足在异构网络中包含多类型节点的社群搜
索与检测。
因此,现有技术中难以解决针对异构网络多类型节点的社群检测,也没有相应的
方法来检测出这种社群结构。
技术实现要素:
本发明的目的是提供一种基于节点约束的异构网络社群检测方法、装置、计算机
设备及存储介质,旨在解决现有技术中没有针对异构网络多类型节点的社群检测以及对这
4
CN 111597396 A 说 明 书 2/10 页
种社群结构的检测算法。
第一方面,本发明实施例提供了一种基于节点约束的异构网络社群检测方法,其
包括:预先设置通过三元组表示异构网络G的类型约束s;其中,所述三元组用于表示每个类型为l1的节点至少有k个类型为l2的邻居节点,l1,l2∈LG,k≥1,所述
LG为所述异构网络G的节点的类型集合;
根据用户的查询条件获取用户的社群需求,并获取满足所述社群需求的类型约束
集合S,其中,S={s1,s2,…,st},所述s1,s2,...,st表示不同的类型约束;
根据所述类型约束集合S获取满足所述社群需求的节点类型集合LS;
判断所述异构网络G中的每一个节点v的类型是否属于所述节点类型集合LS,以及
每一个节点v是否满足所述类型约束集合S中的每一个类型约束;
若所述异构网络G中的节点v的类型不属于所述节点类型集合LS,或者所述节点v
不满足所述类型约束集合S中任意一个类型约束,则将所述节点v判定为非有效节点;
将所述异构网络G中的所有非有效节点加入至待删除节点集合H中并进行删除,并
将所述待删除节点集合H中的非有效节点与每一邻居节点组成对应的消息,加入至消息队
列Q中;
根据所述类型约束集合S的每一类型约束迭代判断所述消息队列Q中是否产生了
新的非有效节点,若是则将新的非有效节点删除,从而得到满足查询条件的社群。
第二方面,本发明实施例提供了一种基于节点约束的异构网络社群检测装置,其
包括:
预设单元,用于预先设置通过三元组表示异构网络G的类型约束s;其中,
所述三元组用于表示每个类型为l1的节点至少有k个类型为l2的邻居节点,l1,l2
∈LG,k≥1,所述LG为所述异构网络G的节点的类型集合;
第一获取单元,用于根据用户的查询条件获取用户的社群需求,并获取满足所述
社群需求的类型约束集合S,其中,S={s1,s2,…,st},所述s1,s2,...,st表示不同的类型约
束;
第二获取单元,用于根据所述类型约束集合S获取满足所述社群需求的节点类型
集合LS;
第一判断单元,用于判断所述异构网络G中的每一个节点v的类型是否属于所述节
点类型集合LS,以及每一个节点v是否满足所述类型约束集合S中的每一个类型约束;
第二判断单元,用于若所述异构网络G中的节点v的类型不属于所述节点类型集合
LS,或者所述节点v不满足所述类型约束集合S中任意一个类型约束,则将所述节点v判定为
非有效节点;
删除单元,用于将所述异构网络G中的所有非有效节点加入至待删除节点集合H中
并进行删除,并将所述待删除节点集合H中的非有效节点与每一邻居节点组成对应的消息,
加入至消息队列Q中;
迭代判断单元,用于根据所述类型约束集合S的每一类型约束迭代判断所述消息
队列Q中是否产生了新的非有效节点,若是则将新的非有效节点删除,从而得到满足查询条
件的社群。
第三方面,本发明实施例又提供了一种计算机设备,其包括存储器、处理器及存储
5
CN 111597396 A 说 明 书 3/10 页
在所述存储器上并可在所述处理器上运行的计算机程序,所述处理器执行所述计算机程序
时实现上述第一方面所述的基于节点约束的异构网络社群检测方法。
第四方面,本发明实施例还提供了一种计算机可读存储介质,其中所述计算机可
读存储介质存储有计算机程序,所述计算机程序当被处理器执行时使所述处理器执行上述
第一方面所述的基于节点约束的异构网络社群检测方法。
本发明公开了一种基于节点约束的异构网络社群检测方法、装置、计算机设备及
存储介质,其中,方法包括:预先设置通过三元组表示异构网络G的类型约束s;其
中,所述三元组用于表示每个类型为l1的节点至少有k个类型为l2的邻居节点,l1,
l2∈LG,k≥1,所述LG为所述异构网络G的节点的类型集合;根据用户的查询条件获取用户的
社群需求,并获取满足所述社群需求的类型约束集合S,其中,S={s1 ,s2 ,… ,st},所述s1 ,
s2,...,st表示不同的类型约束;根据所述类型约束集合S获取满足所述社群需求的节点类
型集合LS;判断所述异构网络G中的每一个节点v的类型是否属于所述节点类型集合LS,以及
每一个节点v是否满足所述类型约束集合S中的每一个类型约束;若所述异构网络G中的节
点v的类型不属于所述节点类型集合LS,或者所述节点v不满足所述类型约束集合S中任意
一个类型约束,则将所述节点v判定为非有效节点;将所述异构网络G中的所有非有效节点
加入至待删除节点集合H中并进行删除,并将所述待删除节点集合H中的非有效节点与每一
邻居节点组成对应的消息,加入至消息队列Q中;根据所述类型约束集合S的每一类型约束
迭代判断所述消息队列Q中是否产生了新的非有效节点,若是则将新的非有效节点删除,从
而得到满足查询条件的社群。该方法根据用户的社群需求,获取了满足社群需求的类型约
束集合S以及节点类型集合LS,然后根据类型约束集合S和节点类型集合LS将异构网络G中所
有的非有效节点找出并删除,最后得到满足查询条件的社群。本发明实施例实现了满足用
户在异构网络中进行基于节点约束的个性化社群查询的需求。
附图说明
为了更清楚地说明本发明实施例技术方案,下面将对实施例描述中所需要使用的
附图作简单地介绍,显而易见地,下面描述中的附图是本发明的一些实施例,对于本领域普
通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。
图1为现有技术提供的k-核社群示意图;
图2为现有技术提供的学术网络示意图;
图3为图2中满足用户需求的实际社群示意图;
图4为基于现有技术查找到的2-核社群示意图;
图5为本发明实施例提供的基于节点约束的异构网络社群检测方法的流程示意
图;
图6为本发明实施例提供的基于节点约束的异构网络社群检测方法的子流程示意
图;
图7为本发明实施例提供的基于节点约束的异构网络社群检测方法的又一子流程
示意图;
图8为本发明实施例提供的基于节点约束的异构网络社群检测方法的又一子流程
示意图;
6
CN 111597396 A 说 明 书 4/10 页
图9为本发明实施例提供的对学术网络进行节点分类和编号的网络示意图;
图10为本发明实施例提供的基于节点约束的异构网络社群检测装置的示意性框
图;
图11为本发明实施例提供的计算机设备的示意性框图。