一种基于信任关联度的微博网络社区发现方法

摘要

目前，现有的社交网络快速划分社区算法存在质量低、不能充分利用节点链接信息的问题，而效果较好的划分算法也存在时间复杂度高、无法应用于大规模社交网络的问题。为此，提出了基于信任关联度的微博网络社区发现算法。在定义社区节点对信息群度、动态分配网络边权重值的基础上，计算节点的信任关联度矩阵，再通过改进的K-medoids算法对节点进行聚类分析，通过计算社区数的LC模块度确定网络社区的理想结构。在新浪微博数据集上进行实验，结果表明，该算法能使得社区的划分结果更准确。

主权项

一种基于信任关联度的微博网络社区发现方法，其特征在于包括以下步骤:101、获取微博数据来定义节点的信息群度，具体包括以下步骤:Al、根据节点的原创微博数o_ij、微博转发数r_ij来计算出节点之间的活跃值a_ij，其中有a_ij＝(β₁×o_ij+β₂×r_ij)/n；Bl、根据节点之间的评论数为c_ij、赞数为l_ij，微博总数n来计算出节点之间的博文质量值q_ij，其中有q_ij＝(λ₁×c_ij+λ₂×l_ij)/n；Cl、将节点之间边权重w_ij的值设为节点对的信息群度，即d_ij＝1/(a_ij+q_ij)w_ij＝d_ij102、根据101中求得的信息群度来计算节点之间的信任关联度，具体包括以下步骤:A2、由于节点i与j之间的节点对的信息群度越小，它们的信任关联度就越大，定义两个相邻节点v_i、v_j的信任关联度：node Relation(v_i,v_j)＝1‑w_ijB2、利用深度优先搜索算法求得图中所有的非相邻节点之间的最短路径，然后再求出非相邻节点之间的最大信任关联度。假设微博网络中非相邻节点v_i和节点v_j之间的最短路径为shortPath(v_i,v_j)＝{(v_i,v_k),(v_k,v_m),...,(v_n,v_j)}，如果非相邻节点间的最短路径数为s，则选择其中乘积最大的作为非相邻节点的信任关联度，即$node\mathrm{Re}lation(v_i,v_j)=\underset{s}{max}\left\{\underset{(v_i,v_k)\in shortPath(v_i,v_j)}{\Pi }node\mathrm{Re}lation(v_i,v_k)\right\}$C2、根据A2、B2可以构造微博网络的节点信任关联度矩阵R，即R＝[node Relation(v_i,v_j)]_|V|×|V|D2、由于R是一个对称矩阵，根据节点与其自身的信任关联度值为1，因此为了计算方便，将矩阵R主对角线上的元素值设为相应节点的度，即103、在101、102的基础上再采用LC模块度，它与社区的连接密度和内聚系数相关，具体包括以下步骤:A3、假设有某种划分形式，将网络G划分为S₁，S₂，…，Sn。首先，计算社区Si的连接密度L(Si)，其中，n_i表示社区Si的节点数；E(S_i)表示社区Si内部的边数，即$L\left(S_i\right)=\left\{\begin{array}{cc}1& n_i=1\\ \frac{2E\left(S_i\right)}{n_i(n_i-1)}& n_i>1\end{array}\right.$B3、然后，计算社区Si的内聚系数Coh(Si)，其中，i≠j,并且A(S_i,S_j)表示连接社区Si和Sj之间的边的总数，即$Coh\left(S_i\right)=\left\{\begin{array}{cc}0& E\left(S_i\right)=1\\ \frac{E\left(S_i\right)}{E\left(S_i\right)+\underset{j\ne 1}{\Sigma }A(S_i,S_j)}& E\left(S_i\right)>1\end{array}\right.$C3、在A3、B3的基础上计算LC模块度Q(S₁,S₂,...,S_n)，即$Q(S_1,S_2,...,S_n)=\left\{\begin{array}{cc}0& n=0\\ \frac{\underset{i=1}{\overset{n}{\Sigma }}L\left(S_i\right)Coh\left(S_i\right)}{n}& n>1\end{array}\right.$D3、再用改进的K‑medoids算法对节点进行聚类，首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对象的距离分配给最近的一个簇，以簇类各个节点轮换为相应的聚类中心，最后得出最大的LC模块度值对应社区划分的最佳结果。