1.一种基于结构平衡约束的符号网络社区发现方法,其特征在于,具体包括如下步骤:步骤1:符号网络形式化表示为无向图G=(V,E+,E-);其中V={v0,v1,...,vn-1}表示n个网络节点的集合,E+表示网络节点之间正连接边的集合,E-表示网络节点之间负连接边的集合,其中, 即两个节点之间不可能同时存在正连接边和负连接边;
步骤2:构建符号网络邻接矩阵A和结构平衡约束信息矩阵M;
构建一个n×n的邻接矩阵A=[aij]n×n表示节点之间的连接边信息,其中n为所述符号网络中节点的数量;
构建一个约束矩阵M=[mis]n×n表示所有正关系约束对,当vi和vs之间存在大概率的正关系约束时,则mis=1,否则mis=0;
步骤3:基于半非负矩阵分解构建社区发现模型;
步骤4:求解社区发现模型获得W和H矩阵;
步骤5:根据H获得社区发现结果。
2.根据权利要求1所述的一种基于结构平衡约束的符号网络社区发现方法,其特征在于:步骤2中,在邻接矩阵A对于任意一个节点对vi和vj的连接边eij,如果eij∈E+,则aij=aji=+1,如果eij∈E-,则aij=aji=-1,如果 则aij=aji=0。
3.根据权利要求1或2所述的一种基于结构平衡约束的符号网络社区发现方法,其特征在于:步骤2中,对于任意三个网络节点构成的三元组<vi,vj,vs>,如果其中连接边满足或者则网络节点vi和vs之间存在正关系约束。
4.根据权利要求1所述的一种基于结构平衡约束的符号网络社区发现方法,其特征在于:步骤3中,假设社区数目为k,令W=[wil]n×k∈n×k表示节点社区特征矩阵,表示节点与社区的归属关系矩阵,其中wil表示社区l中第i个节点的特征向量,hjl表示节点j与社区l的归属关系,表示任意实数集合,+表示正实数集合和0;
基于半非负矩阵分解模型,直接分解符号网络的邻接矩阵A为W和HT的近似乘积,同时将M表达的约束信息转化为对H的正则约束项,设计如下社区发现模型:其中L为M的拉普拉斯矩阵,λ为正则项参数,tr(·)为矩阵的迹,F为Frobenius范数,即欧式距离。
5.根据权利要求4所述的一种基于结构平衡约束的符号网络社区发现方法,其特征在于:步骤3中,对于网络节点vi和vs,如果mis=1,那么vi和vs在同一个社区,则对应的节点社区指示向量hi和hs的欧式距离 趋近0。
6.根据权利要求1所述的一种基于结构平衡约束的符号网络社区发现方法,其特征在于:步骤4中,采用交替迭代更新W和H的方式求解社区发现模型,首先将目标函数J(W,H)写为矩阵迹的形式:J(W,H)=tr(AAT-2AHWT+WHTHWT)+λtr(HTLH)固定H,令J(W,H)关于W的导数为0,即: 从而求得W的迭代更新规则为wil=(AH(HTH)-1)il;
n×k
对于H,将H的求解转换为对J(W,H)的受限约束求极值,并引入拉格朗日乘数α∈ 构建如下拉格朗日函数:L(W,H)=J(W,H)+tr(αHT)
求得L(W,H)关于H的导数为:
通过引入Karush-Kuhn-Tucker(KKT)条件,求得H的迭代更新规则为:其中hil表示节点i与社区l的归属强度,
7.根据权利要求1所述的一种基于结构平衡约束的符号网络社区发现方法,其特征在于:步骤5中,首先设定迭代次数t以及收敛阈值 初始化H和W,然后迭代应用H和W的更新规则,当迭代次数超过t或者 则能获得H和W的最优解,最后根据H获取社区划分结果;
具体为:假定待发现的k个社区为C={c0,c1,...,ck-1},对于任意一个用户节点vi,基于节点i与社区l的归属强度hil,采用式 将节点i具有最大归属强度的社区编号赋值给p,则有cp=cp∪{vi},即将网络节点vi划分为社区l。