%======================================================================
%
%?????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