首页 > 代码库 > A Node Influence Based Label Propagation Algorithm for Community detection in networks 文章算法实现的疑问

A Node Influence Based Label Propagation Algorithm for Community detection in networks 文章算法实现的疑问

2024-10-05 09:27:39   217人阅读

这是我最近看到的一篇论文，思路还是很清晰的，就是改进的LPA算法。改进的地方在两个方面：

（1）结合K-shell算法计算量了节点重重要度NI（node importance），标签更新顺序则按照NI由大到小的顺序更新

技术分享

     得到ks值后，载计算一下节点邻居ks值和度值d的比值

 

（2）当出现次数最多的标签不止一个时，再计算一下标签重要度LI（label importance）

技术分享

    其实就是找到节点相同标签的那些令居计算一个合值，看着也不难啊

（3）最后这个算法使用的是异步传播

下面是我实现的代码

function Labelnew=NIBlpa(A,alpha)
%  A Node Influence Based Label Propagation Algorithm for
% Community Detection in Networks
% [X,Y,Z] = NIBlpa(A，alpha)
% 
% Inputs: 
% k - clique size 
% A - adjacency matrix
% 
% Outputs: 
% X - detected communities 
% Y - all cliques (i.e. complete subgraphs that are not parts of larger
% complete subgraphs)
% Z - k-clique matrix
%
% Author : Yang Yang
% Email : bethansy@yahoo.com
ks=kshell(A);
n=size(A,1);
D=sum(A,2);
NI=ks;
label = 1:size(A,2);
%%
% calculate NI(node importance)
for i=1:n
    Nei=find(A(i,:)==1);
    NI(i,2)=ks(i,2)+alpha*sum(ks(Nei,2)./D(Nei));
end
sequence=sortrows(NI,-2);
%%
% Label propagation
    Label1 = label;
    Labelnew = Label1;
    
 while(1)
        for i=1:n
            % 找到邻居下标对应的标签
            nb_lables = Labelnew(A(sequence(i,1),:)==1);
          % 只考虑了每个节点至少有一个邻居，如果有孤立节点程序不运行保持原标签
            if size(nb_lables,2)>0
                x = HistRate(nb_lables);
                max_nb_labels = x(x(:,2)==max(x(:,2)),1);
                if size(max_nb_labels)==1
                    Labelnew(sequence(i,1))= max_nb_labels;
                else
                    LI=zeros(length(max_nb_labels),1);
                    for ma=1:length(max_nb_labels)
                        Nei=find(A(sequence(i),:));
                        index=Labelnew(Nei)==max_nb_labels(ma);
                        LI(ma)=sum(NI(Nei(index),2)./D(Nei(index)));
                    end
                   [~,maxx]=max(LI);
                   Labelnew(sequence(i,1))=max_nb_labels(maxx);
                end
            end
               
       end
        % 收敛条件,预防跳跃
        if Labelnew==Label1
            break;
        else
            Label1 = Labelnew;
               
        end
 end

　　下面是调用K-shell算法的代码

function [kvalue]=kshell(A)
%  A ：邻接矩阵
%  A=load(‘cdbBA_4000_5_0_.txt‘); 
% 
n=size(A,1);
kvalue=http://www.mamicode.com/zeros(n,2);>

　　但是后在几个数据集上测试效果都非常不好，例如karate上nmi只有0.2多，但是论文中作者得到的结果却是1，我已经把文章看了几遍还是找不出算法和作者哪里有出入，不过发现改进（2）的公式是错误的源头？抓头？？？其指教

 

A Node Influence Based Label Propagation Algorithm for Community detection in networks 文章算法实现的疑问


联系
我们