[发明专利]基于节点隶属度的标签传播社团结构挖掘方法

摘要

一种基于节点隶属度的标签传播社团结构挖掘方法，包括以下步骤：为网络中的各个节点赋予一个唯一的标签，并用标签表示节点所属的社团；将复杂网络邻接矩阵中的行向量看作是各节点的采样样本，计算两节点之间的权值系数作为边的权值；利用各节点连边权值系数的方差作为该节点的隶属度；在每次标签更新迭代中只更新隶属度大于标签更新阀值的节点标签，将隶属度小于标签更新阀值的节点作为重叠节点；如果标签改变或标签传播次数小于标签迭代阈值，则重复上述迭代过程，否则停止更新。本发明在时间复杂度提升不大的情况下能够很好地检测出复杂网络的重叠社团结构，具有良好的鲁棒性和准确性。

主权项

一种基于节点隶属度的标签传播社团结构挖掘方法，其特征在于：该方法包括以下步骤：S1、在一个具有N个节点vi(i＝1,2,…,N)的复杂网络图G中，按照由1至N的递增顺序为网络中的N个节点编号；为每一个节点构造三元组{节点编号，节点标签，节点隶属度}，其中，节点标签的初始值等于该节点的编号，节点隶属度的初始值为0；网络中节点标签的集合表示为L＝{l1,l2,…,lS}(S≤N)，集合L的元素li(i＝1,2,...,S)是一个节点标签；预设标签更新阀值λ、标签迭代阈值T和令标签传播次数t＝0；S2、计算网络中直接相连的所有节点对之间的权值系数，并将这些权值系数作为各连边权值，并更新标签迭代次数t＝t+1；所述的计算网络中直接相连的所有节点对间的权值系数，是指利用网络图G的邻接矩阵A，按公式(1)计算每条边eij的权值系数rij：rij=N-1NΣt=1N(ati-ai‾)(atj-aj‾)Σt=1N(ati-ai‾)2Σt=1N(atj-aj‾)2+1---(1)]]>其中，aij为网络邻接矩阵A中的元素，i＝1,2,...,N，j＝1,2,...,N。S3、利用节点标签及连边权值计算网络中各节点的隶属度，具体如下：对网络中的所有节点vi(i＝1,2,...,N)，设集合是节点vi的直接邻居节点所具有的互异标签的集合，其中Q是互异标签的数目；用表示节点vi的直接邻居节点中标签值为的节点的集合，计算节点vi与其直接邻居节点集合中，标签为的节点连边的权值总和，公式如下ri(lip)=Σj∈Ni(lip)rij---(2)]]>其中，1≤p≤Q；计算节点vi所在的所有连边权值的均值，公式如下：ri‾=Σf∈Li′ri(f)Q---(3)]]>计算节点vi所在的所有连边的权值的方差，并将该方差值作为节点vi的隶属度D(i)，公式如下：D(i)=Σq∈Li′(ri(q)-ri‾)2Q---(4)]]>S4、对于网络中任意节点vi(i＝1,2,...,N)，若其隶属度D(i)大于标签更新阀值λ，则更新将该节点标签；S5、判断是否有节点标签发生了改变或者标签迭代次数t小于预设的标签迭代阈值T，如有则返回步骤2；否则，输出网络G的具有重叠的社区结构。