基于非負(fù)矩陣分解的社交網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法

徐晟+趙永剛

摘要：社交網(wǎng)絡(luò)用戶眾多，連接關(guān)系復(fù)雜，挖掘其中的社團(tuán)結(jié)構(gòu)對(duì)于研究網(wǎng)絡(luò)的結(jié)構(gòu)，分析用戶行為特點(diǎn)，揭示信息傳播規(guī)律都有重要的意義。本文針對(duì)有向加權(quán)和無(wú)向加權(quán)網(wǎng)絡(luò)特點(diǎn)，介紹了基于非負(fù)矩陣分解的社團(tuán)劃分算法。真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，算法是有效的，符合人們對(duì)網(wǎng)絡(luò)中人際關(guān)系的直觀理解，為研究社交網(wǎng)絡(luò)的結(jié)構(gòu)和關(guān)系演變提供了一種有效的方法。

關(guān)鍵詞： 社交網(wǎng)絡(luò)； 社團(tuán)結(jié)構(gòu)；非負(fù)矩陣分解

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）12-0049-02

1 概述

社交網(wǎng)絡(luò)如微博、微信、博客等在人們的生活中發(fā)揮的越來(lái)越廣泛的應(yīng)用，這些社交網(wǎng)絡(luò)也在網(wǎng)絡(luò)輿情等方面發(fā)揮了重要作用。這是因?yàn)樵谏缃痪W(wǎng)絡(luò)中，用戶之間相互連接、影響，從而促進(jìn)了信息像洪水一樣的快速而廣泛的傳播，與傳統(tǒng)媒體、門戶網(wǎng)站不同之處就在于，他沒(méi)有一個(gè)明顯的傳播主渠道。在社交網(wǎng)絡(luò)中，用戶經(jīng)常只是和少部分其他用戶信息交互頻繁，而與其他大部分用戶聯(lián)系很少，這樣，在用戶之間就形成了許多明顯的圈子，即社團(tuán)結(jié)構(gòu)。社團(tuán)內(nèi)的用戶之間相互聯(lián)系密切，相互共享信息或者進(jìn)行合作，如微博、facebook、Twitter等網(wǎng)絡(luò)應(yīng)用中，有共同興趣的節(jié)點(diǎn)相互分享視頻、評(píng)論等信息，形成一種社團(tuán)結(jié)構(gòu)[1]。在這些圈子內(nèi)，總會(huì)存在諸如名人、超級(jí)用戶（如微博中的大V）和活躍用戶，是社團(tuán)中的活躍分子。相比之下，用戶與社團(tuán)外部之間的聯(lián)系就相對(duì)稀疏的許多，但是，許多輿情也通過(guò)這些稀疏的連接將信息從一個(gè)社團(tuán)散布到其他社團(tuán)，從而引起其他社團(tuán)廣泛的關(guān)注。因此，在社交網(wǎng)絡(luò)上，既要挖掘這些社團(tuán)結(jié)構(gòu)，獲得用戶之間的關(guān)系結(jié)構(gòu)，便于對(duì)網(wǎng)絡(luò)進(jìn)行管理，又要掌握網(wǎng)絡(luò)中社團(tuán)活動(dòng)的重要用戶，掌握信息廣泛傳播的關(guān)鍵節(jié)點(diǎn)，只有這樣，才可以全面掌握社交網(wǎng)絡(luò)的活動(dòng)規(guī)律，正確預(yù)見(jiàn)潛在的網(wǎng)絡(luò)事件，挖掘諸如犯罪關(guān)系網(wǎng)等重要信息，保障網(wǎng)絡(luò)的健康有序。

社交網(wǎng)絡(luò)是一種復(fù)雜網(wǎng)絡(luò)，它規(guī)模龐大，結(jié)構(gòu)復(fù)雜，表現(xiàn)在節(jié)點(diǎn)數(shù)目巨大，網(wǎng)絡(luò)結(jié)構(gòu)呈現(xiàn)多種不同特征。連接具有多樣性，節(jié)點(diǎn)之間的連接權(quán)重存在詫異。節(jié)點(diǎn)集可能屬于非線性動(dòng)力學(xué)系統(tǒng)，例如節(jié)點(diǎn)狀態(tài)隨時(shí)間發(fā)生復(fù)雜變化。自2002年Girven和Newman提出社區(qū)挖掘的概念至今，新的理論、方法層出不窮，新的應(yīng)用領(lǐng)域不斷涌現(xiàn).它不僅吸引了來(lái)自計(jì)算機(jī)科學(xué)、物理、數(shù)學(xué)、生物和社會(huì)學(xué)等領(lǐng)域的研究者，成為最具挑戰(zhàn)性的多學(xué)科交叉研究課題之一；而且已被應(yīng)用于社會(huì)網(wǎng)絡(luò)分析，如恐怖組織識(shí)別、組織結(jié)構(gòu)管理、網(wǎng)絡(luò)推薦等方方面面。采用非負(fù)矩陣分解（NMF）的方法進(jìn)行社團(tuán)的發(fā)現(xiàn)。

2 基于非負(fù)矩陣分解的社團(tuán)發(fā)現(xiàn)的方法

非負(fù)矩陣分解是近年來(lái)出現(xiàn)的一種新方法。它對(duì)矩陣分解中的元素都添加了非負(fù)的限制，即大于或等于0，這與事物的整體是部分之和的直觀概念相符合，在應(yīng)用中具有很強(qiáng)的可解釋性，但是，對(duì)于非對(duì)稱矩陣的非負(fù)分解，目前的算法效果并不太好，而在實(shí)際中，很多網(wǎng)絡(luò)連接關(guān)系是有向的，它們對(duì)應(yīng)的矩陣就是非對(duì)稱的。我們通過(guò)對(duì)目標(biāo)矩陣進(jìn)行簡(jiǎn)單變換，添加必要的約束項(xiàng)，來(lái)實(shí)現(xiàn)基于非負(fù)矩陣分解的有向加權(quán)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)，同時(shí)進(jìn)一步分析用戶在社團(tuán)中的重要性，判斷用戶在社團(tuán)中所處的作用和特點(diǎn)，從而可以達(dá)到有效分析和解剖網(wǎng)絡(luò)結(jié)構(gòu)的目的。

2.1社團(tuán)發(fā)現(xiàn)模型

對(duì)于一個(gè)網(wǎng)絡(luò)連接關(guān)系，一般使用圖來(lái)描述。其中：表示第i個(gè)節(jié)點(diǎn)，表示第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)關(guān)系的大小。其中， X是社團(tuán)指示矩陣 ，其元素表示第i個(gè)節(jié)點(diǎn)屬于第j個(gè)社團(tuán)的大小。 S是社團(tuán)關(guān)系矩陣 ，其元素表示第i個(gè)社團(tuán)與第j個(gè)社團(tuán)的密切程度，n 表示節(jié)點(diǎn)的個(gè)數(shù)，k表示社團(tuán)的個(gè)數(shù)，一般來(lái)講，社團(tuán)的個(gè)數(shù)要遠(yuǎn)遠(yuǎn)小于節(jié)點(diǎn)的個(gè)數(shù)。

3 實(shí)驗(yàn)

3.1 Zachary karate數(shù)據(jù)集

Zachary karate數(shù)據(jù)集是一個(gè)真實(shí)網(wǎng)。它是Zachary空手道俱樂(lè)部成員關(guān)系網(wǎng)絡(luò)，是社會(huì)學(xué)分析等領(lǐng)域中最常用的一個(gè)小型檢測(cè)網(wǎng)絡(luò)之一。從1970到1972年，Wayne Zachary用三年時(shí)間觀察了美國(guó)一所大學(xué)空手道俱樂(lè)部成員間的社會(huì)關(guān)系，并構(gòu)造出了社會(huì)關(guān)系網(wǎng)（Zacharys karate club network）。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)分別表示某一個(gè)俱樂(lè)部成員，節(jié)點(diǎn)間的連接表示兩個(gè)成員經(jīng)常一起出現(xiàn)在俱樂(lè)部活動(dòng)（如空手道訓(xùn)練、俱樂(lè)部聚會(huì)等）之外的其他場(chǎng)合，即在俱樂(lè)部之外他們可以被稱為朋友。調(diào)查過(guò)程中，該俱樂(lè)部因?yàn)橹鞴躂ohn A.（節(jié)點(diǎn)34）與教練Mr. Hi（節(jié)點(diǎn)1）之間的爭(zhēng)執(zhí)而分裂成2個(gè)各自為核心的小俱樂(lè)部。這個(gè)矩陣經(jīng)常被用來(lái)檢測(cè)算法的有效性。

3.2 其他真實(shí)數(shù)據(jù)集

我們還利用其他真實(shí)數(shù)據(jù)集來(lái)做實(shí)驗(yàn)比較，如：American College Football，Neural Network數(shù)據(jù)集，以模塊度值[11]作為衡量指標(biāo)，實(shí)驗(yàn)表明，我們的算法都得到了較精確的社團(tuán)劃分結(jié)果。除了Dolphin Social Network數(shù)據(jù)集外，我們的算法都要好于其他基于非負(fù)矩陣分解的算法。

4 結(jié)論

本文針對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)復(fù)雜的連接關(guān)系，改進(jìn)了以往社團(tuán)劃分算法只能解決無(wú)向網(wǎng)絡(luò)問(wèn)題的缺點(diǎn)，構(gòu)建了基于有向加權(quán)圖的非負(fù)矩陣社團(tuán)劃分模型，提出了模型求解的算法，并且提出了社團(tuán)中節(jié)點(diǎn)的重要性等性質(zhì)的定量分析，在真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)表明，我們提出的算法正確的給出了社團(tuán)劃分結(jié)果，并對(duì)節(jié)點(diǎn)在社團(tuán)中的性質(zhì)進(jìn)行了詳細(xì)的分析，其結(jié)果符合人們的直觀認(rèn)識(shí)。我們的算法對(duì)于研究社交網(wǎng)絡(luò)中復(fù)雜的人際關(guān)系提供了一種有用的方法，對(duì)于網(wǎng)絡(luò)的結(jié)構(gòu)分析，信息在用戶之間的傳播有參考意義。

參考文獻(xiàn)：

[1] 曹貴強(qiáng).紙幣識(shí)別及紅外鑒偽技術(shù)的研究[D].遼寧科技大學(xué)，2014.

[2] 李玉翔.基于網(wǎng)絡(luò)社區(qū)的用戶興趣建模與推薦技術(shù)研究[D].解放軍信息工程大學(xué)，2013.