基于多維混合圖和核心節(jié)點(diǎn)的社團(tuán)發(fā)現(xiàn)算法

祝周　石琳　孔祥順

摘? ?要：社區(qū)發(fā)現(xiàn)和好友推薦算法一直是復(fù)雜網(wǎng)絡(luò)的研究熱點(diǎn)之一，在公安業(yè)務(wù)工作、網(wǎng)絡(luò)輿情控制、電子商務(wù)等領(lǐng)域具有重要的意義。為解決公安工作中防范恐怖主義事件、打擊易復(fù)發(fā)類犯罪、穩(wěn)控重點(diǎn)群體等突出難題，論文提出了一種基于核心種子節(jié)點(diǎn)擴(kuò)展的啟發(fā)式社團(tuán)發(fā)現(xiàn)算法。該算法通過(guò)有效融合多維信息形成混合圖，以種子節(jié)點(diǎn)作為初始社區(qū)，綜合考慮人物節(jié)點(diǎn)間不同交互行為和關(guān)聯(lián)行為的權(quán)重，依托實(shí)戰(zhàn)重點(diǎn)將協(xié)同過(guò)濾、Tanimoto系數(shù)、六度空間理論等算法相結(jié)合，最后把社區(qū)鄰接節(jié)點(diǎn)中的活躍節(jié)點(diǎn)降序排列作為重點(diǎn)社團(tuán)目標(biāo)，得到了一種有核心節(jié)點(diǎn)的基于“人、事、地、網(wǎng)、組織”五維混合圖的社團(tuán)發(fā)現(xiàn)數(shù)據(jù)模型，為警務(wù)大數(shù)據(jù)及其他應(yīng)用提供支撐。

關(guān)鍵詞：混合圖;核心節(jié)點(diǎn);鏈接度;社團(tuán)發(fā)現(xiàn)

中圖分類號(hào)：TP391? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：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 引言

近年來(lái)，以手機(jī)[1]、微信、微博等社交網(wǎng)絡(luò)（Social Network）為代表的社會(huì)媒體逐漸成為人們?nèi)粘Ｉ钪兄匾慕涣髌脚_(tái)，呈現(xiàn)出獨(dú)特的網(wǎng)絡(luò)特征[2]，現(xiàn)實(shí)與網(wǎng)絡(luò)已難以分割。由于社交網(wǎng)絡(luò)平臺(tái)的多樣性、隱匿性和開(kāi)放性等原因，導(dǎo)致公安機(jī)關(guān)在解決防范恐怖主義事件、打擊易復(fù)發(fā)類犯罪、穩(wěn)控重點(diǎn)群體等突出問(wèn)題時(shí)難上加難。如何充分利用互聯(lián)網(wǎng)社交網(wǎng)絡(luò)關(guān)系數(shù)據(jù)，虛實(shí)結(jié)合、挖掘目標(biāo)、發(fā)現(xiàn)社團(tuán)、獲取情報(bào)、查找重心，已成為當(dāng)前基層公安工作的一項(xiàng)非常重要的業(yè)務(wù)需求[3]。通過(guò)研究社團(tuán)中已知人員目標(biāo)，分析其多種社交網(wǎng)絡(luò)工具產(chǎn)生的虛實(shí)數(shù)據(jù)，引入多維關(guān)系云圖、核心節(jié)點(diǎn)、鏈接度等概念，重點(diǎn)將協(xié)同過(guò)濾[4，5]、Tanimoto系數(shù)等好友推薦及社團(tuán)發(fā)現(xiàn)算法相結(jié)合，以期得到一種有核心節(jié)點(diǎn)的基于“人、事、地、網(wǎng)、組織”五維混合圖的社團(tuán)發(fā)現(xiàn)數(shù)據(jù)模型。

2? 相關(guān)研究

在基層警務(wù)工作中，通過(guò)已知目標(biāo)挖掘其重要關(guān)系人[6]，要面對(duì)多種社交網(wǎng)絡(luò)工具產(chǎn)生的具有稀疏性和多樣性的數(shù)據(jù)信息，分析過(guò)程極其復(fù)雜，受工作意識(shí)、技戰(zhàn)術(shù)水平等制約，個(gè)人需求難以得到滿足，因此如何利用多種社交網(wǎng)絡(luò)信息快速發(fā)現(xiàn)潛在的工作目標(biāo)成為巨大挑戰(zhàn)。在傳統(tǒng)的根據(jù)社交網(wǎng)絡(luò)圖計(jì)算用戶相似度的方法中， 或直接計(jì)算目標(biāo)相似度而較少考慮好友的影響，或者將所有好友賦予相同權(quán)重， 即考慮了關(guān)系數(shù)量卻沒(méi)有區(qū)分重要性。

目前，流行的推薦方法基于一個(gè)假設(shè)：兩個(gè)用戶越相似，則他們?cè)接锌赡艹蔀榕笥选Ｓ腥N主要的方法刻畫(huà)用戶的相似度：基于用戶的屬性特征、基于網(wǎng)絡(luò)結(jié)構(gòu)的局部特性和基于網(wǎng)絡(luò)結(jié)構(gòu)的全局特性。

（1）基于用戶屬性特征的方法進(jìn)行朋友推薦[7]的思想是通過(guò)機(jī)器學(xué)習(xí)的手段，分析出不同類型的屬性對(duì)用戶的貢獻(xiàn)度不同，將其分類處理?；谠摲诸悾岢龅乃惴梢栽谡莆沼脩艋举Y料以及近期行為的基礎(chǔ)上，搜索出與之相關(guān)性更強(qiáng)的好友或能夠引發(fā)其興趣點(diǎn)的商品，用來(lái)快速、準(zhǔn)確、全面地得到用戶與其好友之間親疏程度排序及分類的結(jié)果，如果兩個(gè)用戶具有相同的年齡、性別、學(xué)?；蛘叩攸c(diǎn)等，則他們更加相似，也就更加可能成為朋友。

（2）基于網(wǎng)絡(luò)結(jié)構(gòu)的局部特征的方法利用用戶朋友網(wǎng)絡(luò)結(jié)構(gòu)的局部結(jié)構(gòu)信息。有很多局部相似性測(cè)量指標(biāo)[8]，如共同鄰居（Common Neighbor，CN）、Jaccard和Adamic/Adar等。CN也叫FOAF算法，被很多流行的OSNs所采用。它考慮兩個(gè)頂點(diǎn)的共同鄰居的數(shù)量，如果兩個(gè)用戶的共同朋友越多，則他們?cè)娇赡苄纬涉溄?。設(shè)N（x）表示頂點(diǎn)x的鄰居的集合，則頂點(diǎn)x與y的相似性為：。Jaccard方法不僅考慮了共同鄰居的數(shù)量，還考慮到兩個(gè)用戶擁有的鄰居數(shù)量，即 。Adamic/Adar也考慮兩頂點(diǎn)共同鄰居的度信息，并且認(rèn)為度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)，根據(jù)共同鄰居節(jié)點(diǎn)的度為每個(gè)頂點(diǎn)賦予一個(gè)權(quán)重值，該權(quán)重等于該頂點(diǎn)的度的對(duì)數(shù)的倒數(shù)，，一些研究表明，Adamic/Adar在局部特性指標(biāo)中具有最好的性能[9]。

（3）基于網(wǎng)絡(luò)全局特征方法偵測(cè)朋友社交網(wǎng)絡(luò)的所有路徑的結(jié)構(gòu)，其中Google網(wǎng)頁(yè)排序算法PageRank的拓展算法——重啟動(dòng)隨機(jī)游走算法（Random Walk with Restart，RWR）吸引了很多研究領(lǐng)域?qū)W者的興趣。RWR算法[10，11]是一個(gè)基于圖的隨機(jī)游走馬爾科夫鏈模型。相比于其他的相似性算法，RWR方法具有捕捉圖形全局結(jié)構(gòu)以及頂點(diǎn)之間多側(cè)面關(guān)系等優(yōu)點(diǎn)。

上述方法僅利用社交網(wǎng)絡(luò)中用戶朋友網(wǎng)絡(luò)信息，而在社交網(wǎng)絡(luò)數(shù)據(jù)中常常包含多種對(duì)象和網(wǎng)絡(luò)關(guān)系[12]。本文以推薦算法來(lái)挖掘重要關(guān)系人，擴(kuò)展了單項(xiàng)網(wǎng)絡(luò)關(guān)系，基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)[10]，融合了多種關(guān)系，引入鏈接度[13，14]來(lái)描述目標(biāo)的相似度，得到與核心節(jié)點(diǎn)的核心鏈接度來(lái)確定重點(diǎn)目標(biāo)。

3 基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法

3.1 基本思想

社交關(guān)系網(wǎng)絡(luò)是多維網(wǎng)絡(luò)，包含多種對(duì)象與網(wǎng)絡(luò)關(guān)系，對(duì)象之間的網(wǎng)絡(luò)關(guān)系受多種因素的影響。本文將對(duì)象之間多種關(guān)聯(lián)行為劃分為交互類和關(guān)聯(lián)類，構(gòu)建各類型的單一關(guān)系網(wǎng)絡(luò)，以關(guān)系人物為節(jié)點(diǎn)將多個(gè)子網(wǎng)復(fù)合成復(fù)雜的關(guān)系網(wǎng)絡(luò)云圖，借用了社團(tuán)發(fā)現(xiàn)的局部節(jié)點(diǎn)模型[13]、好友推薦的共同鄰居模型、文本分類的向量空間模型等數(shù)據(jù)模型，定義了關(guān)系云圖、核心節(jié)點(diǎn)、鏈接度等概念[13，14]，結(jié)合實(shí)戰(zhàn)對(duì)不同的邊設(shè)置了不同權(quán)重，再使用協(xié)同過(guò)濾、Tanimoto系數(shù)、六度空間[15，16]等理論算法計(jì)算鏈接度，最后分析與核心種子節(jié)點(diǎn)社區(qū)相鄰接的活躍節(jié)點(diǎn)鏈接度數(shù)值關(guān)系，鎖定重點(diǎn)目標(biāo)或劃出社團(tuán)。

3.2 多子網(wǎng)關(guān)系云圖構(gòu)建

基于社交網(wǎng)絡(luò)全局特征來(lái)表達(dá)網(wǎng)絡(luò)中所有可能的結(jié)構(gòu)，定義一個(gè)以關(guān)系人物為節(jié)點(diǎn)的多子網(wǎng)關(guān)系云圖[10]，融合多種對(duì)象和多種關(guān)系，使結(jié)果能夠真實(shí)反映對(duì)象間的交互度和相似度，具體分為六個(gè)步驟。

（1）構(gòu)建核心節(jié)點(diǎn)的社交網(wǎng)絡(luò)數(shù)據(jù)倉(cāng)庫(kù)。從互聯(lián)網(wǎng)多渠道抽取社交網(wǎng)絡(luò)工具數(shù)據(jù)信息、從電信運(yùn)營(yíng)商若干電信通訊基站抽取通訊記錄數(shù)據(jù)信息[1]、從公安管理以及其他方法獲取的虛實(shí)數(shù)據(jù)信息，清洗后作為數(shù)據(jù)源。

（2）利用數(shù)據(jù)源中人物與人物之間的關(guān)聯(lián)，組織與人物之間的關(guān)聯(lián)，位置與人物之間的關(guān)聯(lián)，考慮整個(gè)網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的聯(lián)系，組建關(guān)系云圖G，以G=（V，A，E）表示。

（3）V表示節(jié)點(diǎn)集合，包含四種類型節(jié)點(diǎn)Vu、Vc、Vp、Vt。其中，Vu為人物節(jié)點(diǎn)集合，Vc為人物參加的組織節(jié)點(diǎn)集合，Vp為位置節(jié)點(diǎn)集合，Vt為各類型頂點(diǎn)集合，即V=Vu∪Vc∪Vp∪Vt。因數(shù)據(jù)來(lái)源不一，人物使用的各類社交網(wǎng)絡(luò)工具不具有唯一性，人物節(jié)點(diǎn)的各屬性并非齊備完整，人物節(jié)點(diǎn)的唯一標(biāo)識(shí)使用獨(dú)立的唯一標(biāo)識(shí)，而不使用身份證、社交網(wǎng)絡(luò)工具ID等屬性類標(biāo)識(shí)。

（4）A是人物節(jié)點(diǎn)的屬性集合，其中，A_Vi為人物節(jié)點(diǎn)V_i所擁有的屬性集合?，F(xiàn)主要包含六種類型頂點(diǎn)A_c、A_t、A_sn、A_id、A_xm、A_sfz。其中，A_c為組織屬性，A_t為手機(jī)號(hào)碼屬性，A_sn為社交網(wǎng)絡(luò)工具屬性，A_id為人物唯一標(biāo)識(shí)屬性，Axm為姓名屬性，A_sfz為身份證號(hào)碼屬性。各人物節(jié)點(diǎn)的社交工具種類及號(hào)碼、手機(jī)號(hào)碼等可能有多個(gè)，因而其屬性記錄的數(shù)據(jù)也并非唯一值，假設(shè)人物節(jié)點(diǎn)Vi有Numx種社交工具及相應(yīng)號(hào)碼，有Numy個(gè)手機(jī)號(hào)碼，參加了Numz個(gè)組織或圈子，則A_vi={A_id∪A_sfz∪A_xm∪A_cz∪A_snx∪A_ty，Num_x?|A_sn|，Num_y?|A_t|，Num_z?|Ac | }。

（5）E是邊的集合，主要邊的類型有Esnj、Ecj、Etk、Ep。其中，Esnj為社交網(wǎng)絡(luò)工具好友關(guān)系集合，如果人物Vu1和Vu2之間存在好友（含關(guān)注）聯(lián)系，每增加一種社交網(wǎng)絡(luò)工具好友則相應(yīng)增加一條關(guān)系邊。Ecj為關(guān)系人組織群體關(guān)系集合，如果人物Vu1和Vu2之間存在相同的組織群體（含圈子、群組）聯(lián)系，每增加一個(gè)相同的組織群體，則相應(yīng)在兩個(gè)人物節(jié)點(diǎn)與組織節(jié)點(diǎn)之間分別增加一條關(guān)系邊。Etk為關(guān)系人手機(jī)通訊關(guān)系集合，如果節(jié)點(diǎn)Vu1和Vu2之間存在手機(jī)通訊聯(lián)系，每增加一種（非一次）手機(jī)通訊關(guān)系則相應(yīng)增加一條關(guān)系邊。Ep為關(guān)系人位置交互關(guān)系集合，如果人物節(jié)點(diǎn)Vu1和Vu2之間存在相同的位置聯(lián)系，每增加一個(gè)相同的位置則相應(yīng)分別增加一條關(guān)系邊，Ep包含現(xiàn)實(shí)位置關(guān)系與虛擬位置關(guān)系兩種情形。

（6）關(guān)系云圖中有的關(guān)系邊是有向的，有的是無(wú)向的，因此統(tǒng)一成一個(gè)有向圖，將無(wú)向邊表示為兩條有向弧，各關(guān)系邊都是帶有權(quán)值的。

3.3? 關(guān)聯(lián)類相似度加權(quán)網(wǎng)絡(luò)構(gòu)建

關(guān)系云圖的拓?fù)浣Y(jié)構(gòu)，僅表示個(gè)人在社會(huì)交往中的范圍，連接節(jié)點(diǎn)的邊越多表示這個(gè)人的交際范圍越廣，但是很難準(zhǔn)確分析與其關(guān)系最密切的人是誰(shuí)?，F(xiàn)實(shí)中各種社交網(wǎng)絡(luò)工具邊上的權(quán)重具有非常重要的意義，親密度不同的人物之間，所存在的社交網(wǎng)絡(luò)工具邊的數(shù)量及種類有很大區(qū)別，而邊權(quán)越大關(guān)系越密切。本文構(gòu)建了交互加權(quán)網(wǎng)絡(luò)作為基礎(chǔ)網(wǎng)絡(luò)，主要方法如下。

（1）歸一化處理每一條邊上的權(quán)值，使其取值范圍為（0，1）。

（2）結(jié)合工作實(shí)際，使用層次分析法創(chuàng)建各節(jié)點(diǎn)之間虛擬屬性邊的重要度矩陣，得出各虛擬邊弧的權(quán)值。

（3）主要計(jì)算各類社交網(wǎng)絡(luò)工具邊權(quán)、各類手機(jī)通訊邊權(quán)、各類組織圈子關(guān)系[17]邊權(quán)等關(guān)聯(lián)虛擬類邊權(quán)。

（4）Wij代表兩個(gè)人物節(jié)點(diǎn)Vi和Vj之間的各類虛擬邊（非位置類邊）的權(quán)重總值，即為兩個(gè)人物節(jié)點(diǎn)間各類虛擬非位置邊權(quán)的總和。

（5）位置類邊權(quán)值因作用特殊另行計(jì)算。

3.4? 交互類虛擬位置相似度計(jì)算

基于位置的社交網(wǎng)絡(luò)服務(wù)是利用GPS、蜂窩網(wǎng)、WLAN等技術(shù)獲得移動(dòng)終端的地理位置信息，支持用戶隨時(shí)隨地自由記錄并分享地理位置等信息。而位置維度的社團(tuán)發(fā)現(xiàn)，可根據(jù)社交網(wǎng)絡(luò)服務(wù)或其他方法獲取的地理位置信息，借用文本分類的向量空間模型[18]。即以位置向量來(lái)描述人物，將每個(gè)位置作為向量空間坐標(biāo)系的一維，人物被形式化為多維空間向量中的一個(gè)向量。在多維向量空間模型中，使用TF-IDF權(quán)重計(jì)算方法計(jì)算某一維向量值，而人物節(jié)點(diǎn)的位置相似度用Tanimoto系數(shù)進(jìn)行計(jì)算，主要方法如下。

（1）位置向量包含基站位置和IP地址兩類數(shù)據(jù)，即以基站和IP地址作為核心數(shù)據(jù)。

（2）標(biāo)準(zhǔn)化處理的傳統(tǒng)的TF，以nfiL表示人物i在位置L出現(xiàn)的頻數(shù)，以Pi表示人物i的位置集合，以表示人物i在所有位置中頻數(shù)的最大值，公式如下：

（3）修正并規(guī)范后的IDF，以表示人物i的位置集合中所有頻數(shù)的和，fiL表示人物i的位置L在人物i位置集合中的頻率，fjL表示人物j的位置L在人物j位置集合中的頻率，公式如下：

（4）為解決數(shù)據(jù)稀疏及單一性問(wèn)題，結(jié)合實(shí)戰(zhàn)以提升位置頻數(shù)對(duì)實(shí)際相似度的影響準(zhǔn)確率，本文對(duì)fiL=1時(shí)的頻數(shù)nfiL進(jìn)行歸一化處理以hiL表示，以WiL表示人物i向量在位置L維度上的向量值，也是人物節(jié)點(diǎn)i與位置節(jié)點(diǎn)L間邊的權(quán)重，公式如下：

（5）使用Tanimoto系數(shù)計(jì)算人物節(jié)點(diǎn)i和j的虛擬位置相似度Psim （Vi，Vj），公式如下：

3.5? 交互類現(xiàn)實(shí)位置相似度計(jì)算

如果關(guān)系云圖中人物節(jié)點(diǎn)之間存在公安工作或其他方式獲取的現(xiàn)實(shí)位置數(shù)據(jù)邊Ep，要單獨(dú)計(jì)算其現(xiàn)實(shí)位置相似度。現(xiàn)實(shí)位置相似度[19]是反映兩個(gè)人物節(jié)點(diǎn)相似性最重要的指標(biāo)，因?yàn)槠浯砹藘蓚€(gè)人物曾在同一時(shí)間、同一地點(diǎn)發(fā)生過(guò)極為親密的行為。本文在此項(xiàng)計(jì)算中使用了指數(shù)函數(shù)，兩個(gè)人物如果僅有幾次交集，可能是偶然行為，但隨著近期內(nèi)現(xiàn)實(shí)交集行為的數(shù)量增多，就更有可能有著相似的工作生活圈，因此相似度應(yīng)該隨著交互行為數(shù)量的上升而上升，并且上升趨勢(shì)是先慢后快。人物i和j的現(xiàn)實(shí)位置交集頻數(shù)用Lij表示，將Lij+0.01作為分母視為收縮參數(shù)，對(duì)數(shù)據(jù)歸一化處理，利用指數(shù)函數(shù)算法，常數(shù)e約為2.71828，則人物節(jié)點(diǎn)i和j的現(xiàn)實(shí)位置相似度Lsim （Vi，Vj），公式如下：

3.6? 鏈接度的定義

在關(guān)系云圖中，綜合衡量拓?fù)浣Y(jié)構(gòu)和各節(jié)點(diǎn)之間邊權(quán)，本文定義了兩個(gè)人物節(jié)點(diǎn)Vi和Vj間的鏈接度Vsim （Vi，Vj），來(lái)描述各人物之間的相似度。由于社交網(wǎng)絡(luò)具有小世界特性[20]，大部分節(jié)點(diǎn)可以從其他任一節(jié)點(diǎn)經(jīng)少數(shù)幾步到達(dá)。即使兩個(gè)節(jié)點(diǎn)沒(méi)有直接相連或者沒(méi)有共同鄰居節(jié)點(diǎn)，他們之間仍然存在某種聯(lián)系，這種聯(lián)系通過(guò)節(jié)點(diǎn)之間最短路徑進(jìn)行傳遞。因此，對(duì)于直接相連的人物，他們的相似度與彼此之間路徑的權(quán)重以及與共同好友的權(quán)重相關(guān);對(duì)于不直接相連的人物，他們的相似度為他們之間的最短路徑上所有節(jié)點(diǎn)對(duì)的相似度的乘積，路徑越長(zhǎng)，相似度越低。當(dāng)存在多條最短路徑時(shí)，取乘積較大者作為他們的相似度。根據(jù)六度分隔理論[15，16]，世界上任意兩人之間所間隔的人數(shù)平均不超過(guò)六人。因此，當(dāng)兩個(gè)人物節(jié)點(diǎn)之間路徑長(zhǎng)度大于 6 時(shí)，則認(rèn)為他們的緊密程度近似為零。以Ni和Nj分別代表人物節(jié)點(diǎn)i和節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)集合，以pathij表示人物節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑。用戶節(jié)點(diǎn)之間的鏈接度Vsim （Vi，Vj）及用戶節(jié)點(diǎn)Vi與其他節(jié)點(diǎn)Vx（非人物節(jié)點(diǎn)）之間的權(quán)值Vsim （Vi，Vx）算法定義如下：

（1）Vi，Vj相鄰

（2）

（3）

（4）

3.7? 總鏈接度和核心鏈接度的定義

根據(jù)警務(wù)實(shí)戰(zhàn)，分別將人物節(jié)點(diǎn)i和j之間的位置等屬性邊權(quán)值與鏈接度賦予權(quán)重α進(jìn)行計(jì)算，得到人物節(jié)點(diǎn)i和j的總鏈接度Tsim （Vi，Vj）。以Vk表示核心節(jié)點(diǎn)集，為獲取以核心節(jié)點(diǎn)為中心的社團(tuán)，用核心鏈接度Csim （Vi）表示人物節(jié)點(diǎn)i到各不同權(quán)重β的核心節(jié)點(diǎn)的總鏈接度之和，如暫無(wú)經(jīng)驗(yàn)權(quán)重則默認(rèn)取1，可通過(guò)機(jī)器學(xué)習(xí)，逐步獲取各經(jīng)驗(yàn)權(quán)重，具體公式如下：

（1）

（2）

3.8? 算法設(shè)計(jì)

輸入：關(guān)系云圖G=（V=Vu∪Vc∪Vp∪Vt，A=Ac∪At∪Asn∪Aid∪Axm∪Asfz，E=Esnj∪Ecj∪Etk∪Ep），核心節(jié)點(diǎn)集Vk，各類案事件權(quán)重調(diào)節(jié)參數(shù)α和各核心節(jié)點(diǎn)的權(quán)重調(diào)節(jié)參數(shù)β。

輸出：按核心鏈接度降序排名各關(guān)系人物列表。

方法：

（1）輸入待分析的核心節(jié)點(diǎn)集Vk及其對(duì)應(yīng)的關(guān)系云圖G，并設(shè)定好相關(guān)權(quán)重參數(shù);

（2）迭代計(jì)算每一個(gè)節(jié)點(diǎn)的相關(guān)屬性的關(guān)聯(lián)度，以增減節(jié)點(diǎn);

（3）計(jì)算G中每一個(gè)人物節(jié)點(diǎn)的交互類虛擬位置相似度;

（4）計(jì)算G中每一個(gè)人物節(jié)點(diǎn)的交互類現(xiàn)實(shí)位置相似度;

（5）計(jì)算G中每一個(gè)人物節(jié)點(diǎn)的鏈接度;

（6）根據(jù)（3）（4）（5）的結(jié)果計(jì)算各人物節(jié)點(diǎn)的總鏈接度;

（7）根據(jù)（6）的總鏈接度計(jì)算各人物節(jié)點(diǎn)的核心鏈接度;

（8）將各節(jié)點(diǎn)的核心鏈接度降序排列，據(jù)此確定各人物節(jié)點(diǎn)與核心節(jié)點(diǎn)間的相互關(guān)系，劃分重點(diǎn)目標(biāo)與社團(tuán)。

3.9? 算法實(shí)驗(yàn)

本文對(duì)社交網(wǎng)絡(luò)工具數(shù)據(jù)、通訊記錄數(shù)據(jù)以及其他方法獲取的虛實(shí)數(shù)據(jù)信息進(jìn)行了模擬，建立實(shí)驗(yàn)數(shù)據(jù)集來(lái)測(cè)試算法的準(zhǔn)確性和可操作性。實(shí)驗(yàn)在Windows Server 2008 R2的環(huán)境下使用Python語(yǔ)言運(yùn)行。

（1）實(shí)驗(yàn)構(gòu)建了四次某犯罪團(tuán)伙三個(gè)已知目標(biāo)的社交網(wǎng)絡(luò)虛實(shí)數(shù)據(jù)倉(cāng)庫(kù)。

（2）利用層次分析法確定了社交網(wǎng)絡(luò)工具微信邊權(quán)Wsnwx=0.34，社交網(wǎng)絡(luò)工具微博邊權(quán)Wsnwb=0.16，手機(jī)通訊記錄邊權(quán)Wt1=0.34等。

（3）將數(shù)據(jù)倉(cāng)庫(kù)內(nèi)的數(shù)據(jù)輸入算法形成關(guān)系云圖，并將權(quán)重調(diào)節(jié)參數(shù)α1、α2、α3、β均賦值為1。

（4）利用本文中多維混合圖和核心節(jié)點(diǎn)的社團(tuán)發(fā)現(xiàn)算法對(duì)四次實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了分析挖掘，與人工分析出的犯罪組織重點(diǎn)人員為參照，均成功的按核心鏈接度的高低挖掘出犯罪團(tuán)伙中的重點(diǎn)人員，準(zhǔn)確程度在88%以上。

4? 總結(jié)與展望

本文算法的實(shí)現(xiàn)包括模型構(gòu)建和算法設(shè)計(jì)。在闡述各個(gè)模塊構(gòu)建過(guò)程中，詳細(xì)介紹了關(guān)系云圖的構(gòu)建和各類權(quán)重計(jì)算及設(shè)置方法，在云圖的構(gòu)建中為了充分反映人物多種社交網(wǎng)絡(luò)工具的關(guān)系特征，精準(zhǔn)預(yù)測(cè)其關(guān)聯(lián)性，綜合考慮了多種類虛實(shí)邊關(guān)系。在權(quán)重設(shè)置中，根據(jù)云圖中頂點(diǎn)的關(guān)聯(lián)度和交互度，借用好友推薦的共同鄰居模型、文本分類的向量空間模型等賦予人物社會(huì)化行為相應(yīng)的權(quán)重。最后利用核心鏈接度準(zhǔn)確計(jì)算關(guān)系云圖中各人物節(jié)點(diǎn)的與初始核心節(jié)點(diǎn)間的關(guān)聯(lián)相似度，得出最終人物推薦列表以鎖定團(tuán)伙目標(biāo)。

此模型研究是將多種傳統(tǒng)警務(wù)技戰(zhàn)法及大數(shù)據(jù)社會(huì)網(wǎng)絡(luò)分析研究領(lǐng)域進(jìn)行深度融合的一種嘗試，需要緊緊依托于公安大數(shù)據(jù)的發(fā)展，存在不足之處。首先，混合圖中的節(jié)點(diǎn)包括人物、位置、圈子等多種類型，算法的空間消耗很高。其次，本文提出的基于混合圖的各綜合算法仍賦予了鏈接度大的人物過(guò)大的挖掘推薦強(qiáng)度，對(duì)于某些鏈接度小但更為重點(diǎn)的特殊人物節(jié)點(diǎn)挖掘多樣性不高。在今后的研究中，應(yīng)當(dāng)從數(shù)據(jù)挖掘角度進(jìn)一步在發(fā)現(xiàn)社團(tuán)、研究社團(tuán)內(nèi)部交互模式以及預(yù)測(cè)社團(tuán)的模型上進(jìn)行深入廣泛的分析和探討，逐步探索擴(kuò)展六度空間理論的多層次關(guān)系，積累各類案事件不同的權(quán)值，特別要提高一些鏈接度小的特殊關(guān)鍵目標(biāo)人物推薦強(qiáng)度，提高算法的準(zhǔn)確性。

5? 結(jié)束語(yǔ)

針對(duì)目前社會(huì)網(wǎng)絡(luò)環(huán)境及各類個(gè)性化通訊服務(wù)現(xiàn)狀，結(jié)合警務(wù)工作實(shí)際，本文提出基于社交網(wǎng)絡(luò)及通訊痕跡中人物關(guān)聯(lián)關(guān)系視角下的分析模式，參考OSNs中主流的推薦算法，設(shè)計(jì)了一種基于復(fù)雜混合圖的社團(tuán)挖掘算法模型，將各種社交網(wǎng)絡(luò)及通訊痕跡中的人物關(guān)系網(wǎng)絡(luò)和位置等社會(huì)化交互行為融入模型，更有效地解決了公安工作中快速挖掘重點(diǎn)目標(biāo)和社團(tuán)問(wèn)題。

參考文獻(xiàn)

[1] 高建強(qiáng)，譚劍，崔永發(fā).一種基于通訊痕跡的社會(huì)網(wǎng)絡(luò)團(tuán)伙分析模型[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（3）：206-208.

[2] 劉小玲，譚宗穎.復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分算法的情報(bào)學(xué)應(yīng)用研究[J].圖書(shū)館學(xué)研究，2011，（8）：20-25.

[3] 楊莉莉，楊永川.基于社會(huì)網(wǎng)絡(luò)的犯罪組織關(guān)系挖掘[J].計(jì)算機(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] 樊夢(mèng)佳，鈕艷，杜翠蘭，等.一種基于聚集系數(shù)的社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)工程與科學(xué)，2016，38（2）：363-369.

[7] 過(guò)云燕，王宏志，張瑋奇.社交網(wǎng)絡(luò)中基于分類屬性的好友推薦[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（12）：99-106.

[8] 施少懷.一種基于用戶傾向的微博好友推薦算法[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

[9] Liben-Nowell D， Kleinberg J. The Link-Prediction Problem for Social Networks [M]. John Wiley & Sons， Inc. 2007， 58， 1019-1031.

[10] 俞琰，邱廣華，陳愛(ài)萍.基于混合圖的在線社交網(wǎng)絡(luò)朋友推薦算法[J].現(xiàn)代圖書(shū)情報(bào)技術(shù)，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] 呂潤(rùn)桃，趙金考，李鈺，等.異質(zhì)社交網(wǎng)絡(luò)中多通道特征融合的好友推薦模型[J].激光雜志，2014，35（12）：107-111.

[13] 張瑜，蔡國(guó)永.基于局部思想的在線社區(qū)劃分算法[J].微型機(jī)與應(yīng)用，2013，32（13）：76-79.

[14] 解，汪小帆.復(fù)雜網(wǎng)絡(luò)的一種快速局部社團(tuán)劃分算法[J].計(jì)算機(jī)仿真，2007，24（11）：82-85.

[15] 朱亞麗.“六度分離”假說(shuō)的信息學(xué)意義[J].圖書(shū)情報(bào)工作，2005，49（6）：59-61.

[16] 劉宏杰，陸浩，張楠，等.基于微博的六度空間理論研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（8）：2826-2829.

[17] 王玙，高琳.基于社交圈的在線社交網(wǎng)絡(luò)朋友推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（4）：801-808.

[18] 賀超波，湯庸，陳國(guó)華，等.面向大規(guī)模社交網(wǎng)絡(luò)的潛在好友推薦方法[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2013，36（4）：420-424.

[19] 符饒.基于位置服務(wù)的潛在好友推薦方法[J].軟件，2015，36（1）：62-66.

[20] 許為，林柏鋼，林思娟，等.一種基于用戶交互行為和相似度的社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究[J].信息網(wǎng)絡(luò)安全，2015，（7）：77-83.