基于非負矩陣分解的社交網絡社團發現方法

徐晟+趙永剛

摘要：社交網絡用戶眾多，連接關系復雜，挖掘其中的社團結構對于研究網絡的結構，分析用戶行為特點，揭示信息傳播規律都有重要的意義。本文針對有向加權和無向加權網絡特點，介紹了基于非負矩陣分解的社團劃分算法。真實數據集上的實驗表明，算法是有效的，符合人們對網絡中人際關系的直觀理解，為研究社交網絡的結構和關系演變提供了一種有效的方法。

關鍵詞： 社交網絡； 社團結構；非負矩陣分解

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）12-0049-02

1 概述

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

社交網絡是一種復雜網絡，它規模龐大，結構復雜，表現在節點數目巨大，網絡結構呈現多種不同特征。連接具有多樣性，節點之間的連接權重存在詫異。節點集可能屬于非線性動力學系統，例如節點狀態隨時間發生復雜變化。自2002年Girven和Newman提出社區挖掘的概念至今，新的理論、方法層出不窮，新的應用領域不斷涌現.它不僅吸引了來自計算機科學、物理、數學、生物和社會學等領域的研究者，成為最具挑戰性的多學科交叉研究課題之一；而且已被應用于社會網絡分析，如恐怖組織識別、組織結構管理、網絡推薦等方方面面。采用非負矩陣分解（NMF）的方法進行社團的發現。

2 基于非負矩陣分解的社團發現的方法

非負矩陣分解是近年來出現的一種新方法。它對矩陣分解中的元素都添加了非負的限制，即大于或等于0，這與事物的整體是部分之和的直觀概念相符合，在應用中具有很強的可解釋性，但是，對于非對稱矩陣的非負分解，目前的算法效果并不太好，而在實際中，很多網絡連接關系是有向的，它們對應的矩陣就是非對稱的。我們通過對目標矩陣進行簡單變換，添加必要的約束項，來實現基于非負矩陣分解的有向加權網絡的社團發現，同時進一步分析用戶在社團中的重要性，判斷用戶在社團中所處的作用和特點，從而可以達到有效分析和解剖網絡結構的目的。

2.1社團發現模型

對于一個網絡連接關系，一般使用圖來描述。其中：表示第i個節點，表示第i個節點到第j個節點關系的大小。其中， X是社團指示矩陣 ，其元素表示第i個節點屬于第j個社團的大小。 S是社團關系矩陣 ，其元素表示第i個社團與第j個社團的密切程度，n 表示節點的個數，k表示社團的個數，一般來講，社團的個數要遠遠小于節點的個數。

3 實驗

3.1 Zachary karate數據集

Zachary karate數據集是一個真實網。它是Zachary空手道俱樂部成員關系網絡，是社會學分析等領域中最常用的一個小型檢測網絡之一。從1970到1972年，Wayne Zachary用三年時間觀察了美國一所大學空手道俱樂部成員間的社會關系，并構造出了社會關系網（Zacharys karate club network）。網絡中的每個節點分別表示某一個俱樂部成員，節點間的連接表示兩個成員經常一起出現在俱樂部活動（如空手道訓練、俱樂部聚會等）之外的其他場合，即在俱樂部之外他們可以被稱為朋友。調查過程中，該俱樂部因為主管John A.（節點34）與教練Mr. Hi（節點1）之間的爭執而分裂成2個各自為核心的小俱樂部。這個矩陣經常被用來檢測算法的有效性。

3.2 其他真實數據集

我們還利用其他真實數據集來做實驗比較，如：American College Football，Neural Network數據集，以模塊度值[11]作為衡量指標，實驗表明，我們的算法都得到了較精確的社團劃分結果。除了Dolphin Social Network數據集外，我們的算法都要好于其他基于非負矩陣分解的算法。

4 結論

本文針對網絡中節點復雜的連接關系，改進了以往社團劃分算法只能解決無向網絡問題的缺點，構建了基于有向加權圖的非負矩陣社團劃分模型，提出了模型求解的算法，并且提出了社團中節點的重要性等性質的定量分析，在真實的網絡數據集上的實驗表明，我們提出的算法正確的給出了社團劃分結果，并對節點在社團中的性質進行了詳細的分析，其結果符合人們的直觀認識。我們的算法對于研究社交網絡中復雜的人際關系提供了一種有用的方法，對于網絡的結構分析，信息在用戶之間的傳播有參考意義。

參考文獻：

[1] 曹貴強.紙幣識別及紅外鑒偽技術的研究[D].遼寧科技大學，2014.

[2] 李玉翔.基于網絡社區的用戶興趣建模與推薦技術研究[D].解放軍信息工程大學，2013.