社會網(wǎng)絡(luò)社區(qū)識別方法研究

楊高明，李敬兆，張順香，周華平

(安徽理工大學 計算機科學與工程學院, 安徽 淮南 232001)

0 引言

目前存在著各種各樣的網(wǎng)絡(luò)，諸如：社會網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)、WWW、Internet、WSN、經(jīng)濟網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電力網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)看起來雖然千差萬別，但實際上有著許多相似的性質(zhì)，如聚類效應(yīng)、小世界效應(yīng)、以及結(jié)點度分布為冪律分布和某些結(jié)點間的異配性等。由于聚類效應(yīng)的存在，社會網(wǎng)絡(luò)中往往存在著一些聯(lián)系緊密的結(jié)點構(gòu)成的簇，所謂的社區(qū)識別指的是將這樣的簇找出來以供進一步的分析和研究。無論是在社會網(wǎng)絡(luò)還是其他類型的復(fù)雜網(wǎng)絡(luò)的實際應(yīng)用中，社區(qū)識別都是不可或缺的一個重要步驟。例如，針對犯罪和恐怖主義活動，美國執(zhí)法機構(gòu)利用相關(guān)部門提供的數(shù)據(jù)構(gòu)建了龐大的信息網(wǎng)絡(luò)，而且開發(fā)了對該網(wǎng)絡(luò)進行知識發(fā)現(xiàn)和分析的工具CrimeNet Explorer[1]。為預(yù)測和找到各犯罪團伙和恐怖組織的首要和骨干分子，CrimeNet Explorer首先就要對當前信息網(wǎng)絡(luò)進行社區(qū)識別以區(qū)分不同的犯罪團伙和恐怖組織，然后才能運用社會網(wǎng)絡(luò)分析(Social Network Analysis，SNA)等方法和技術(shù)在所得到的各個社區(qū)中進行分析和確認[2]。社區(qū)識別方法的研究已越來越受到學術(shù)界的重視，但仍然存在一些缺陷和不足，主要表現(xiàn)為：針對的網(wǎng)絡(luò)一般為同質(zhì)網(wǎng)絡(luò)，識別算法不是增量算法，需要先驗或?qū)＜抑R，沉淀在網(wǎng)絡(luò)中的知識未能得到合理地利用，針對的網(wǎng)絡(luò)往往是單關(guān)系網(wǎng)絡(luò)，識別結(jié)果難以理解等。這些問題都需要學者進一步的研究。

1 社會網(wǎng)絡(luò)概述

社會網(wǎng)絡(luò)就是社會行動者之間連接而成的關(guān)系結(jié)構(gòu)。人、班級、學校、公司、國家等都可認為是社會行動者，這些社會行動者之間可以存在各種各樣的關(guān)系。社會網(wǎng)絡(luò)分析(SNA)是由研究者利用實證數(shù)據(jù)構(gòu)造的互動結(jié)構(gòu)圖，用以分析網(wǎng)絡(luò)參與者之間的關(guān)系形態(tài)的技術(shù)。SNA的發(fā)展在西方已有了七八十年的歷史，人類學、心理學、社會學、圖論、概率論和統(tǒng)計學等多種學科和學派為其注入了強大的活力。但其作為一個明確的專門領(lǐng)域或研究方法的形成以及得到廣泛的應(yīng)用和發(fā)展，只是近一二十年的事情。利用SNA方法及其理論提供的一些科學概念和量度，如密度、點度中心性、絕對點度中心度、中間中心性、絕對中間中心度、相對中間中心度、接近中心度、絕對接近中心度等，能夠?qū)Ω鞣N社會關(guān)系進行精確的量化表征和分析，從而揭示其結(jié)構(gòu)，并對其產(chǎn)生的各種現(xiàn)象進行更加深刻而具體的解釋。由于許多現(xiàn)象都可以用社會網(wǎng)絡(luò)加以描述，所以SNA已經(jīng)成為當前學術(shù)界一個非?；钴S的研究課題。

國外對SNA的研究和應(yīng)用已涵蓋了諸多方面和領(lǐng)域，如犯罪網(wǎng)絡(luò)、反恐網(wǎng)絡(luò)、電子商務(wù)、疫情監(jiān)測、作者合作網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)、基因常規(guī)網(wǎng)絡(luò)、郵件網(wǎng)絡(luò)、虛擬學習、作者—主題分析、社區(qū)發(fā)現(xiàn)、空間文本挖掘、標簽系統(tǒng)、虛擬社區(qū)、口語處理、角色識別、博客世界、青少年關(guān)系網(wǎng)絡(luò)、社會層次發(fā)現(xiàn)、電話通訊網(wǎng)絡(luò)、推薦系統(tǒng)、大型程序中Bug的預(yù)測和發(fā)現(xiàn)等。以上的這些列舉，只是國外開展SNA研究的冰山一角，這些研究的總體脈絡(luò)是：理論，實踐，再理論，再實踐，已形成了一個持續(xù)發(fā)展的良性循環(huán)。

相比較而言，國內(nèi)對SNA的研究起步較晚。在改革開放之后，我國的SNA研究只限于社會科學領(lǐng)域，其與計算機技術(shù)相結(jié)合也只是近幾年的事。國內(nèi)對SNA的研究相對滯后，從深度和廣度兩方面都與國外的研究水平有著很大的差距，而且大部分研究論文皆屬于社會科學和經(jīng)濟管理領(lǐng)域，與計算機科學直接相關(guān)的不足10%，而且大多還停留在初步的理論探討或簡單應(yīng)用，要想形成良性循環(huán)任重而道遠。客觀上，伴隨著中華民族的復(fù)興，作為一個新近崛起的經(jīng)濟大國，中國不僅需要社會科學和經(jīng)濟管理領(lǐng)域領(lǐng)域SNA的研究，也需要與信息時代的計算機技術(shù)相結(jié)合的SNA的研究，以便能夠大幅提高工作效率。開展SNA的研究有利于國家許多方面的發(fā)展，例如：利用SNA研究反恐網(wǎng)絡(luò)，有利于國家安全，美國學者的模擬實驗已經(jīng)證明，如果預(yù)先利用基于SNA的反恐網(wǎng)絡(luò)進行先行處理，則“9.11”事件完全可以被提前終止，新疆“7.5”事件的發(fā)生更能說明我國展開這方面研究的迫切性和重要性；利用SNA研究疫情監(jiān)控，可以保證國家衛(wèi)生安全，能夠快速找出疫情傳播的薄弱環(huán)節(jié)，用最短的時間取得最大的收益。

目前尚無統(tǒng)一和通用的SNA方法應(yīng)用框架，但美國的CrimeNet Explorer項目中針對犯罪網(wǎng)絡(luò)提出的框架具有通用的潛質(zhì)。該框架包括四個主要階段：網(wǎng)絡(luò)建立，網(wǎng)絡(luò)劃分，結(jié)構(gòu)分析和網(wǎng)絡(luò)可視化。這個框架完全勾勒出應(yīng)用SNA方法的整體輪廓，其中，網(wǎng)絡(luò)劃分是一個NP-hard問題，而且網(wǎng)絡(luò)劃分階段起到承上啟下的作用，所以在整個過程中該階段占有極其重要的地位。對于社會網(wǎng)絡(luò)劃分研究，國內(nèi)尚處于起步階段，國外則剛從同質(zhì)劃分階段過渡到異質(zhì)劃分階段。

網(wǎng)絡(luò)劃分也可以稱作網(wǎng)絡(luò)社區(qū)識別。但一般來說，網(wǎng)絡(luò)社區(qū)識別具較之前者具有更豐富的內(nèi)涵。從目前的文獻來看，對于網(wǎng)絡(luò)社區(qū)識別這一概念主要有兩種理解：一是指利用某種方法將網(wǎng)絡(luò)劃分成內(nèi)部聯(lián)系緊密而相互之間聯(lián)系稀疏的簇，二是指按照某種要求以人機交互的方式將滿足要求的社區(qū)找出來。網(wǎng)絡(luò)劃分的內(nèi)涵只局限于社會網(wǎng)絡(luò)社區(qū)識別的第一種理解 中。為使術(shù)語具有更強的概括性，本研究中盡量使用社會網(wǎng)絡(luò)社區(qū)識別這一術(shù)語。但在個別情況下，如在介紹基于譜聚類的社區(qū)識別方法時，社會網(wǎng)絡(luò)劃分顯得更自然、更直觀，所以在有些地方還會使用網(wǎng)絡(luò)劃分一詞。

很多情況下，社會網(wǎng)絡(luò)社區(qū)識別都是在考慮社會行動者之間存在各種關(guān)系的情況下，通過對社會行動者進行聚類實現(xiàn)的。大多數(shù)的傳統(tǒng)聚類方法把研究對象假設(shè)為具有相同數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)對象，即每種數(shù)據(jù)對象都可以用特定長度的特征向量來描述。但是現(xiàn)實世界中的數(shù)據(jù)對象的數(shù)據(jù)結(jié)構(gòu)是復(fù)雜多變且不統(tǒng)一的，往往包含多種類型的數(shù)據(jù)對象并且彼此相互關(guān)聯(lián)。傳統(tǒng)聚類算法在應(yīng)對異質(zhì)、多關(guān)系的社會網(wǎng)絡(luò)時，常常會遇到許多不可逾越的障礙。

2 社會網(wǎng)絡(luò)分析的研究

近些年來，國外的學者從理論和實踐兩個方面對SNA進行了廣泛而深入的研究和探討。為了進行犯罪調(diào)查和防止犯罪，幫助法律執(zhí)行部門和情報機構(gòu)高效地從犯罪網(wǎng)絡(luò)中進行知識發(fā)現(xiàn)，美國耗費三年時間開發(fā)了基于SNA的CrimeNet Explorer，模擬實驗證明該軟件十分有效。“9·11”之后，反恐網(wǎng)絡(luò)中的知識發(fā)現(xiàn)也一直是外國學者的研究目標，文獻中不但對一些恐怖襲擊事件運用SNA進行了分析，還證明了如果能夠在事件發(fā)生之前就應(yīng)用SNA對網(wǎng)絡(luò)進行分析，完全可能阻止事件的發(fā)生，并將所有罪犯繩之以法；另外，該文獻還特別關(guān)注了網(wǎng)絡(luò)的可視化問題。隱私保護是近年來的一個研究熱點，Elena Zheleva等人對SNA中的隱私保護問題[3]進行深入的研究，給出了攻擊模型。研究作者合作網(wǎng)絡(luò)也是一個重要的課題，Ulrik Brandes等人利用SNA對維基百科的合作結(jié)構(gòu)[4]進行探討，提出了描述和分析作者合作結(jié)構(gòu)的模型和算法。BlockModel一直是SNA研究領(lǐng)域一個重要的模型，Edoardo M. Airoldi等人提出混合成員隨機塊模型[5]，新模型較舊模型有了較大的改進，可應(yīng)用于蛋白質(zhì)相互作用網(wǎng)絡(luò)、基因常規(guī)網(wǎng)絡(luò)、郵件網(wǎng)絡(luò)等。

目前在Internet 上存在許多社會網(wǎng)絡(luò)網(wǎng)站，這些網(wǎng)站采集了注冊用戶的基本信息，并允許這些用戶介紹親朋加入，由此即構(gòu)成了社會網(wǎng)絡(luò)，在此基礎(chǔ)上還可進一步與享有共同愛好的其他人發(fā)展新的友誼關(guān)系，Peter Mika研究了社會網(wǎng)絡(luò)與語義網(wǎng)絡(luò)的關(guān)系，指出了社會網(wǎng)絡(luò)網(wǎng)站存在的缺陷以及應(yīng)對的策略。網(wǎng)絡(luò)的可視化是SNA研究領(lǐng)域的一個重要方面，網(wǎng)絡(luò)的可視化目的在于使隱藏的網(wǎng)絡(luò)結(jié)構(gòu)和個體角色等能更清晰、更易于理解的方式展現(xiàn)出來，F(xiàn)abricio Benevenuto 等人提出一個用于網(wǎng)絡(luò)可視化的統(tǒng)計模型，并且深入研究了基于視頻構(gòu)建的社區(qū)興趣發(fā)現(xiàn)，并在發(fā)現(xiàn)投機行為模式的基礎(chǔ)上討論了投機行為對用戶間相互信任的損害[6]。博客，以及當下流行的微博，可以幫助人們表達思想、發(fā)表觀點、分享經(jīng)驗和理念。博客和微博的開放標準以及發(fā)表信息的低門檻，使網(wǎng)絡(luò)社區(qū)中蘊含了大量的知識。尋找合適的工具從博客網(wǎng)絡(luò)社區(qū)中發(fā)現(xiàn)知識，是一個熱點問題。社會網(wǎng)絡(luò)社區(qū)挖掘是SNA的一個重要研究方向，Deng Cai等人給出異質(zhì)社會網(wǎng)絡(luò)隱藏社區(qū)挖掘的新方法[7]，實驗證明該方法非常有效，遠遠優(yōu)于傳統(tǒng)的挖掘方法。合作關(guān)系網(wǎng)絡(luò)屬于大型社會網(wǎng)絡(luò)之一，網(wǎng)絡(luò)的進化演變是SNA的重要研究任務(wù)。

國內(nèi)對SNA的研究相對滯后，但在某些領(lǐng)域也取得了一些可喜成果。例如，人名檢索結(jié)果重名消解問題的研究。眾所周知，人物重名現(xiàn)象十分普遍。搜索引擎的人名檢索結(jié)果通常是多個同名人物相關(guān)網(wǎng)頁的混合，郎君等人依據(jù)同名的不同人物具有不同的社會網(wǎng)絡(luò)的思想，利用檢索結(jié)果中共現(xiàn)的人名發(fā)現(xiàn)并拓展檢索人物相關(guān)的潛在社會網(wǎng)絡(luò)，結(jié)合圖的譜分割算法和模塊度指標進行社會網(wǎng)絡(luò)的自動聚類，在此基礎(chǔ)上實現(xiàn)人名檢索結(jié)果的重名消解。在人工標注的中文人名語料上進行實驗，整體性能達到較好水平[8]。再如，基于社會網(wǎng)絡(luò)可視化分析的數(shù)據(jù)挖掘研究，楊育彬等人結(jié)合社會網(wǎng)絡(luò)可視化分析和數(shù)據(jù)挖掘的理論與方法，引入相關(guān)的地理信息，對1980—2002年間世界范圍內(nèi)1417例恐怖襲擊事件的數(shù)據(jù)庫進行數(shù)據(jù)分析，以這些恐怖襲擊事件各要素結(jié)點之間關(guān)系作為基本分析單位，對恐怖組織之間活動模式和發(fā)展特點等內(nèi)在規(guī)律進行挖掘與解釋，得出一些有意義的結(jié)果。提出的方法可以有效地推廣應(yīng)用于蛋白質(zhì)結(jié)構(gòu)分析、生物基因分析以及各類社會問題的分析過程[9]。

3 社會網(wǎng)絡(luò)社區(qū)識別的研究

針對社會會網(wǎng)絡(luò)社區(qū)識別的研究，國外起步較早且發(fā)展比較成熟，先后有 Kernighan-Lin算法、GN算法及其改進算法、主題模型PLSA、作者-主題模型、譜聚類、基于密度的方法、SimRank算法、RankClus算法、NetClus算法等研究成果。Kernighan-Lin算法基于貪婪算法將網(wǎng)絡(luò)識別為兩個大小已知的社區(qū)[10]，其最主要的缺陷是如果不能正確指定社區(qū)的大小則會造成結(jié)點的錯分。GN算法則是從網(wǎng)絡(luò)中依次移除邊界數(shù)最大的邊以實現(xiàn)社區(qū)識別，但該算法時間復(fù)雜度過高[11]，社區(qū)劃分質(zhì)量較差。針對GN算法的缺陷，陸續(xù)有一些基于模塊度的改進算法被提出[12]，但由于模塊度定義的固有缺陷，這些改進算法傾向于將網(wǎng)絡(luò)識別成由規(guī)模相似的社區(qū)構(gòu)成。主題模型PLSA單純地利用文本信息對網(wǎng)絡(luò)進行識別，并未考慮對象之間的鏈接信息。作者-主題模型[13]對PLSA進行了進一步的發(fā)展，不但利用了純文本信息，還通過利用復(fù)雜產(chǎn)生模型加入了對象類型信息。對文本信息和圖約束的目標函數(shù)進行優(yōu)化組合[14]，也是一種較好的識別方法。以上這幾種識別方法都把文本信息作為重要的識別依據(jù)，應(yīng)用范圍較小，而且只能應(yīng)用在同質(zhì)網(wǎng)絡(luò)上。

在國內(nèi)，社會網(wǎng)絡(luò)社區(qū)識別的研究總體上還只局限于基于國外經(jīng)典算法的改進以對同質(zhì)網(wǎng)絡(luò)進行研究；就目前掌握的資料看，尚未發(fā)現(xiàn)異質(zhì)網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)研究。最值得注意的研究工作是淦文燕等的基于拓撲勢的社區(qū)發(fā)現(xiàn)研究[15]，該研究提出的識別方法具有較高的準確率，但該研究也是基于同質(zhì)網(wǎng)絡(luò)的。

4 結(jié)語

隨著信息技術(shù)的發(fā)展和普及，傳統(tǒng)的社會成員之間因互動而形成的社會關(guān)系已經(jīng)延伸到虛擬網(wǎng)絡(luò)環(huán)境中。社會網(wǎng)絡(luò)不僅為人們提供了交友娛樂的平臺，而且逐漸成為輔助行政、商務(wù)等活動的有力工具，成為一種新型的協(xié)同工作方式。同時，為了完善和改進社會網(wǎng)絡(luò)的溝通和交互機制，各種協(xié)同技術(shù)也應(yīng)用到社會網(wǎng)絡(luò)中。本文針對以上情況對社會網(wǎng)絡(luò)分析和社區(qū)結(jié)構(gòu)識別這兩項重要的研究內(nèi)容進行了總結(jié)，以起到拋磚引玉的作用。

[參考文獻]

[1] Jennifer Xu, Hsinchun Chen. CrimeNet Explorer: A Framework for criminal network knowledge discovery[J]. ACM Transactions on Infromation Systems, 2005, 23(2): 201-226.

[2] Jennifer Xu, Hsinchun Chen. Criminal Network Analysis and Visualization[J]. Communications of the ACM, 2005, 48(6): 100-107.

[3] Elena Zheleva, Lise Getoor. To Join or Not to Join: The Illusion of privacy in social networks with mixed public and private user profiles[C]// IW3C2, 2009: 531-540.

[4] Ulrik Brandes, Patrick Kenis, Jürgen Lerner, et al. Network analysis of collaboration structure in Wikipedia [C]// Proceedings of the 18th International Conference on World Wide Web, 2009: 731-740.

[5] Edoardo M. Airoldi, David M. Blei, et al. Mixed membership stochastic block models[J]. Journal of Machine Learning Research, 2008: 1981-2014.

[6] Fabricio Benevenuto, Tiago Rodrigues, Virgilio Almeida, et al. Video interactions in online video social networks[J]. Transactions on Multimedia Computing, Communications, and Applications, 2009, 5(4): 1-30.

[7] Deng Cai, Zheng Shao, Xiaofei He. Mining hidden community in heterogeneous social networks[C] // Proceedings of the 3rd international workshop on Link discovery, 2005: 58-65.

[8] 郎君, 秦兵, 宋巍，等. 基于社會網(wǎng)絡(luò)的人名檢索結(jié)果重名消解[J]. 計算機學報, 2009, 32(7): 1355-1374.

[9] Yang Yu-bin, Li Ning, Zhang Yao. Networked data mining based on social network visualizations[J]. Journal of Software, 2008, 19(8): 1980-1994.

[10] Kernighan B W, Lin S. A efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49: 291-307.

[11] Girvan M, Newman M E J. Community structure in social and biological networks[C] // Proc. Natl. Acad. Sci., 2001,99:7821-7826.

[12] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Phys. Rev. E., 2004,69: 1-16.

[13] M. Steyvers, P. Smyth, M. Rosen-Zvi, et. al. Probabilistic author-topic models for information discovery[C] // In KDD’04, 2004: 306-315.

[14] Q. Mei, D. Zhang, C. Zhai. A general optimization framework for smoothing language models on graph structures[C]// In SIGIR’08, 2008: 611-618.

[15] 淦文燕, 赫南, 李德毅，等. 一種基于拓撲勢的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J]. 軟件學報, 2009, 20(8): 2241-2254.