社区发现算法

基于相似度的社区发现分裂算法，包括GML文件的读取，相似度计算等，有实例文件可进行实验。

%======================================================================
%
%     Communities Finding 
%     注意，这个方法中有个问题
%     在数据预处理节点要去掉一度节点，但是不代表预处理后该图中没有一度节点存在
%     如果一个节点的度为2，并且其中的一个边连接了一个一度节点，那么。。。。。。
%
%======================================================================

clc;clear
%=====================================================================
%% 1.   数据初始化

%获得图信息
Directed_Graph = 0;             %表示是有向图还是无向图：0为无向图、1为有向图
NodeNum        = 0;             %节点的个数
EdgeNum        = 0;             %边的个数
NodeID         = 0;                  %存储节点编号
NetworkDataAdj      = 0;             %网路的邻接矩阵
[NetworkDataAdj NodeID NodeNum EdgeNum Directed_Graph] = ReadGML（NetworkDataAdj NodeID NodeNum EdgeNum Directed_Graph）;

i_weak            = 1;                             %表示用强社团还是弱社团定义确定社团结构 1表示弱社团定义  0 表示强社团定义

NodeNum           = size（NetworkDataAdj 1）;       %图中的点数
EdgeNum           = 0;                             %图中的边数
MaxCommunitiesNum = 1;                             %已经划分出了几个社团，初始值为1
CommunitiesIndex_final  = zeros（1NodeNum） ;       %存放最终各个节点所在的社团标号

i_weak            = 1;                             %表示用强社团还是弱社团定义确定社团结构 1表示弱社团定义  0 表示强社团定义

%==========================================================================
%%  2.   网络数据预处理

%去掉那些只与一个点相连的节点
DeleteNodes = ones（1NodeNum）;
LeftNodes   = 0;    %保留下的节点数目

%检索网络节点，确定1度节点的位置和数目
for i = 1 : NodeNum;
    NumOfAdjNode = 0;   %标识节点i直接与几个节点相连
    for j = 1 : NodeNum;
        if NetworkDataAdj（ij） ~= 0
            NumOfAdjNode = NumOfAdjNode + 1;
            EdgeNum      = EdgeNum      + 1;
        end
    end

    if NumOfAdjNode >= 2
        DeleteNodes（i） = 0;
        LeftNodes = LeftNodes + 1;
    end
end

EdgeNum = EdgeNum / 2;  %求得图中的边数

%将1度节点所占的行和列去掉
NetworkData = zeros（LeftNodes LeftNodes）;    %存储预处理后的网络结构
CommunitiesIndex = ones（1LeftNodes）;         %标识各节点属于哪个社团，初值为所有节点都属于1社团
Data_k = 0; 
Data_l = 0;

for i = 1 : NodeNum
    Data_l = 0;
    if DeleteNodes（i） == 0
          Data_k = Data_k + 1;
          for j = 1 : NodeNum
            if DeleteNodes（j） == 0
                Data_l = Data_l + 1;
                NetworkData（Data_kData_l） = NetworkDataAdj（ij）;
            end
          end
    end
end

%求各个节点的度
k_Node = zeros（1 LeftNodes）;                      %记录各个节点的度数
k_Node_Step = zeros（1 LeftNodes）;                 %记录当前步中各个节点的度数，防止出现一度节点再次被孤立的情况
for i = 1 : LeftNodes
    row = find（ NetworkData（i :） ）;
    k_Node（i） = size（ row 2）;
end
k_Node_Step = k_Node;
%==========================================================================
%%  3.   社团寻找算法

NetworkData_backup_1 = NetworkData;                 %保存网络原始数据
Similarity_Matrix = zeros（LeftNodes LeftNodes）;    %初始化网络节点的相似度矩阵

%--------------------------------------------------------------------------
%寻找相似度最大的节点，并逐步添加边
%或者寻找相似度最小的节点，逐步减少边

%判断是否分裂出社团
Flag_IsCommunities   = 1;  %初始值赋1是指最初将整个网络看做一个大社团
Flag_IsCommunitie

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       7098  2010-06-28 20:32  Detecting Community based on similarity\Community_Finding.m

     文件       5965  2012-02-25 17:33  Detecting Community based on similarity\Community_Finding_Excel.m

     文件       6472  2012-12-01 20:36  Detecting Community based on similarity\Community_Finding_GML.m

     文件        470  2010-07-01 10:34  Detecting Community based on similarity\ConvertToxml.m

     文件       3530  2010-06-11 23:27  Detecting Community based on similarity\dfs.m

     文件       9518  2006-07-26 15:04  Detecting Community based on similarity\dolphins.gml

     文件       1434  2010-06-11 19:06  Detecting Community based on similarity\FindTag.m

     文件      33507  2006-07-22 05:32  Detecting Community based on similarity\football.gml

     文件       1460  2010-06-06 20:24  Detecting Community based on similarity\IsFindingCommunities.m

     文件        693  2010-05-31 19:15  Detecting Community based on similarity\IsFindingSubgraph.m

     文件       4194  2006-07-21 12:39  Detecting Community based on similarity\karate.gml

     文件       1227  2010-06-21 09:54  Detecting Community based on similarity\MinSimilarity.m

     文件      32256  2010-06-03 18:31  Detecting Community based on similarity\Network_Data_Krate.xls

     文件       5365  2012-12-01 20:36  Detecting Community based on similarity\ReadGML.m

     文件       1906  2010-06-21 09:31  Detecting Community based on similarity\Similarity.m

     目录          0  2012-12-01 20:37  Detecting Community based on similarity

----------- ---------  ---------- -----  ----

               115095                    16