一種基於節點Jaccard相似度的社交網絡社團發現方法

2023-05-23 22:14:11 2

一種基於節點Jaccard相似度的社交網絡社團發現方法
【專利摘要】本發明公開了一種基於節點Jaccard相似度的社交網絡社團發現方法，包括：對網絡數據進行預處理;根據Jaccard相似度算法計算出每對節點的相似度；初始將每個節點分別看作一個社團；聚合相似度最高的社團；再次聚合根據所得社團計算的相似度最高的社團，直至網絡中沒有再能聚合的社團。本發明提出了通過計算社團點之間的Jaccard相似度採用層次聚類的思想進行社團劃分的方法，有益效果為：在計算機處理過程中使用該方法較為簡單、靈活；在社交網絡計算中能準確的發現出用戶所需的網絡社團。
【專利說明】—種基於節點Jaccard相似度的社交網絡社團發現方法
[0001]【技術領域】
本發明公開了一種基於節點Jaccard相似度的社交網絡社團發現方法，屬於複雜網絡技術，具體地說是一種社交網絡的社團發現技術。
【背景技術】
[0002]近幾年,社交網絡的發展如火如荼，國外的知名社交網站如Facebook、Twitter及Google+等，國內有人人網、QQ朋友網等等。從某種意義上說，社交網絡是現實網絡的一種映射。研究發現很多現實網絡是具有社團結構的，通過分析，可以根據用戶需求找到用戶感興趣的社團。現今人們對網絡中的社團劃分算法已經做了相當多的研究工作，已成為當前重要的學科研究領域之一。
[0003]在研究社團劃分算法時，通常將網絡用圖來描述，即由節點集合V和邊集合E組成的圖G=(V，E)可表示一個網絡。歸納圖形分割研究而發展起來的算法如下:
Kernighan-Lin算法是一種基於貪婪算法原理的二分法。其基本原理是:定義一個增益函數Q，Q為兩個社團內部的邊數與連接兩個社團之間的邊數之差，之後尋找使Q值最大的劃分方法。KL算法只採用最好的候選解，而拒絕接受所有較差的候選解，因此所找的是局部最優解而不是全局最優解。此外這種二分法最大的局限性在於事先知道社團的個數和社團的規模，用先驗知識產生一個較好的初始社團結構；該算法對其初始解非常敏感，不好的初始解往往導致緩慢的收斂和較差的最終解。由此可見KL很難應用於不預先得知的網絡大小的實際網絡分析中。
[0004]基於Laplace矩陣特徵值的譜平分法最先在計算機圖形分割中被應用，它之所以在圖形分割中有著較好的劃分效果，是由於以嚴密的數學理論依據為指導的。它的基本思想是:基於一個無向圖G對應的對稱矩陣L，根據它的不同特徵值對應的不同特徵向量來確定網絡的劃分。由分析可知:在複雜網絡劃分中可以根據網絡對應的Laplace矩陣的第二小的特徵值將其首先分為2個社團，再對每個社團迭代進行劃分，直到劃分得到實際的網絡，再此迭代過程中往往出現錯誤的劃分，效果並不理想；譜平分法每次只能將網絡平分，如果一個網絡存在多個社團，就必須對子社團多次重複劃分，然而多次劃分必然依賴於第一次劃分的正確性；分析複雜網絡比較耗時；所以該算法不適合多社團或者多節點存在模糊性的複雜網絡。
[0005]基於層次聚類發展而來的算法有很多，這類算法主要又分為兩類:
(I)凝聚類算法，這種算法是自下而上的，其思想是首先將網絡中的每個節點劃分為單獨的一個社團，然後基於社團聚合規則將不同的小社團聚合成更大的社團，直到滿足要求為止；(2)分裂類方法，這種算法是自上而下的，其思想是首先將整個網絡看成一個社團，然後依據社團劃分規則，不停的將大的社團劃分為較小的社團。
[0006]GN算法是一個基於邊介數的社團發現算法，是典型的分裂方法。GN算法的基本原理是從網絡中逐步移去介數最大的邊。GN算法的基本步驟如下:
步驟1:計算複雜網絡中所有邊的邊介數；步驟2:比較網絡中所有的邊介數並移除邊介數最高的邊；
步驟3:重複執行步驟I和2，直到每個節點就是一個獨立的社團。
[0007]GN算法雖然克服了之前算法僅能二分的缺點，但沒有一個量的定義，即不能判斷網絡的社團分解到什麼程度才算是最合適；而且求取邊介數這一個重要步驟耗時比較長，每次移除邊介數最高的邊之後，都要重新計算網絡的邊介數。
[0008]Newman快速算法是一種典型的凝聚算法。Newman快速算法借鑑了層次聚類算法的思想，基於協調混合定義了一個衡量網絡劃分質量的標準，度模塊。算法首先將網絡中的所有節點初始化為一個社團，即初始時，一個社團只包含一個節點，此外A個社團構成的左階方陣A= (A7)初始化為:
【權利要求】
1.一種基於節點Jaccard相似度的社交網絡社團發現方法,包括以下步驟: 步驟一:對社交網絡數據進行預處理，其中包括:將社交網絡中的用戶抽象成網絡中的節點，獲取包括所有節點構成的集合，兩節點之間邊構成的集合； 步驟二:根據步驟一預處理的結果通過Jaccard相似度的計算方法計算出所述社交網絡中的每兩個節點的Jaccard相似度； 所述兩節點的Jaccard相似度計算方法如下； 2-1具體地，計算社交網絡數據中任意節點i和節點j的Jaccard相似度:首先分別獲取與節點i或節點j相互連接的各個節點以及包含節點i或j本身的節點的集合，既集合Vi或集合Vj ； 2-2計算節點i和節點j的Jaccard相似度:集合Vi和Vj的交集與併集的比值，即SIM (Vi, Vj) = (Vi n Vj)/(Vi U Vj)； 步驟三:根據步驟一所得的所有節點和步驟二所得每對節點的相似度，組成一個節點相似度矩陣； 步驟四:選擇步驟三所述節點相似度矩陣中相似度最大的進行聚合，由此獲得新的社團； 步驟五:計算所述社交網絡數據中兩個社團之間的Jaccard相似度； 所述兩個社團之間的Jaccard相似度計算方法如下: 5-1具體地，計算社交網絡數據中任意社團k和社團I的Jaccard相似度:首先獲取來自社團k的任意節點m和來自社團I的任意節點η ； 5-2如所述步驟二的方法計算節點m和節點η的Jaccard相似度； 5-3重複5-1步驟至5-2步驟計算出分別來自社團k和社團I組成的所有節點對的相似度； 5-4根據步驟5-3得出的社團k和社團I的每對節點相似度並根據結果求出平均值，既兩個社團之間的Jaccard相似度； 步驟六:根據所述步驟五的方法計算社交網絡數據中所有社團間的Jaccard相似度；步驟七:根據所述社交網絡數據中社團和所述步驟六計算的結果，構成網絡中各個社團的社團相似度矩陣； 步驟八:根據步驟七所述社團相似度矩陣中相似度最大的社團進行聚合，構成新的社團； 步驟九:重複步驟五至步驟八，直到整個網絡聚合成一個社團為止。
2.根據權利要求1所述一種基於節點Jaccard相似度的社交網絡社團發現方法，其特徵包含:所述步驟三得到所訴節點相似度矩陣後，將社團網絡數據中每一個節點初始化為一個社團。
3.根據權利要求1所訴的一種基於節點Jaccard相似度的社交網絡社團發現方法，其特徵包含:所述對社交網絡數據進行預處理，可獲得一個鄰接矩陣，所述鄰接矩陣中的元素只有I和O，I表示行和列代表的節點相連，O表示行和列代表的節點不相連。
4.根據權利要求1所述的一種基於節點Jaccard相似度的社交網絡社團發現方法，其特徵包含:兩個社團之間的Jaccard相似度，所述步驟五中5_1或5_3需獲取的節點對必須分別來自所求的兩個社團。
【文檔編號】G06F17/30GK103838803SQ201310154663
【公開日】2014年6月4日 申請日期:2013年4月28日 優先權日:2013年4月28日
【發明者】張小松, 牛偉納, 羅強, 李建彬, 廖軍, 張可, 陳瑞東, 王東, 李宏鳶 申請人:電子科技大學