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

有效

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

技術領域

本發明涉及一種基于控制集改進算法的社交網絡分層方法，屬于在線社交網絡技術領域。

背景技術

隨著信息技術的高速發展，大型數據庫與數據采集工具被廣泛應用于企業及政府的管理實踐中，這為人們帶來了大量原始數據，同時也對相關的數據處理技術提出了更高的要求。為了更有效地處理大型數據集，并從中發現有用的信息，多種數據挖掘技術應運而生，如分類技術、預測技術、聚類分析等等。

另一方面，在線社交網絡已經成為互聯網上發展最快的應用，如何從海量的社交數據中提取出有用的信息已成為重要的研究課題。例如，通過數據挖掘的方法，我們可以分析出用戶之間的相關性、購買興趣分布等實用信息，然后在不同的地區制定不同的營銷策略。

關于社交網絡的數據挖掘其研究內容非常廣泛，對網絡進行層次劃分也是其中之一。不難發現，在大量的社交網絡中都存在著不同的社交層次。比如，一些人比另一些人的人緣更好，一些人的舉動更能引起其他人的模仿等等，找到這樣的社交領袖團體不僅對于決策的制定者非常重要，對于執行者都有非比尋常的意義。而現在已有的關于社交網絡的結構分析方法，如社團發現、引文分析等方法等不能滿足確定社交影響者的目標，因此我們采用經典的圖控制集來解決這一問題。

而圖中的最小控制集是經典的NP-困難問題，它的確定性算法通常帶來復雜的數據結構和漫長的運行時間，實際運行效果并不理想。

發明內容

本發明提出了一種基于控制集改進算法的社交網絡分層方法，采用啟發式方法中的進化算法來求解最小控制集問題，進而對相關的社交網絡進行分層分析，不僅結構簡單，而且計算效率較高。

本發明為解決其技術問題采用如下技術方案：

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

所述步驟（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)。

本發明的有益效果如下：

（1）將社交網絡的有影響力團體抽象為圖的控制集，使得對不同分層方法的定量比較成為可能，同時此方法立意明確，可以方便地與其它分層策略組合使用。

（2）對于傳統的確定性算法，本發明所采用的進化算法結構更簡單，算法的執行效率更高，所帶來的實用性也更強。

附圖說明

圖1是本發明方法的原理示意圖。

圖2是經典的Zachary空手道俱樂部網絡結構圖。

圖3是本發明的進化算法中生成種群過程的流程圖。

圖4是本發明的進化算法進行一輪遺傳變異的流程圖。

圖5是空手道俱樂部網絡的分層示意圖，其中黑點為領袖團體。