在線社會網(wǎng)絡的結(jié)構化分析方法及應用研究.pdf

1、繼科學計算和生命計算之后，面向網(wǎng)絡化社會系統(tǒng)的社會計算已然成為學術界的研究熱點和前沿課題。社會網(wǎng)絡結(jié)構分析是社會計算的核心問題之一，深入理解社會網(wǎng)絡的結(jié)構特性有助于提高社會生產(chǎn)效率、緩解社會矛盾、提高社會收益、解決社會問題，因此具有廣闊的應用前景。現(xiàn)有的社會網(wǎng)絡結(jié)構分析方法大多面向靜態(tài)網(wǎng)絡，無法滿足在線社會網(wǎng)絡的演變要求。此外，網(wǎng)絡結(jié)構分析中固有存在的一些技術難點，如算法時間復雜度過高、需要先驗知識、結(jié)構形態(tài)受限、數(shù)據(jù)維度過高等，同樣限

2、制了該領域的發(fā)展。針對傳統(tǒng)社會網(wǎng)絡結(jié)構分析方法中存在的不足，本著對現(xiàn)有方法進行改進、完善和發(fā)展，本文一方面研究如何設計在線式社會網(wǎng)絡結(jié)構分析框架以滿足在線網(wǎng)絡的實時性要求，另一方面研究如何設計更具前瞻性的方法和理論以解決社會網(wǎng)絡模體識別中存在的技術難點，最后，利用網(wǎng)絡模體的結(jié)構特性，解決應用系統(tǒng)中存在的具體問題。歸納而言，本文的研究內(nèi)容主要包括以下4個方面：
　?。?）多關系社會網(wǎng)絡社區(qū)識別方法研究。相比于單質(zhì)網(wǎng)絡社區(qū)識別，多關系

3、社會網(wǎng)絡中的社區(qū)結(jié)構是隱含的、難以發(fā)現(xiàn)的?，F(xiàn)有方法大多從結(jié)構表達能力上看待異構社區(qū)結(jié)構，進而多采用全局優(yōu)化方法。這類方法在某些特定的網(wǎng)絡類型求解中可能具有一定的優(yōu)勢，但缺乏普適性。例如當異構網(wǎng)絡各層級內(nèi)部的社交關系差別很大時，全局優(yōu)化會使識別出的社區(qū)結(jié)果偏離真實社區(qū)，因此精度較低。此外這類方法忽略了各網(wǎng)絡層級之間的關聯(lián)性，因此社區(qū)內(nèi)部節(jié)點間的交互程度可能很低，從而失去現(xiàn)實意義。本文將異構社區(qū)識別任務視為社交個體的局部選擇過程，首先通過度

4、量異構網(wǎng)絡層間吸引力、同質(zhì)網(wǎng)絡節(jié)點游走可達概率，提出異構網(wǎng)絡隨機游走模型；然后對隨機游走路徑施以同社區(qū)互可達性約束，將各子網(wǎng)節(jié)點間的相似性度量，建模為隨機游走的可達性度量；最后，將相似性函數(shù)推廣到層次聚類，異構社區(qū)識別任務可以在較短的時間內(nèi)迭代完成。
　?。?）在線社會網(wǎng)絡社區(qū)識別方法研究。靜態(tài)網(wǎng)絡社區(qū)識別中普遍存在的社區(qū)重疊問題、參數(shù)依賴問題、社區(qū)形態(tài)約束問題在動態(tài)網(wǎng)絡環(huán)境下的解決難度更大。一方面，已經(jīng)被廣泛認可的靜態(tài)社區(qū)識別技

5、術或理論大多無法適用于動態(tài)網(wǎng)絡；另一方面，某些參量在網(wǎng)絡演變時可能對社區(qū)結(jié)構造成不可預料的改變，這給動態(tài)社區(qū)識別中的實時性、精準性要求帶來了嚴峻的考驗。為解決這些問題，我們提出社區(qū)穩(wěn)定性這一概念替代傳統(tǒng)的基于結(jié)構的社區(qū)定義。社區(qū)穩(wěn)定性基于節(jié)點間的同質(zhì)性吸引，因此穩(wěn)定狀態(tài)的社區(qū)結(jié)構應滿足社區(qū)內(nèi)部節(jié)點具有較強的互吸引力，而分處于不同社區(qū)的節(jié)點盡可能不具有任何吸引力。該方法避免了傳統(tǒng)社區(qū)識別中的結(jié)構約束，因此社區(qū)可以具有各種形狀；進一步講，社

6、區(qū)穩(wěn)定性的天然存在使得算法不必依賴于各種輸入?yún)?shù)；由于社區(qū)邊緣節(jié)點可能同時被不同的穩(wěn)定核心吸引，因此所識別出的社區(qū)結(jié)構具有重疊性。在動態(tài)社區(qū)識別方面，我們將在線社區(qū)識別問題轉(zhuǎn)化為社區(qū)穩(wěn)定性的校準問題，進而動態(tài)社區(qū)結(jié)構可通過對歷史社區(qū)校準而得。
　?。?）在線社會網(wǎng)絡結(jié)構壓縮方法研究。如果按數(shù)據(jù)存儲規(guī)模進行劃分，社會網(wǎng)絡壓縮研究可分為無損壓縮和有損壓縮兩種。本文關注于網(wǎng)絡結(jié)構的規(guī)?？s減，因此屬于有損壓縮的研究范疇。無損壓縮方法雖然能

7、夠避免壓縮損失，但存在壓縮率極限，無法滿足用戶的實際需求。而在有損壓縮中，時間開銷過高、結(jié)構表達能力較弱、對動態(tài)網(wǎng)絡匹配性較低是亟待解決的關鍵問題。本文提出一種基于結(jié)構相似性整合的兩階段動態(tài)網(wǎng)絡壓縮框架。在第一階段，通過證明將壓縮損失的差異性優(yōu)化，轉(zhuǎn)化為壓縮過程中節(jié)點合并的局部選擇優(yōu)化，從而證明了靜態(tài)網(wǎng)絡壓縮序列的線性時間復雜性；在第二階段，以穩(wěn)定壓縮損失為前提，校準前一時刻的壓縮表達以此避免算法的重復執(zhí)行，在滿足在線社會網(wǎng)絡演變要求的

8、同時提高了壓縮效率。
　　（4）在線社會網(wǎng)絡社區(qū)結(jié)構應用研究。在結(jié)構分析的應用層面，我們關注于移動互聯(lián)網(wǎng)中的蠕蟲遏制問題。現(xiàn)有的蠕蟲遏制方案大多面向單質(zhì)網(wǎng)絡，無法遏制蠕蟲的混合傳播。此外，網(wǎng)絡動態(tài)性帶來的結(jié)構改變加大了蠕蟲病毒的遏制難度。針對這些問題，我們提出一種基于社區(qū)的混合蠕蟲雙向反饋遏制系統(tǒng)。該系統(tǒng)借助了社區(qū)結(jié)構對蠕蟲病毒的捕獲能力。首先對社區(qū)邊緣節(jié)點施以門禁免疫策略將蠕蟲控制在社區(qū)內(nèi)部；然后，提出分布式蠕蟲標簽轉(zhuǎn)發(fā)策略，使