基于多維混合圖和核心節點的社團發現算法
2019-07-08 07:09:26祝周石琳孔祥順
網絡空間安全 2019年2期
祝周 石琳 孔祥順
摘? ?要：社區發現和好友推薦算法一直是復雜網絡的研究熱點之一，在公安業務工作、網絡輿情控制、電子商務等領域具有重要的意義。為解決公安工作中防范恐怖主義事件、打擊易復發類犯罪、穩控重點群體等突出難題，論文提出了一種基于核心種子節點擴展的啟發式社團發現算法。該算法通過有效融合多維信息形成混合圖，以種子節點作為初始社區，綜合考慮人物節點間不同交互行為和關聯行為的權重，依托實戰重點將協同過濾、Tanimoto系數、六度空間理論等算法相結合，最后把社區鄰接節點中的活躍節點降序排列作為重點社團目標，得到了一種有核心節點的基于“人、事、地、網、組織”五維混合圖的社團發現數據模型，為警務大數據及其他應用提供支撐。
關鍵詞：混合圖;核心節點;鏈接度;社團發現
中圖分類號：TP391? ? ? ? ? 文獻標識碼：A
Community detection method based on multidimensional mixed graph and core nodes
Zhu Zhou， Shi Lin， Kong Xiangshun
（Anshan Public Security Bureau of Liaoning， LiaoningAnshan 114000）
Abstract： Community detection and friend recommendation algorithms have always been one of the research hotspots in complex networks. It is of great significance in the field of public security business， network public opinion control， electronic commerce and other fields. To solve the problems of preventing counter-terrorism， combating the recurrence of crime and stabilizing key groups， this paper presents a heuristic community detection method based on core seed nodes extension. The method effectively fuses multidimensional mixed graph， and it considers user interaction and association behavior weight comprehensively. Seed nodes are used as the initial community. Relying on the actual combat， we focus on the combination of collaborative filtering， Tanimoto coefficient， Six Degrees of Separation and other algorithms. Finally， the active nodes in the neighboring nodes of the community are ranked in descending order as the key community targets. A data model of community detection based on five-dimensional mixed graph of people， events， places， networks and organizations with core nodes is obtained. It provides support for police big data and other applications.
Key words： mixed graph; core nodes; link degree; community detection
1 引言
近年來，以手機[1]、微信、微博等社交網絡（Social Network）為代表的社會媒體逐漸成為人們日常生活中重要的交流平臺，呈現出獨特的網絡特征[2]，現實與網絡已難以分割。由于社交網絡平臺的多樣性、隱匿性和開放性等原因，導致公安機關在解決防范恐怖主義事件、打擊易復發類犯罪、穩控重點群體等突出問題時難上加難。如何充分利用互聯網社交網絡關系數據，虛實結合、挖掘目標、發現社團、獲取情報、查找重心，已成為當前基層公安工作的一項非常重要的業務需求[3]。通過研究社團中已知人員目標，分析其多種社交網絡工具產生的虛實數據，引入多維關系云圖、核心節點、鏈接度等概念，重點將協同過濾[4，5]、Tanimoto系數等好友推薦及社團發現算法相結合，以期得到一種有核心節點的基于“人、事、地、網、組織”五維混合圖的社團發現數據模型。
2? 相關研究
在基層警務工作中，通過已知目標挖掘其重要關系人[6]，要面對多種社交網絡工具產生的具有稀疏性和多樣性的數據信息，分析過程極其復雜，受工作意識、技戰術水平等制約，個人需求難以得到滿足，因此如何利用多種社交網絡信息快速發現潛在的工作目標成為巨大挑戰。在傳統的根據社交網絡圖計算用戶相似度的方法中， 或直接計算目標相似度而較少考慮好友的影響，或者將所有好友賦予相同權重， 即考慮了關系數量卻沒有區分重要性。
目前，流行的推薦方法基于一個假設：兩個用戶越相似，則他們越有可能成為朋友。有三種主要的方法刻畫用戶的相似度：基于用戶的屬性特征、基于網絡結構的局部特性和基于網絡結構的全局特性。
（1）基于用戶屬性特征的方法進行朋友推薦[7]的思想是通過機器學習的手段，分析出不同類型的屬性對用戶的貢獻度不同，將其分類處理?；谠摲诸?，提出的算法可以在掌握用戶基本資料以及近期行為的基礎上，搜索出與之相關性更強的好友或能夠引發其興趣點的商品，用來快速、準確、全面地得到用戶與其好友之間親疏程度排序及分類的結果，如果兩個用戶具有相同的年齡、性別、學?；蛘叩攸c等，則他們更加相似，也就更加可能成為朋友。
（2）基于網絡結構的局部特征的方法利用用戶朋友網絡結構的局部結構信息。有很多局部相似性測量指標[8]，如共同鄰居（Common Neighbor，CN）、Jaccard和Adamic/Adar等。CN也叫FOAF算法，被很多流行的OSNs所采用。它考慮兩個頂點的共同鄰居的數量，如果兩個用戶的共同朋友越多，則他們越可能形成鏈接。設N（x）表示頂點x的鄰居的集合，則頂點x與y的相似性為：。Jaccard方法不僅考慮了共同鄰居的數量，還考慮到兩個用戶擁有的鄰居數量，即 。Adamic/Adar也考慮兩頂點共同鄰居的度信息，并且認為度小的共同鄰居節點的貢獻大于度大的共同鄰居節點，根據共同鄰居節點的度為每個頂點賦予一個權重值，該權重等于該頂點的度的對數的倒數，，一些研究表明，Adamic/Adar在局部特性指標中具有最好的性能[9]。
（3）基于網絡全局特征方法偵測朋友社交網絡的所有路徑的結構，其中Google網頁排序算法PageRank的拓展算法——重啟動隨機游走算法（Random Walk with Restart，RWR）吸引了很多研究領域學者的興趣。RWR算法[10，11]是一個基于圖的隨機游走馬爾科夫鏈模型。相比于其他的相似性算法，RWR方法具有捕捉圖形全局結構以及頂點之間多側面關系等優點。
上述方法僅利用社交網絡中用戶朋友網絡信息，而在社交網絡數據中常常包含多種對象和網絡關系[12]。本文以推薦算法來挖掘重要關系人，擴展了單項網絡關系，基于多子網復合復雜網絡[10]，融合了多種關系，引入鏈接度[13，14]來描述目標的相似度，得到與核心節點的核心鏈接度來確定重點目標。
3 基于多子網復合復雜網絡的社團發現算法
3.1 基本思想
社交關系網絡是多維網絡，包含多種對象與網絡關系，對象之間的網絡關系受多種因素的影響。本文將對象之間多種關聯行為劃分為交互類和關聯類，構建各類型的單一關系網絡，以關系人物為節點將多個子網復合成復雜的關系網絡云圖，借用了社團發現的局部節點模型[13]、好友推薦的共同鄰居模型、文本分類的向量空間模型等數據模型，定義了關系云圖、核心節點、鏈接度等概念[13，14]，結合實戰對不同的邊設置了不同權重，再使用協同過濾、Tanimoto系數、六度空間[15，16]等理論算法計算鏈接度，最后分析與核心種子節點社區相鄰接的活躍節點鏈接度數值關系，鎖定重點目標或劃出社團。
3.2 多子網關系云圖構建
基于社交網絡全局特征來表達網絡中所有可能的結構，定義一個以關系人物為節點的多子網關系云圖[10]，融合多種對象和多種關系，使結果能夠真實反映對象間的交互度和相似度，具體分為六個步驟。
（1）構建核心節點的社交網絡數據倉庫。從互聯網多渠道抽取社交網絡工具數據信息、從電信運營商若干電信通訊基站抽取通訊記錄數據信息[1]、從公安管理以及其他方法獲取的虛實數據信息，清洗后作為數據源。
（2）利用數據源中人物與人物之間的關聯，組織與人物之間的關聯，位置與人物之間的關聯，考慮整個網絡中各節點之間的聯系，組建關系云圖G，以G=（V，A，E）表示。
（3）V表示節點集合，包含四種類型節點Vu、Vc、Vp、Vt。其中，Vu為人物節點集合，Vc為人物參加的組織節點集合，Vp為位置節點集合，Vt為各類型頂點集合，即V=Vu∪Vc∪Vp∪Vt。因數據來源不一，人物使用的各類社交網絡工具不具有唯一性，人物節點的各屬性并非齊備完整，人物節點的唯一標識使用獨立的唯一標識，而不使用身份證、社交網絡工具ID等屬性類標識。
（4）A是人物節點的屬性集合，其中，AVi為人物節點Vi所擁有的屬性集合?，F主要包含六種類型頂點Ac、At、Asn、Aid、Axm、Asfz。其中，Ac為組織屬性，At為手機號碼屬性，Asn為社交網絡工具屬性，Aid為人物唯一標識屬性，Axm為姓名屬性，Asfz為身份證號碼屬性。各人物節點的社交工具種類及號碼、手機號碼等可能有多個，因而其屬性記錄的數據也并非唯一值，假設人物節點Vi有Numx種社交工具及相應號碼，有Numy個手機號碼，參加了Numz個組織或圈子，則Avi={Aid∪Asfz∪Axm∪Acz∪Asnx∪Aty，Numx?|Asn|，Numy?|At|，Numz?|Ac | }。
（5）E是邊的集合，主要邊的類型有Esnj、Ecj、Etk、Ep。其中，Esnj為社交網絡工具好友關系集合，如果人物Vu1和Vu2之間存在好友（含關注）聯系，每增加一種社交網絡工具好友則相應增加一條關系邊。Ecj為關系人組織群體關系集合，如果人物Vu1和Vu2之間存在相同的組織群體（含圈子、群組）聯系，每增加一個相同的組織群體，則相應在兩個人物節點與組織節點之間分別增加一條關系邊。Etk為關系人手機通訊關系集合，如果節點Vu1和Vu2之間存在手機通訊聯系，每增加一種（非一次）手機通訊關系則相應增加一條關系邊。Ep為關系人位置交互關系集合，如果人物節點Vu1和Vu2之間存在相同的位置聯系，每增加一個相同的位置則相應分別增加一條關系邊，Ep包含現實位置關系與虛擬位置關系兩種情形。
（6）關系云圖中有的關系邊是有向的，有的是無向的，因此統一成一個有向圖，將無向邊表示為兩條有向弧，各關系邊都是帶有權值的。
3.3? 關聯類相似度加權網絡構建
關系云圖的拓撲結構，僅表示個人在社會交往中的范圍，連接節點的邊越多表示這個人的交際范圍越廣，但是很難準確分析與其關系最密切的人是誰。現實中各種社交網絡工具邊上的權重具有非常重要的意義，親密度不同的人物之間，所存在的社交網絡工具邊的數量及種類有很大區別，而邊權越大關系越密切。本文構建了交互加權網絡作為基礎網絡，主要方法如下。
（1）歸一化處理每一條邊上的權值，使其取值范圍為（0，1）。
（2）結合工作實際，使用層次分析法創建各節點之間虛擬屬性邊的重要度矩陣，得出各虛擬邊弧的權值。
（3）主要計算各類社交網絡工具邊權、各類手機通訊邊權、各類組織圈子關系[17]邊權等關聯虛擬類邊權。
（4）Wij代表兩個人物節點Vi和Vj之間的各類虛擬邊（非位置類邊）的權重總值，即為兩個人物節點間各類虛擬非位置邊權的總和。
（5）位置類邊權值因作用特殊另行計算。
3.4? 交互類虛擬位置相似度計算
基于位置的社交網絡服務是利用GPS、蜂窩網、WLAN等技術獲得移動終端的地理位置信息，支持用戶隨時隨地自由記錄并分享地理位置等信息。而位置維度的社團發現，可根據社交網絡服務或其他方法獲取的地理位置信息，借用文本分類的向量空間模型[18]。即以位置向量來描述人物，將每個位置作為向量空間坐標系的一維，人物被形式化為多維空間向量中的一個向量。在多維向量空間模型中，使用TF-IDF權重計算方法計算某一維向量值，而人物節點的位置相似度用Tanimoto系數進行計算，主要方法如下。
（1）位置向量包含基站位置和IP地址兩類數據，即以基站和IP地址作為核心數據。
（2）標準化處理的傳統的TF，以nfiL表示人物i在位置L出現的頻數，以Pi表示人物i的位置集合，以表示人物i在所有位置中頻數的最大值，公式如下：
（3）修正并規范后的IDF，以表示人物i的位置集合中所有頻數的和，fiL表示人物i的位置L在人物i位置集合中的頻率，fjL表示人物j的位置L在人物j位置集合中的頻率，公式如下：
（4）為解決數據稀疏及單一性問題，結合實戰以提升位置頻數對實際相似度的影響準確率，本文對fiL=1時的頻數nfiL進行歸一化處理以hiL表示，以WiL表示人物i向量在位置L維度上的向量值，也是人物節點i與位置節點L間邊的權重，公式如下：
（5）使用Tanimoto系數計算人物節點i和j的虛擬位置相似度Psim （Vi，Vj），公式如下：
3.5? 交互類現實位置相似度計算
如果關系云圖中人物節點之間存在公安工作或其他方式獲取的現實位置數據邊Ep，要單獨計算其現實位置相似度。現實位置相似度[19]是反映兩個人物節點相似性最重要的指標，因為其代表了兩個人物曾在同一時間、同一地點發生過極為親密的行為。本文在此項計算中使用了指數函數，兩個人物如果僅有幾次交集，可能是偶然行為，但隨著近期內現實交集行為的數量增多，就更有可能有著相似的工作生活圈，因此相似度應該隨著交互行為數量的上升而上升，并且上升趨勢是先慢后快。人物i和j的現實位置交集頻數用Lij表示，將Lij+0.01作為分母視為收縮參數，對數據歸一化處理，利用指數函數算法，常數e約為2.71828，則人物節點i和j的現實位置相似度Lsim （Vi，Vj），公式如下：
3.6? 鏈接度的定義
在關系云圖中，綜合衡量拓撲結構和各節點之間邊權，本文定義了兩個人物節點Vi和Vj間的鏈接度Vsim （Vi，Vj），來描述各人物之間的相似度。由于社交網絡具有小世界特性[20]，大部分節點可以從其他任一節點經少數幾步到達。即使兩個節點沒有直接相連或者沒有共同鄰居節點，他們之間仍然存在某種聯系，這種聯系通過節點之間最短路徑進行傳遞。因此，對于直接相連的人物，他們的相似度與彼此之間路徑的權重以及與共同好友的權重相關;對于不直接相連的人物，他們的相似度為他們之間的最短路徑上所有節點對的相似度的乘積，路徑越長，相似度越低。當存在多條最短路徑時，取乘積較大者作為他們的相似度。根據六度分隔理論[15，16]，世界上任意兩人之間所間隔的人數平均不超過六人。因此，當兩個人物節點之間路徑長度大于 6 時，則認為他們的緊密程度近似為零。以Ni和Nj分別代表人物節點i和節點j的鄰居節點集合，以pathij表示人物節點i和節點j之間的最短路徑。用戶節點之間的鏈接度Vsim （Vi，Vj）及用戶節點Vi與其他節點Vx（非人物節點）之間的權值Vsim （Vi，Vx）算法定義如下：
（1）Vi，Vj相鄰
（2）
（3）
（4）
3.7? 總鏈接度和核心鏈接度的定義
根據警務實戰，分別將人物節點i和j之間的位置等屬性邊權值與鏈接度賦予權重α進行計算，得到人物節點i和j的總鏈接度Tsim （Vi，Vj）。以Vk表示核心節點集，為獲取以核心節點為中心的社團，用核心鏈接度Csim （Vi）表示人物節點i到各不同權重β的核心節點的總鏈接度之和，如暫無經驗權重則默認取1，可通過機器學習，逐步獲取各經驗權重，具體公式如下：
（1）
（2）
3.8? 算法設計
輸入：關系云圖G=（V=Vu∪Vc∪Vp∪Vt，A=Ac∪At∪Asn∪Aid∪Axm∪Asfz，E=Esnj∪Ecj∪Etk∪Ep），核心節點集Vk，各類案事件權重調節參數α和各核心節點的權重調節參數β。
輸出：按核心鏈接度降序排名各關系人物列表。
方法：
（1）輸入待分析的核心節點集Vk及其對應的關系云圖G，并設定好相關權重參數;
（2）迭代計算每一個節點的相關屬性的關聯度，以增減節點;
（3）計算G中每一個人物節點的交互類虛擬位置相似度;
（4）計算G中每一個人物節點的交互類現實位置相似度;
（5）計算G中每一個人物節點的鏈接度;
（6）根據（3）（4）（5）的結果計算各人物節點的總鏈接度;
（7）根據（6）的總鏈接度計算各人物節點的核心鏈接度;
（8）將各節點的核心鏈接度降序排列，據此確定各人物節點與核心節點間的相互關系，劃分重點目標與社團。
3.9? 算法實驗
本文對社交網絡工具數據、通訊記錄數據以及其他方法獲取的虛實數據信息進行了模擬，建立實驗數據集來測試算法的準確性和可操作性。實驗在Windows Server 2008 R2的環境下使用Python語言運行。
（1）實驗構建了四次某犯罪團伙三個已知目標的社交網絡虛實數據倉庫。
（2）利用層次分析法確定了社交網絡工具微信邊權Wsnwx=0.34，社交網絡工具微博邊權Wsnwb=0.16，手機通訊記錄邊權Wt1=0.34等。
（3）將數據倉庫內的數據輸入算法形成關系云圖，并將權重調節參數α1、α2、α3、β均賦值為1。
（4）利用本文中多維混合圖和核心節點的社團發現算法對四次實驗數據進行了分析挖掘，與人工分析出的犯罪組織重點人員為參照，均成功的按核心鏈接度的高低挖掘出犯罪團伙中的重點人員，準確程度在88%以上。
4? 總結與展望
本文算法的實現包括模型構建和算法設計。在闡述各個模塊構建過程中，詳細介紹了關系云圖的構建和各類權重計算及設置方法，在云圖的構建中為了充分反映人物多種社交網絡工具的關系特征，精準預測其關聯性，綜合考慮了多種類虛實邊關系。在權重設置中，根據云圖中頂點的關聯度和交互度，借用好友推薦的共同鄰居模型、文本分類的向量空間模型等賦予人物社會化行為相應的權重。最后利用核心鏈接度準確計算關系云圖中各人物節點的與初始核心節點間的關聯相似度，得出最終人物推薦列表以鎖定團伙目標。
此模型研究是將多種傳統警務技戰法及大數據社會網絡分析研究領域進行深度融合的一種嘗試，需要緊緊依托于公安大數據的發展，存在不足之處。首先，混合圖中的節點包括人物、位置、圈子等多種類型，算法的空間消耗很高。其次，本文提出的基于混合圖的各綜合算法仍賦予了鏈接度大的人物過大的挖掘推薦強度，對于某些鏈接度小但更為重點的特殊人物節點挖掘多樣性不高。在今后的研究中，應當從數據挖掘角度進一步在發現社團、研究社團內部交互模式以及預測社團的模型上進行深入廣泛的分析和探討，逐步探索擴展六度空間理論的多層次關系，積累各類案事件不同的權值，特別要提高一些鏈接度小的特殊關鍵目標人物推薦強度，提高算法的準確性。
5? 結束語
針對目前社會網絡環境及各類個性化通訊服務現狀，結合警務工作實際，本文提出基于社交網絡及通訊痕跡中人物關聯關系視角下的分析模式，參考OSNs中主流的推薦算法，設計了一種基于復雜混合圖的社團挖掘算法模型，將各種社交網絡及通訊痕跡中的人物關系網絡和位置等社會化交互行為融入模型，更有效地解決了公安工作中快速挖掘重點目標和社團問題。
參考文獻
[1] 高建強，譚劍，崔永發.一種基于通訊痕跡的社會網絡團伙分析模型[J].計算機應用與軟件，2012，29（3）：206-208.
[2] 劉小玲，譚宗穎.復雜網絡社團結構劃分算法的情報學應用研究[J].圖書館學研究，2011，（8）：20-25.
[3] 楊莉莉，楊永川.基于社會網絡的犯罪組織關系挖掘[J].計算機工程，2009，35（15）：91-93.
[4] Das A， Datar M， Garg A， et al. Google News Personalization： Scalable Online Collaborative Filtering[C].In： Proceedings of the 16th International World Wide Web Conference. New York： ACMPress， 2007， 272-280.
[5] Linden G， Smith B， York J. Amazon.com Recommendation： Item-to-Item Collaborative Filtering[J]. IEEE Internet Computing， 2003， 7（1）：76-80.
[6] 樊夢佳，鈕艷，杜翠蘭，等.一種基于聚集系數的社區發現算法[J].計算機工程與科學，2016，38（2）：363-369.
[7] 過云燕，王宏志，張瑋奇.社交網絡中基于分類屬性的好友推薦[J].計算機工程與應用，2015，51（12）：99-106.
[8] 施少懷.一種基于用戶傾向的微博好友推薦算法[D].哈爾濱：哈爾濱工業大學，2013.
[9] Liben-Nowell D， Kleinberg J. The Link-Prediction Problem for Social Networks [M]. John Wiley & Sons， Inc. 2007， 58， 1019-1031.
[10] 俞琰，邱廣華，陳愛萍.基于混合圖的在線社交網絡朋友推薦算法[J].現代圖書情報技術，2011，（11）：54-59.
[11] Tong Hanghang， Faloutsos Christos， Pan Jiayu. Fast Random Walk with Restart and Its Applications[C]. In： Proceedings of the 6th International Conference on Data Mining （ICDM06）. 2006， Washington， DC. USA： IEEE Computer Society， 2006： 613-622.
[12] 呂潤桃，趙金考，李鈺，等.異質社交網絡中多通道特征融合的好友推薦模型[J].激光雜志，2014，35（12）：107-111.
[13] 張瑜，蔡國永.基于局部思想的在線社區劃分算法[J].微型機與應用，2013，32（13）：76-79.
[14] 解，汪小帆.復雜網絡的一種快速局部社團劃分算法[J].計算機仿真，2007，24（11）：82-85.
[15] 朱亞麗.“六度分離”假說的信息學意義[J].圖書情報工作，2005，49（6）：59-61.
[16] 劉宏杰，陸浩，張楠，等.基于微博的六度空間理論研究[J].計算機應用研究，2012，29（8）：2826-2829.
[17] 王玙，高琳.基于社交圈的在線社交網絡朋友推薦算法[J].計算機學報，2014，37（4）：801-808.
[18] 賀超波，湯庸，陳國華，等.面向大規模社交網絡的潛在好友推薦方法[J].合肥工業大學學報，2013，36（4）：420-424.
[19] 符饒.基于位置服務的潛在好友推薦方法[J].軟件，2015，36（1）：62-66.
[20] 許為，林柏鋼，林思娟，等.一種基于用戶交互行為和相似度的社交網絡社區發現方法研究[J].信息網絡安全，2015，（7）：77-83.
