[發明專利]一種基于控制集改進算法的社交網絡分層方法

有效

• 申請號: 201310061114.2
• 申請日: 2013-02-27
• 公開（公告）號: CN103150360A
• 公開（公告）日: 2013-06-12
• 發明（設計）人: 彭茂;張媛
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/12
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 許方

1.一種基于控制集改進算法的社交網絡分層方法，其特征在于，包括如下三個步驟：（1）將社交網絡中的成員視作圖的頂點，若兩個成員之間有聯系，則在對應的兩點之間聯邊，如此則得到一個圖，然后將社交網絡的分層問題轉化為搜索圖的最小控制集問題；（2）用基于引導變異的的進化算法來搜索最小控制集；（3）將圖的控制集轉化為社交網絡的領袖團體以實現分層。

2.根據權利要求1所述的一種基于控制集改進算法的社交網絡分層方法，其特征在于所述步驟（2）中用基于引導變異的的進化算法來搜索最小控制集，包括如下步驟：

1）進行編碼轉換，將最小控制集問題轉換到進化算法所能處理的搜索空間中；

2）生成種群：

a）在????????????????????????????????????????????????個頂點的圖中，隨機選取個點，設為點集，在的基礎上隨機添加點集之外的點得到控制集，從中依次刪點，使其成為極小控制集，記為，即得到種群中的一個新個體；

b）重復步驟a）所述的修復過程次，即得到有個個體的進化算法種群，N是正整數；

3)遺傳變異:?

A)令時間，記個初始解分別為,,…,，其中為維向量；

B)從個解中留取其中頂點個數較少的個解，不妨設為,,…,，其中的頂點數最少；

C)定義引導向量為

，

其中為種群大小，為取自種群的點數較少之個體的數量，為進化算法的學習系數；

D)對進行變異系數為引導向量為的引導變異，為介于0和1之間的實數：設，其中每一元素以概率發生變異，若變異，則以概率成為1，以概率成為0；

E)記步驟D）所生成的新的向量為，對向量進行如生成種群中步驟a）的修復過程，得到種群中的一個新個體；

F)重復進行步驟D)和E）兩步，直到生成個新解，連同生成種群中步驟b)中留取的個好解，組成新一代的種群；

G)令，判斷此時生成的種群是否收斂為同一解，或者遺傳變異次數達到預設的上界，如果成立，則遺傳變異過程結束；否則循環執行步驟A)--F)。