主权项 |
一种基于信息瓶颈理论和社区探测的网络信息检索方法,其特征在于,该方法采用划分式聚类,将网络中的n个节点分为k个簇,簇也叫社区,其中n,k为自然数,且2≤k<n,具体步骤如下:(1)给定一个无向图G=(V,E),将该图转换成二部图B,转换规则为:①图G中的节点a对应图B中的两个节点u<sub>a</sub>和v<sub>a</sub>;②图G中的边(a,b)对应图B中的两条边(u<sub>a</sub>,v<sub>b</sub>)和(u<sub>b</sub>,v<sub>a</sub>),且这两条边的权重等于图G中边(a,b)的权重,即w<sub>ab</sub>,其中G=(V,E)表示一个n个节点和m条边的无向图,m为自然数,V表示节点集合,E表示边集合,V={1,2,…,n},E={(a,b)|a,b∈V},w<sub>ab</sub>表示边(a,b)的权重,a,b为自然数,1≤a≤n,1≤b≤n;转换后,得到关于该二部图的矩阵M,矩阵M的行对应节点(u<sub>1</sub>,u<sub>2</sub>,…,u<sub>n</sub>),矩阵M的列对应节点(v<sub>1</sub>,v<sub>2</sub>,…,v<sub>n</sub>),矩阵M的元素m<sub>ab</sub>对应边(u<sub>a</sub>,v<sub>b</sub>)的权重,即m<sub>ab</sub>=w<sub>ab</sub>,再对矩阵M的元素执行标准化,即m<sub>ab</sub>=m<sub>ab</sub>/w,其中w为矩阵M中所有元素之和。(2)给定一个网络,划分为k个簇,其集合为C={C<sub>1</sub>,C<sub>2</sub>,…,C<sub>k</sub>},每个簇和所有节点组成的簇P间信息损失为<img file="FDA0001110963250000011.GIF" wi="371" he="127" />令簇C<sub>i</sub>质心的特征向量为(W<sub>i1</sub>,W<sub>i2</sub>,…,W<sub>in</sub>),其中W<sub>i1</sub>,W<sub>i2</sub>,…,W<sub>in</sub>为质心向量的特征值;令簇P质心的特征向量为(W<sub>1</sub>,W<sub>2</sub>,…,W<sub>n</sub>),当簇C<sub>i</sub>和簇P合并时产生的信息损失<img file="FDA0001110963250000012.GIF" wi="1003" he="133" />其中<img file="FDA0001110963250000013.GIF" wi="638" he="127" />再给定一个网络,被划分为k个簇,其集合为C={C<sub>1</sub>,C<sub>2</sub>,…,C<sub>k</sub>},每个簇C<sub>i</sub>和该簇内每个节点组成的簇{d}间的簇内信息损失为<img file="FDA0001110963250000014.GIF" wi="467" he="143" />E和I的交点为k。(3)网络被随机划分为k个簇,表示为C={C<sub>1</sub>,C<sub>2</sub>,…,C<sub>k</sub>},依次选择每个节点d,将其从现有归属簇中选出,形成一个临时簇{d},计算{d}与现有每个簇的信息损失dis({d},C<sub>i</sub>);将节点d合并到簇C’中,其中C'=argmin<sub>v∈C</sub>dis({d},v),执行该重新分配过程l次,l为自然数;以上步骤共执行z次,每次选取不同的k个初始簇,评分函数S等于在聚类过程中所有信息损失之和,当S值最小时,选择此时对应的方案为最佳方案。 |