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

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

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

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

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

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

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

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

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