[發明專利]一種融合節點分析與邊分析的復雜網絡社區識別方法

有效

• 申請號: 202010516378.2
• 申請日: 2020-06-09
• 公開（公告）號: CN111698743B
• 公開（公告）日: 2022-09-13
• 發明（設計）人: 鄧琨;蔣慶豐;劉星妍
• 申請（專利權）人: 嘉興學院
• 主分類號: H04W36/00
• 分類號: H04W36/00;H04W48/16;G06Q50/00
• 代理公司: 北京勁創知識產權代理事務所(普通合伙) 11589
• 代理人: 徐家升

1.一種融合節點分析與邊分析的復雜網絡社區識別方法，其特征在于：包括初始化邊社區階段、擴展邊社區階段及擴展節點社區階段3個階段；

所述初始化邊社區階段，具體為：

初始化邊社區階段首先搜索網絡中度較高的若干節點作為初始化邊社區階段的中心節點，然后將與中心節點相連的邊歸屬為同一社區，完成初始化邊社區階段；

該階段首先從網絡中任意節點v_i開始搜索，若其周圍鄰居節點中度最大節點v_j的度大于或等于當前節點v_i的度，則將v_j作為當前節點，繼續搜索鄰居節點中度更大的節點，反復執行這一過程，直到當前節點為鄰居節點中度最大的節點，那么當前節點即作為一個中心節點；然后，算法從未被搜索過的區域中，繼續搜索中心節點，直到網絡中全部節點均被搜索過為止；最后，將與中心節點存在連接的邊歸屬為同一社區，則完成初始化邊社區階段，進入擴展邊社區階段；

所述擴展邊社區階段，具體為：

該階段以初始化邊社區階段所產生的初始化邊社區作為輸入，具體為，若任意邊e_v,v′所連接兩個節點v,v′與社區LC_i中節點u是共同鄰居節點，若將邊e_v,v′加入社區LC_i，使得LC_i中形成三角形的數量與邊數的比例值增加，則將該邊加入社區LC_i中；或者在社區LC_i中的邊e_tt′的兩個節點t、t'均與社區外的節點s有邊相連，若將邊e_ts和邊e_t′s加入到社區LC_i中，使得社區緊密度增加，則將邊e_ts與e_t′s歸屬到社區LC_i中；反復執行該操作，直到網絡中沒有邊再能夠加入任意社區，此階段完成；

所述擴展節點社區階段，具體為：

該階段首先將擴展邊社區階段所得的邊社區結構轉換為節點社區；然后，反復計算由孤立邊轉換而產生的孤立節點與周圍鄰接社區的連接緊密度，也就是使任意節點i加入到社區C_i產生新的社區C_i′，當C_i′內的邊數與C_i′外的邊數的比例數大于社區C_i內的邊數與C_i外的邊數的比例數時，則將節點i加入到社區C_i，否則，不將節點i加入到社區C_i；最后，算法進一步分析社區中的重疊節點，以提高社區識別的準確率，即計算重疊節點與其所屬社區的社區內邊數與社區外邊數的比例數，若存在重疊節點歸屬于某一社區，使社區內與社區外邊數的比例降低，則將此重疊節點從該社區中刪除；

經過所述3個階段操作，若依然存在某節點未屬于任何社區，則說明該節點歸屬于周圍任一鄰接社區均會使社區緊密度降低，此時將該節點加入到使社區內邊數與社區外邊數比例降低最小的那個社區中，反復執行以上操作，直到網絡中不存在孤立點，以及所有重疊節點均被分析過為止。