基于NMF的社團及屬性標簽發現方法

李 真,胡谷雨,潘志松,張艷艷

(陸軍工程大學 指揮控制工程學院,南京 210007)

1 引 言

在線社交媒體近年來得到了飛速發展,微博、微信、推特等社交媒體上有大量的用戶進行在線交互,從而形成了社交網絡.社交網絡的一個主要特征是具有社團結構.社團是指一些用戶的集合,其中(1)集合內部用戶交互緊密而集合之間用戶交互稀疏,(2)集合內部用戶之間具有較高的相似性而集合之間用戶相似性較低[1].社團發現是社交網絡分析的重要研究內容,有助于我們理解社交網絡的組織結構和功能模塊.

目前,研究人員已經提出了多種基于網絡拓撲的社團發現方法[2-4].但是,網絡拓撲只包含了網絡結構方面的信息,并且常常包含噪音[1,5],當網絡比較復雜時,僅僅根據拓撲信息無法準確地挖掘出社團.在社交媒體中,除了網絡拓撲,還存在許多節點內容信息,如節點屬性信息[5-7].例如,在社交網絡中可以獲得用戶的年齡、性別、職業、愛好、購物習慣等信息,這些信息通常稱為節點的內容信息[8].節點內容信息描述了節點的一些特性,從而可以度量節點之間的相似性.研究表明,在同一個社團中的節點不僅聯系緊密,并且具有相似的特性[8].網絡拓撲結構和節點內容信息從不同角度為社團發現提供依據,互為補充,并且這兩種信息隱含的社團結構是一致的[5-8].因此,將網絡拓撲和節點內容信息結合起來進行分析,可以提高社團發現的準確率[9-12].另一方面,目前的社團發現算法只能挖掘社團結構,但是不能對社團進行語義分析,例如社團的形成原因、社團的功能屬性等.對社團進行語義分析使我們不僅能夠從結構上理解社團,還能夠從行為特性上理解社團,有助于更好地分析、管理社團.節點的內容信息隱含了社團的語義信息,可以利用社團中節點共同的一些屬性來對社團進行描述.因此,從節點內容信息中挖掘社團的屬性標簽具有重要的研究意義.

如何有效地融合兩種信息進行社團發現并且對發現的社團進行語義分析是一個具有挑戰性的問題.首先,如何將兩種信息有效地融合是一個難題.雖然拓撲結構和節點內容隱含了相同的社團結構,但是兩種信息都是不全面的、包含噪音的信息,如何融合兩種信息來消除噪音的影響而不是疊加噪音是一個難題.其次,如何從節點的內容信息中挖掘社團的語義信息是一個有待解決的問題.用于描述社團的語義信息可以有多種,比如社團的形成原因、社團的功能、社團成員都有的特性等.因此,一個社團可以用多個屬性標簽來描述,如何挖掘出多個比較準確的屬性標簽來描述社團是個難題.第三,不同的社團之間存在聯系,并且不同社團可能有部分相同的屬性標簽,即聯系緊密的社團應該相應地具有較高的相似度.如何約束通過拓撲挖掘出來的社團關系與通過內容挖掘出來的社團關系的一致性,目前的文獻中還沒有討論.

為了解決上述問題,我們提出基于非負矩陣分解(Nonnegative Matrix Factorization,NMF)的社團及屬性標簽發現方法(Community and Attribute Label Detection,CALD).本文的主要貢獻如下:

1)我們提出了一種基于NMF的社團及屬性標簽發現方法CALD,該方法能夠綜合利用網絡拓撲和節點內容信息同時挖掘社團以及社團的屬性標簽,有助于更好地理解和分析社團;

2)該方法能夠約束從兩種信息中挖掘出來的社團結構以及社團間關系的一致性,從而降低噪音的影響,提高社團及其屬性標簽發現的準確率.

3)在多個真實數據集上的實驗結果表明,我們提出的算法可以有效地挖掘社團及其屬性標簽.

2 相關工作

近年來,通過融合網絡拓撲和內容信息進行社團發現得到了比較廣泛的關注和研究,該類方法一般被稱為多視角聚類[10,11],目前已經有多種算法被提出來.文獻[1]提出基于NMF的聚類方法,根據內容信息計算用戶相似度、留言相似度和用戶交互程度,用于輔助社團發現來提高準確率.文獻[9]提出基于semi-NMF的協同聚類方法,根據內容信息計算所有用戶之間的相似度,從而得到相似關系圖,與拓撲一起用于社團發現.文獻[10,11]在基于NMF的聚類框架中,提出了多種正則化項如節點對約束、中心約束、L1范數等約束從不同信息中發現的社團的一致性,提高了社團發現的準確率.文獻[12]提出的多視角聚類方法能夠在學習過程中自動設置參數的數值,避免了繁復的參數調節問題.在實際情況中,由于用戶之間關系的復雜性,不同視角的信息隱含的社團結構和社團數量可能不完全相同,文獻[13,14]討論了這種復雜場景下的多視角聚類問題,允許不同視角的信息隱含不完全相同的社團,提出了更加魯棒、可擴展性更高的社團發現方法,適應于更加貼近于實際的復雜場景.文獻[15]提出首先根據內容信息計算節點之間的相似性,然后將相似性關系與拓撲關系相融合得到新的節點關系圖,然后進行社團發現.文獻[16,17]通過矩陣分解獲得低秩矩陣和稀疏矩陣,其中低秩矩陣表示多個視角共有的數據,稀疏矩陣表示每個視角存在的噪音,最后根據低秩矩陣進行社團發現,從而降低了噪音的影響.文獻[18]根據馬爾可夫過程對每個視角建立轉移矩陣,并求出所有視角公共的低秩轉移矩陣,然后對轉移矩陣采用譜聚類的方法進行社團發現.文獻[19]提出不僅要考慮所有視角共有的信息,還要通過每個視角獨有的信息來解決信息缺失的問題.文獻中首先對多個視角的數據進行拼接,然后將矩陣分解為低秩的共享信息、稀疏的獨有信息和噪音三部分,最后綜合利用共享信息和獨有信息進行社團發現,提高了社團發現的準確率.但是,上述這些算法主要研究了如何更加有效地綜合利用拓撲結構和節點內容信息提高社團發現的準確率,無法對所發現的社團在語義上進行描述.

針對社團進行語義分析的研究目前相對較少.文獻[20]研究了如何同時挖掘網絡的社團結構和社團的語義描述,提出一個基于NMF的方法,能夠利用節點內容信息輔助拓撲信息提高社團發現的準確率,并同時從內容信息中挖掘社團的語義描述信息.文獻[21]針對社交媒體上一個用戶的所有聯系人構成的網絡進行研究,提出了一種可以對聯系人自動分組的算法.算法綜合利用聯系人之間的網絡拓撲和聯系人內容信息進行分組,同時對各個分組中聯系人的相似性進行度量,挖掘出聯系人共有的一些屬性作為分組的屬性.

3 基于NMF的社團及屬性標簽發現方法

在本節中,我們主要介紹基于NMF的社團及屬性標簽發現算法,其中3.1節給出了模型所需的定義,3.2節描述如何構建優化模型來同時挖掘社團和社團的屬性標簽,3.3節給出了優化目標的迭代求解方法.

3.1 基本定義

3.2 模型構建

針對網絡拓撲結構和節點內容信息,我們采用聯合NMF模型,同時挖掘社團指示矩陣U、社團關系指示矩陣S和社團屬性矩陣H,實現兩種信息的協同學習和有效融合.

(1)

(2)

(3)

綜合可得最終的目標函數如下:

(4)

3.3 優化求解

我們采用梯度下降獲得最優解.設γ,λ,ω為拉格朗日乘子來分別約束U≥0,S≥0,H≥0,則拉格朗日函數為:

(5)

則可以得到U、S、H的梯度為

(6)

(7)

(8)

由KKT條件可知γijUij=0,λijSij=0,ωijHij=0,則可以得到如下等式:

[-2AUST-2AUS+2USUT(US+UST)+2U-2XH)ijUij-γijUij=0

(9)

[-2UTAU+2UTUSUTU+2(S-HTH)]ijSij-λijSij=0

(10)

[-2XTU+2XTXH-2(HS+HST)+4HHTH]ijHij-ωijHij=0

(11)

則可以得到如下的更新規則:

更新U:固定其他變量,根據式(12)更新U.

(12)

更新S:固定其他變量,根據式(13)更新S.

(13)

更新H:固定其他變量,根據式(14)更新H.

(14)

重復迭代上述矩陣分解過程,并不斷更新U、S、H,直至目標函數趨于收斂或達到最大迭代次數.算法流程如下.

算法1.CALD算法

輸入:鄰接矩陣A和屬性矩陣X,社團個數k;

輸出:社團指示矩陣U和社團屬性矩陣H;

① 初始化U≥0,S≥0,H≥0;

②Whilenot convergentdo

③ 分別根據式(12)、(13)、(14)更新U、S、H;

④Endwhile

3.4 收斂性分析

首先采用輔助函數[22]來證明式(14)的收斂性，輔助函數的定義如下：

根據上述定義，可以得到目標函數(4)關于H的輔助函數.設J(H)為目標函數(4)中所有包含H的項的和，則J(H)的輔助函數為：

(15)

1http://mlg.ucd.ie/networks

2http://linqs.cs.umd.edu/projects/projects/lbc/

其中Xpq表示矩陣X中第p行和第q列的元素.式(15)是關于H的凸函數，其全局最小值為：

(16)

下面證明當其他變量固定不變時，根據式(14)更新H時，目標函數(4)將單調遞減直到收斂.

證明:根據定義1、引理1和J(H)的輔助函數，H的任意k(k≥0)次更新都有：

J(H(k))=Z(H(k),H(k))≥Z(H(k+1),H(k))≥J(H(k+1))

(17)

其中H(k)表示H的第k次迭代.因此可知J(H)是單調遞減的.因為目標函數(4)的下界為0，因此H將收斂，由此可證更新式(14)的收斂性.同理可證更新式(12)、(13)的收斂性.

3.5 復雜度分析

4 實驗與結果

在本節中,我們在真實網絡數據集上進行實驗,通過與現有方法進行比較來驗證CALD算法的有效性.

4.1 數據集

表1 數據集統計數據Table 1 Details of datasets

各個數據集的統計數據如表1所示.其中,前四個數據集1是從Twitter上收集的數據,Politics-uk數據集包含了英國419名政治人員在Twitter上的信息,他們被分為5個社團,分別對應5個政治黨派.Politics-ie數據集包含了愛爾蘭的348名政治人員的信息,他們被劃分為7個社團.Football數據集包含了248名足球運動員的信息,他們分別屬于20個足球俱樂部.Olympics數據集包含了2012年倫敦奧運會中28個項目的464名運動員的信息.這些數據集中包含了用戶之間的多種交互信息以及多種內容屬性信息,我們選用follows和listtext兩種信息,其中follows描述了用戶之間相互關注的情況,從中可以獲得網絡拓撲,listtext抽取了用戶發布的Tweets的關鍵詞,從中可以獲得用戶的屬性信息.后面3個數據集2分別收集了3個大學的網頁信息,共包含了612個網頁,每個網頁有1703維屬性.

4.2 實驗和結果

本文中采用的社團發現度量標準為正確率Accuracy[26]和規范化互信息NMI[27](Normalized Mutual Information),這兩種度量標準均以真實的社團劃分結果為參考,取值范圍為0到1,并且取值越高表示發現的社團結構與真實結果越接近,算法性能越好.

本文采用的對比算法有如下5種:PCoSpec (Pairwise Co-regularized Spectral clustering)[28]、CCoSpec(Center-wise Co-regularized Spectral clustering)[28]、PCoNMF (Pairwise Co-regularized NMF clustering)[10]、CCoNMF(Cluster-wise Co-regularized NMF clustering)[10]和SCI(Semantic Community Identification method)[20].其中,PCoSpec和CCoSpec是在譜聚類算法基礎上設計的協同聚類算法,分別采用基于節點對和基于中心的正則化項來約束網絡拓撲和節點內容隱含的社團指示矩陣的相似性.PCoNMF和CCoNMF利用NMF實現兩種數據信息的集成,分別采用節點對和基于中心的約束實現兩種社團指示矩陣之間的逼近.SCI基于NMF算法,不僅能夠挖掘社團結構,還能夠挖掘社團的屬性信息.

在本節中,我們在7個真實數據集上進行實驗,采用Accuracy和NMI作為社團發現的評價指標,通過與上述5種算法進行對比來驗證CALD算法的性能.各個算法在7個數據集上的Accuracy和NMI結果如表2和表3所示.

表3 各算法在7個數據集上的NMI結果Table 3 NMI for different methods on seven datasets

從表中可以看到,CALD算法在大部分數據集上具有較高的Accuracy和NMI.例如,在Politics-uk數據集上,CALD算法的Accuracy性能比SCI提高了12%,比CCoNMF算法提高了超過100%.這是由于CALD算法不僅約束兩種信息隱含的社團結構的一致性,而且約束社團間關系的一致性,降低了噪音的影響,充分利用了拓撲信息和內容信息,從而有效地提高了社團發現的準確率.另外可以看到在Cornell、Texas、Washington數據集上,各個算法的Accuracy、NMI值都比較低,這是因為這三個數據集所隱含的社團結構比較模糊,導致算法無法比較準確的挖掘出各個社團.

4.3 社團屬性標簽

在本節中,我們分析通過CALD算法發現的社團屬性標簽,以Politics-uk數據集為例進行說明.Politics-uk數據集收集了2012年英國419名政治人員在Twitter上的信息,其中listtext中包含了出現頻率超過500次的用戶Tweets關鍵詞,每個用戶都有3614維屬性.從數據集的真實社團劃分結果可知,所有的用戶被劃分為五個社團,分別對應保守黨、工黨、自由民主黨、蘇格蘭民族黨及其他黨派.

圖1 社團屬性標簽云Fig.1 Word clouds for different communities

圖1顯示了通過CALD算法挖掘出的保守黨、工黨和自由民主黨的屬性標簽.其中,單詞的大小與社團屬性值大小有關,即在社團屬性矩陣H中,值越大表示該屬性與該社團相關性越高,則在圖中的單詞也越大.我們去除沒有實際意義的單詞如“bb”等,每個社團選取最相關的10個屬性作為其標簽.在沒有先驗信息的條件下,通過社團發現算法劃分完社團之后,并不能確定各個社團對應哪個黨派.而CALD算法不僅能夠劃分出社團,還能夠挖掘出各社團的屬性標簽,從而可以分析社團的語義,有助于判斷社團所對應的實際黨派.例如,在圖1(a)中,可發現“sporting”、“head”、“lead”、“christian”字體較大,因為2012年倫敦舉辦了奧運會,這體現了當時執政的保守黨的工作.圖1(b)中的“labour2”′、 “labour3”、“workfare”等清晰地表明該社團是工黨,而圖1(c)中的“libdemmery”、“libdems2”、“democratic”等則與自由民主黨相關.從圖中還可以看到不同社團有部分屬性相同的標簽,例如“candidate2012”同時出現在圖1(b)和(c)中,原因可能是這兩個黨派都參與了2012年的地方議會競選.不同社團間相同的屬性標簽越多,表明社團間聯系也越多,其關系也越緊密.

5 總 結

社交網絡中包含的拓撲信息和內容信息都可以用于挖掘其中隱藏的社團結構.本文針對如何更加有效地利用兩種信息來發現社團并分析社團的語義屬性展開研究,提出了一種基于NMF的CALD社團及其屬性標簽挖掘方法.該方法的核心思想是構建一個矩陣聯合分解模型,并通過正則化項約束兩種信息所隱含的指示矩陣的相似性,從而有效地綜合應用拓撲信息和內容信息,提高社團發現的準確率,并挖掘社團的屬性標簽對社團進行語義描述.實驗結果表明,CALD算法能夠比較準確地發現網絡中的社團,并挖掘出各社團的代表性語義標簽,從而加深對社團的屬性、功能等的理解.目前,CALD算法的計算復雜度比較高,如何優化算法,提高算法的運行效率是下一步的研究內容.

：

[1] Pei Yu-long,Chakraborty N,Sycara K.Nonnegative Matrix tri-factorization with graph regularization for community detection in social networks[C].International Joint Conference on Artificial Intelligence,2015:2083-2089.

[2] Kuang D,Park H,Ding C H.Symmetric nonnegative matrix factorization for graph clustering[C].SIAM International Conference on Data Mining,2012.

[3] Van Dongen S.A cluster algorithm for graphs[C].Centrum Voor Wiskunde en Informatica,2000.

[4] Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[5] Tang L,Liu H.Community detection and mining in social media[M].Morgan and Claypool Publishers,2010.

[6] Tang L,Wang X,Liu H.Uncovering groups via heterogeneous interaction analysis[C].Proceedings of IEEE International Conference on Data Mining,2009:503-512.

[7] Wang N,Chen P,Li X.Community detection in heterogeneous multi-mode social network via Co-training[J].Foundations of Intelligent Systems,2014,277(2014):531-538.

[8] Yang Tian-bao,Rong Jin,Yun Chi,et al.Combining link and content for community detection:a discriminative approach[M].Springer,New York,2014.

[9] Gu Q,Zhou J.Co-clustering on manifolds[C].ACM Knowledge Discovery and Data Mining,2009:359-368.

[10] He X,Kan M Y,Xie P,et al.Comment-based multi-view clustering of web 2.0 items[C].Tthe 23rd International Conference on World Wide Web,2014:771-782.

[11] Tang J,Wang X,Liu H.Integrating social media data for community detection[C].Proceedings of the 2011 International Conference on Modeling and Mining Ubiquitous Social Media,Springer-Verlag,2011:1-20.

[12] Hidru D,Goldenberg A.EquiNMF:graph regularized multiview nonnegative matrix factorization[J].Eprint Arxiv,2014,1409(4018):1-9.

[13] Cheng W,Zhang X,Guo Z,et al.Flexible and robust co-regularized multi-domain graph clustering[C].ACM Knowledge Discovery and Data Mining,2013.

[14] Ni J,Tong H,Fan W,et al.Flexible and robust multi-network clustering[C].ACM Knowledge Discovery and Data Mining,2015.

[15] Ruan Y,Fuhry D,Parthasarathy S.Efficient community detection in large networks using content and links[C].Proceedings of the 22nd International Conference on World Wide Web,2012:1089-1098.

[16] Cheng B,Liu G,Wang J,et al.Multi-task low-rank affinity pursuit for image segmentation[C].IEEE International Conference on Computer Vision,2011.

[17] Guo X,Liu D,Jou B,et al.Robust object co-detection[C].IEEE Conference on Computer Vision and Pattern Recognition,2013.

[18] Xia R,Pan Y,Du L,et al.Robust multi-view spectral clustering via low-rank and sparse decomposition[C].The Association for the Advancement of Artificial Intelligence,2014.

[19] Deng C,Lv Z,Liu W,et al.Multi-view matrix decomposition:a new scheme for exploring discriminative information[C].Proceedings of the 24th International Conference on Artificial Intelligence,AAAI Press,2015.

[20] Xiao W,Di J,Xiaochun C,et al.Semantic community identification in large attribute networks[C].The Association for the Advancement of Artificial Intelligence,2016.

[21] Mcauley J,Leskovec J.Learning to discover social circles in ego networks[C].Advances in Neural Information Processing Systems,2012:539-547.

[22] Daniel D Lee,H Sebastian Seung.Algorithms for non-negative matrix factorization[C].In Advances in Neural Information Processing Systems,2001:556-562.

[23] Fei Wang,Tao Li,et al.Community discovery using nonnegative matrix factorization[J].Data Mining and Knowledge Discovery,2011,22(3):493-521.

[24] Nguyen H T,Dinh T N,Vu T.Community detection in multiplex social networks[C].IEEE Conference on Computer Communications Workshops,IEEE,2015:654-659.

[25] Chris Ding,Tao Li,Wei Peng,et al.Orthogonal nonnegative matrix tri-factorizations for clustering[C].ACM Knowledge Discovery and Data Mining,2006:126-135.

[26] Cheng J,Leng M,Li L,et al.Active semi-supervised community detection based on must-link and cannot-link constraints[J].Plos One,2014,9(10):e110088.

[27] Strehl A,Ghosh J.Cluster ensemble—a knowledge reuse framework for combining multiple partitions[J].J.Mach.Learn,2003,3(3):583-617.

[28] Kumar A,Rai P,Daumé H.Co-regularized multi-view spectral clustering[C].International Conference on Neural Information Processing Systems,2011:1413-1421.