一种基于信息瓶颈理论的社区探测方法

摘要

本申请提出一种基于信息瓶颈理论的社区探测方法，在聚类过程中，信息损失变化的趋势非常明显，但模块化曲线的变化趋势相对平缓，有时模块化曲线的最大值也不突出。但是，当簇数目较小时，信息损失曲线较快上升。通过分析信息损失曲线的拐点，可以确定最优的k值。由于采用信息瓶颈理论进行相似度的计算，避免了在传统聚类中随意选择相似度算法产生的主观误差，同时降低了时间复杂度，聚类的效率和准确率得到提高，且可以避免层次聚类容易导致的局部最优解，更适合处理目前的大规模数据集。

主权项

一种基于信息瓶颈理论的社区探测方法，其特征在于，该方法采用划分式聚类，将网络中的n个节点分为k个簇，簇也叫社区，其中n，k为自然数，且2≤k＜n，具体步骤如下：(1)给定一个无向图G＝(V,E)，将该图转换成二部图B，转换规则为：①图G中的节点a对应图B中的两个节点u_a和v_a；②图G中的边(a,b)对应图B中的两条边(u_a,v_b)和(u_b,v_a)，且这两条边的权重等于图G中边(a,b)的权重，即w_ab，其中G＝(V,E)表示一个n个节点和m条边的无向图，m为自然数，V表示节点集合，E表示边集合，V＝{1,2,…,n}，E＝{(a,b)|a,b∈V}，w_ab表示边(a,b)的权重，a,b为自然数，1≤a≤n，1≤b≤n；转换后，得到关于该二部图的矩阵M，矩阵M的行对应节点(u₁,u₂,…,u_n)，矩阵M的列对应节点(v₁,v₂,…,v_n)，矩阵M的元素m_ab对应边(u_a,v_b)的权重，即m_ab＝w_ab，再对矩阵M的元素执行标准化，即m_ab＝m_ab/w，其中w为矩阵M中所有元素之和。(2)给定一个网络，划分为k个簇，其集合为C＝{C₁,C₂,…,C_k}，每个簇和所有节点组成的簇P间信息损失为令簇C_i质心的特征向量为(W_i1,W_i2,…,W_in)，其中W_i1,W_i2,…,W_in为质心向量的特征值；令簇P质心的特征向量为(W₁,W₂,…,W_n)，当簇C_i和簇P合并时产生的信息损失$\mathrm{dis}(C_i,P)=\frac{\left|C_i\right|}{n}\underset{t=1}{\overset{n}{\Sigma }}{W}_{\mathrm{it}}\log \frac{W_{\mathrm{it}}}{W_t^{\prime }}+\frac{\left|C\right|}{n}\underset{t=1}{\overset{n}{\Sigma }}{W}_t\log \frac{W_t}{W_t^{\prime }},$其中再给定一个网络，被划分为k个簇，其集合为C＝{C₁,C₂,…,C_k}，每个簇C_i和该簇内每个节点组成的簇{d}间的簇内信息损失为E和I的交点为k。(3)网络被随机划分为k个簇，表示为C＝{C₁,C₂,…,C_k}，依次选择每个节点d，将其从现有归属簇中选出，形成一个临时簇{d}，计算{d}与现有每个簇的信息损失dis({d},C_i)；将节点d合并到簇C’中，其中C'＝argmin_v∈C dis({d},v)，执行该重新分配过程l次，l为自然数；以上步骤共执行z次，每次选取不同的k个初始簇，评分函数S等于在聚类过程中所有信息损失之和，当S值最小时，选择此时对应的方案为最佳方案。