欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2017108780908
申请人: 云南大学
专利类型:发明专利
专利状态:已下证
专利领域: 电通信技术
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种动态社交网络中基于联盟形成博弈的社区检测方法,其特征在于,具体按照以下步骤进行:

步骤1,采用基于模块度的社区检测方法对初始社区结构进行检测,得到初始社区结构Γ;

步骤2,将相邻网络快照上网络社区结构的演变分解为增加节点、增加连边、删除节点或删除连边;

步骤3,计算t时刻的社区结构增加节点、增加连边、删除节点或删除连边后,t+1时刻所有可能形成的社区结构的收益,确定收益最大的社区结构为实际演变后t+1时刻的社区结构,如此对初始社区结构Γ进行动态局部调整,得到实际演变后的社区结构Γ';

社区结构Γ的收益v(Γ)的计算方法:社交网络表示为一个无向图G=(N,E),其中:N={v1,v2,...,vn}为节点的集合,表示社交网络中的用户,n为整个社交网络中用户的数量;E={e1,e2,...,em}为连边的集合,表示社交网络中用户之间的联系,m为边的数量;A=(aij)n×n,i,j∈N是社交网络的邻接矩阵,如果用户i和用户j之间存在联系,则aij=1,否则,aij=0;x∈N,d(x)表示节点x的度数;Γ={S1,S2,...,Sk}表示社交网络中的社区结构,k表示社区个数,其中,Si表示一个社区, e(S)表示社区S内部的所有用户之间的边的数量,d(S)表示社区S中的所有用户的度数之和;社区S的收益v(S)的计算公式见式(1),社区结构Γ的收益v(Γ)的计算公式见式(2),其中,α∈[0,1],β∈(0,1]。

2.根据权利要求1所述的一种动态社交网络中基于联盟形成博弈的社区检测方法,其特征在于,所述步骤2中,当相邻网络快照上网络结构的演变为增加节点时,假设增加的节点为节点p:(i)如果节点p与其他节点没有连边连接,此时节点p自己形成一个社区,实际演变后的社区结构Γ′=Γ+{{p}};

(ii)如果节点p与一个或多个社区中的节点有连边,比如社区Sj中的节点与节点p有连边连接,如果将节点p加入社区Sj能增加社区Sj的收益v(Sj),则将节点p加入到社区Sj,实际演变后的社区结构Γ′=Γ-{Sj}+{Sj+{p}};如果节点p分别加入多个社区均能使被加入社区的收益增加,则节点p被加入到多个社区中,同时成为多个社区的成员;

(iii)如果节点p与社区Si、社区Sj内的节点联系均很紧密,即节点p的加入使得两个社区有合并为一个社区的趋势,并且合并后的社区的收益分别大于原来两个社区的单独收益,则将社区Si和社区Sj合并为一个社区,实际演变后的社区结构Γ′=Γ-{Si}-{Sj}+{Si+Sj}。

3.根据权利要求1所述的一种动态社交网络中基于联盟形成博弈的社区检测方法,其特征在于,所述步骤2中,当相邻网络快照上网络结构的演变为增加连边时,假设增加的连边为l=(x,y):(i)如果l=(x,y)是社区Si内部的连边,其中x,y∈Si,若加入l=(x,y)后,社区Si边界的节点z离开社区Si后,使得社区Si的收益v(Si)增大,则节点z从社区Si离开;若节点z加入到与节点z有连边连接的社区Sk中,k≠i,能够增大社区Sk的收益,则节点z加入到社区Sk中,实际演变后的社区结构Γ′=Γ-{Si}-{Sk}+{Sk+{z}}+{Si-{z}};

(ii)如果l=(x,y)是社区间的连边,其中x∈Si,y∈Sj,Si≠Sj,加入l=(x,y)之后,如果社区Si和社区Sj合并得到的新社区的收益大于社区Si、Sj的单独收益,则将社区Si和社区Sj合并,实际演变后的社区结构Γ′=Γ-{Si}-{Sj}+{Si+Sj};如果社区Si和社区Sj不能合并,分别对两个社区的边界节点重新确定社区归属:假设节点x为社区Si的边界节点,若则节点x离开社区Si,其中e(x,Si)表示节点x与社区Si内部节点之间的连边数量;若节点x加入到与节点x有连边连接的社区Sk中,k≠i,能够增大社区Sk的收益,则将节点x加入到社区Sk中,实际演变后的社区结构Γ′=Γ-{Si}-{Sk}+{Sk+{x}}+{Si-{x}};

确定社区Si和社区Sj的其余边界节点社区归属的方法与确定节点x社区归属的方法相同。

4.根据权利要求1所述的一种动态社交网络中基于联盟形成博弈的社区检测方法,其特征在于,所述步骤2中,当相邻网络快照上网络结构的演变为删除节点时,假设删除的节点为节点x:(i)如果节点x是孤立的节点,删除节点x,实际演变后的社区结构Γ′=Γ-{{x}};

(ii)如果节点x是度数为1的节点,节点x所属的社区为Si,当与节点x连接的节点y不是社区Si的边界节点,则节点x离开社区Si,实际演变后的社区结构Γ′=Γ-{Si}+{Si-{x}};

当与节点x连接的节点y是社区Si的边界节点,则节点y与节点y的邻居节点均有离开社区Si加入其他社区的可能,若 则节点y离开社区Si,其中e(y,Si)表示节点y与社区Si内部节点之间的连边数量;若节点y加入到与节点y有连边连接的社区Sk中,k≠i,能够增大社区Sk的收益,则节点y加入到社区Sk中,实际演变后的社区结构Γ′=Γ-{Si}-{Sk}+{Si-{y}}+{Sk+{y}};

(iii)如果节点x是度数大于1的节点,首先用基于模块度的社区检测方法在Sk中删除节点x之后的子图上检测子社区结构Π={Si1,Si2,...},如果Π中的子社区Sij∈Π与原社区结构Γ中除社区Si外的社区Sr合并,使得合并后的社区收益大于合并前两个社区的单独收益,则实际演变后的社区结构Γ′=Γ-{Si}-{Sr}+{Sr∪Sij}+Π-{Sij},Sr∈Γ,r≠i;合并完成后,重新考虑社区Si边界节点的社区归属:假设节点y为社区Si的边界节点,若则节点y离开社区Si,其中e(y,Si)表示节点y与社区Si内部节点之间的连边数量;若节点y加入到与节点y有连边连接的社区Sk中,k≠i,能够增大社区Sk的收益,则将节点y加入到社区Sk中,实际演变后的社区结构Γ=Γ-{Si}-{Sk}+{Sk+{y}}+{Si-{y}};

确定社区Si的其余边界节点社区归属的方法与确定节点y社区归属的方法相同。

5.根据权利要求1所述的一种动态社交网络中基于联盟形成博弈的社区检测方法,其特征在于,所述步骤2中,当相邻网络快照上网络结构的演变为删除连边时,假设删除的连边为l=(x,y):(i)连边l=(x,y)是两个社区之间的边,其中x∈Si,y∈Sj,Si≠Sj,删除连边l之后,社区Si和社区Sj之间的联系减少,两个社区内的边界节点由于连边的删除可能会离开自己所在的社区而加入其它社区,重新考虑两个社区中边界节点的社区归属:假设节点y为社区Si的边界节点,若 则节点y离开社区Si,其中e(y,Si)表示节点y与社区Si内部节点之间的连边数量;若节点y加入到与节点y有连边连接的社区Sk中,k≠i,能够增大社区Sk的收益,则将节点y加入到社区Sk中,实际演变后的社区结构Γ=Γ-{Si}-{Sk}+{Sk+{y}}+{Si-{y}},确定社区Si和社区Sj的其他边界节点社区归属的方法与确定节点y社区归属的方法相同;

(ii)连边l=(x,y)是社区Si内部的边,其中x,y∈Si,如果节点x和节点y均为度数为1的点,则删除连边l之后,节点x和节点y度数均变成了0,此时社区Si分裂成两个子社区,一个子社区由节点x组成,另一个由节点y组成;实际演变后的社区结构Γ=Γ-{Si}+{{x}}+{{y}};

如果节点x和节点y中有一个是度数为1的节点,另一个度数大于1,假定d(x)>1,d(y)=1,删除连边l之后,节点y变为了度数为0的点,与社区Si没有连接,此时社区Si分裂成两个子社区,实际演变后的社区结构Γ=Γ-{Si}+{{y}}+{Si-{y}};

如果节点x是社区Si的边界节点,则节点x及节点x的邻居节点均有离开社区Si加入其他社区的可能,需要重新确定社区Si的边界节点的社区归属:若 则节点x离开社区Si,其中e(x,Si)表示节点x与社区Si内部节点之间的连边数量;若节点x加入到与节点x有连边连接的社区Sk中,k≠i,能够增大社区Sk的收益,则将节点x加入到社区Sk中,实际演变后的社区结构Γ=Γ-{Si}-{Sk}+{Si-{x}}+{Sk+{x}},确定社区Si的其余边界节点社区归属的方法与确定节点x社区归属的方法相同;

如果节点x和节点y均为度数为1的节点,删除连边l之后,首先用基于模块度的社区检测方法在删除边l之后Si中的节点及连边构成的子图上检测出社区结构Π={Si1,Si2,...},如果Π中的子社区Sij∈Π与原社区结构Γ中除社区Si外的社区Sr合并,使得合并后的社区收益大于合并前两个社区的单独收益,则实际演变后的社区结构Γ′=Γ-{Si}-{Sr}+{Sr∪Sij}+Π-{Sij},Sr∈Γ,r≠i;合并完成后,重新考虑社区Si边界节点的社区归属:假设节点x为社区Si的边界节点,若 则节点x离开社区Si,其中e(x,Si)表示节点x与社区Si内部节点之间的连边数量;若节点x加入到与节点x有连边连接的社区Sk中,k≠i,能够增大社区Sk的收益,则将节点x加入到社区Sk中,实际演变后的社区结构Γ′=Γ-{Si}-{Sk}+{Sk+{x}}+{Si-{x}},确定社区Si的其余边界节点社区归属的方法与确定节点x社区归属的方法相同。