王 銳，吳玲玲，石 川，吳 斌

?

基于社團(tuán)結(jié)構(gòu)的鏈接預(yù)測和屬性推斷聯(lián)合解決方法

王 銳，吳玲玲，石 川，吳 斌

(北京郵電大學(xué)智能通信軟件與多媒體北京市重點實驗室，北京 100876)

鏈接預(yù)測與屬性推斷是社交網(wǎng)絡(luò)數(shù)據(jù)挖掘的兩項重要任務(wù).之前的大部分研究工作將鏈接預(yù)測和屬性推斷視為不同的問題，分別研究解決方法.然而，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的同質(zhì)性理論，社交網(wǎng)絡(luò)中的鏈接與屬性之間具有內(nèi)在關(guān)聯(lián).本文提出了基于社團(tuán)結(jié)構(gòu)的鏈接預(yù)測和屬性推斷聯(lián)合解決方法(LAIC)，將社團(tuán)結(jié)構(gòu)作為鏈接預(yù)測與屬性推斷的關(guān)聯(lián)因子，利用用戶屬性和社團(tuán)結(jié)構(gòu)進(jìn)行鏈接預(yù)測，利用鏈接信息得到社團(tuán)屬性進(jìn)而推斷用戶屬性.LAIC不僅同時解決了鏈接預(yù)測和屬性推斷問題，而且通過迭代使鏈接預(yù)測和屬性推斷的準(zhǔn)確率可以相互提升.兩個真實數(shù)據(jù)集上的實驗證明LAIC方法是有效的.

社交網(wǎng)絡(luò)；鏈接預(yù)測；屬性推斷；社團(tuán)結(jié)構(gòu)

1 引言

在社交網(wǎng)絡(luò)中，鏈接預(yù)測可以幫助用戶找到潛在好友，改善用戶體驗.屬性推斷可以完善用戶信息，為用戶提供有針對性的服務(wù).因此，鏈接預(yù)測和屬性推斷是社交網(wǎng)絡(luò)數(shù)據(jù)挖掘的兩項重要任務(wù).

之前的研究將鏈接預(yù)測與屬性推斷視為兩個不同的問題.鏈接預(yù)測的研究主要基于節(jié)點相似性與拓?fù)浣Y(jié)構(gòu)相似性.例如，Chen等人[1]在有向圖中利用隨機(jī)游走到達(dá)時間衡量用戶相似性，進(jìn)行聚類，在同一個聚簇中的節(jié)點被認(rèn)為是朋友.屬性推斷方法大致分為兩類：基于特征的方法[2,3]與基于網(wǎng)絡(luò)結(jié)構(gòu)的方法[4,5].基于特征的方法致力于尋找有效特征訓(xùn)練分類器.基于網(wǎng)絡(luò)結(jié)構(gòu)的方法依據(jù)用戶與好友的緊密性推斷用戶屬性.

然而，根據(jù)同質(zhì)性理論[6]，用戶的相同屬性越多，用戶間存在鏈接的概率越大.反之，用戶間若存在鏈接，則他們具有相同屬性的概率越大.因此，鏈接預(yù)測和屬性推斷之間存在內(nèi)在關(guān)聯(lián).至今，只有極少部分工作將鏈接預(yù)測和屬性推斷問題聯(lián)合解決.Yin等人[7]通過社會屬性網(wǎng)絡(luò)中的隨機(jī)游走將鏈接預(yù)測與屬性推斷結(jié)合起來.尹緒森[8]等人利用兩層人工神經(jīng)網(wǎng)絡(luò)，建立可同時解決鏈接預(yù)測與屬性推斷問題的綜合框架.

為了同時解決鏈接預(yù)測和屬性推斷問題，本文提出了基于社團(tuán)結(jié)構(gòu)的鏈接預(yù)測和屬性推斷聯(lián)合解決方法LAIC(Link and Attribute Inference Based on Community).LAIC基于可重社團(tuán)探測，首先利用節(jié)點的社團(tuán)信息和屬性信息進(jìn)行鏈接預(yù)測.之后使用基于社團(tuán)的隨機(jī)游走獲得社團(tuán)屬性，通過用戶所屬社團(tuán)的屬性推斷用戶屬性.最后通過迭代使鏈接預(yù)測與屬性推斷相互提高.

2 基于社團(tuán)結(jié)構(gòu)的鏈接預(yù)測與屬性推斷聯(lián)合解決方法

2.1 社會屬性網(wǎng)絡(luò)

本文使用社會屬性網(wǎng)絡(luò)解決鏈接預(yù)測和屬性推斷問題，這里給出定義.

定義1 社會屬性網(wǎng)絡(luò)SAN

給定網(wǎng)絡(luò)G=(V,E)，V是節(jié)點集，E是邊集.構(gòu)造網(wǎng)絡(luò)G′=(V′,E′)，對G中的每個節(jié)點，在G′中也相應(yīng)構(gòu)造一個節(jié)點，稱為用戶節(jié)點Vp.對G中的每條邊，在G′中也相應(yīng)構(gòu)造一條邊.對每個用戶屬性，在G′中構(gòu)造一個節(jié)點，稱為屬性節(jié)點Va，V′=Vp∪Va.若某個用戶具有某個屬性，則在該用戶節(jié)點與該屬性節(jié)點間構(gòu)造一條邊.

圖1為SAN的示意圖.圖中矩形表示屬性節(jié)點，人物表示用戶節(jié)點，虛線表示用戶屬性，實線表示用戶間的好友關(guān)系.

2.2 基本思路

社團(tuán)包含網(wǎng)絡(luò)的結(jié)構(gòu)信息，兩個用戶的社團(tuán)重疊次數(shù)越多，他們之間越可能存在鏈接[9].兩個用戶的共同屬性越多，則兩個用戶越相似，他們之間也越可能存在鏈接.因此可以通過社團(tuán)信息和用戶屬性求得缺失的鏈接.

此外，社團(tuán)與屬性不是獨立的.社團(tuán)中用戶的屬性決定了社團(tuán)的屬性.反之，若已知社團(tuán)屬性，則可推斷社團(tuán)中用戶的屬性.每個用戶可同時屬于多個社團(tuán)，而每個社團(tuán)具有各自的社團(tuán)屬性.因此可根據(jù)用戶所屬社團(tuán)的屬性推斷用戶的屬性.

圖2說明了LAIC的思路.圖中橢圓形表示社團(tuán)，其它圖標(biāo)含義與圖1相同.圖2中，Ted和Bob同屬于這兩個社團(tuán)且擁有共同屬性“籃球”，而Ted和Lily只同屬于一個社團(tuán)且沒有共同屬性.因此，相對于Lily，Ted和Bob之間鏈接存在的概率更大.此外，Ted同時屬于社團(tuán)A和B，因此，對社團(tuán)A和B越重要的屬性越可能是Ted的屬性.

2.3 具體方法

2.3.1 社團(tuán)探測

本文使用alpha-beta社團(tuán)探測方法[10]進(jìn)行社團(tuán)探測，該方法適用于可重社團(tuán)劃分，高效、簡單且易于并行化.其他能夠準(zhǔn)確發(fā)掘可重社團(tuán)結(jié)構(gòu)的方法亦可用于本文提出的框架.

假設(shè)通過可重社團(tuán)劃分，將G劃分為K個社團(tuán)，并且求得節(jié)點與社團(tuán)的關(guān)系F.用戶-社團(tuán)關(guān)系F為N*K的矩陣，F(xiàn)uc=1表示節(jié)點u屬于社團(tuán)c，否則Fuc=0.

2.3.2 鏈接預(yù)測

為構(gòu)建利用社團(tuán)結(jié)構(gòu)和用戶屬性預(yù)測鏈接的概率模型，本文提出2點假設(shè)：

(1)社團(tuán)結(jié)構(gòu)和用戶屬性聯(lián)合影響節(jié)點間鏈接存在的概率.

(2)不同社團(tuán)對鏈接存在概率的影響是相互獨立的.

僅考慮社團(tuán)信息時，Leskovec等人[9]提出同屬于社團(tuán)c的節(jié)點u和v間存在鏈接的概率為：

Puv(c)=1-exp(-Fuc·Fvc)

(1)

當(dāng)u和v中的任一點不屬于社團(tuán)c時，F(xiàn)uc=0或Fvc=0，則Puv(c)=0.假設(shè)每個社團(tuán)以概率1-exp(-Fuc·Fvc)連接u和v.由于不同社團(tuán)對鏈接存在概率的影響是相互獨立的，u、v間不存在鏈接的概率可寫成u、v在所有社團(tuán)下不存在鏈接的概率之積：

(2)

u、v間存在鏈接的概率Puv為：

(3)

由假設(shè)知，用戶屬性對鏈接存在概率有影響，且用戶具有的相同屬性越多，用戶間存在鏈接的概率越大.考慮到用戶屬性，我們將式(3)改進(jìn)為如下形式：

(4)

2.3.3 屬性推斷

為構(gòu)建利用社團(tuán)結(jié)構(gòu)和社團(tuán)屬性推斷用戶屬性的模型，本文提出2點假設(shè)：

(1)社團(tuán)中所有節(jié)點的屬性均為該社團(tuán)的屬性，但每個社團(tuán)屬性與社團(tuán)的關(guān)聯(lián)強(qiáng)度存在區(qū)別.

(2)節(jié)點的屬性由其所屬社團(tuán)的屬性決定.

從社團(tuán)Ck重啟時隨機(jī)游走的迭代公式為：

(5)

(6)

因為屬性節(jié)點只能與用戶節(jié)點相連，所以從屬性節(jié)點到用戶節(jié)點的轉(zhuǎn)移概率設(shè)置如下：

(7)

用戶節(jié)點可與屬性或用戶節(jié)點相連，我們用參數(shù)λ權(quán)衡屬性與用戶節(jié)點權(quán)重.一般SAN中的隨機(jī)游走區(qū)分用戶-用戶與用戶-屬性兩種邊，同類型邊的轉(zhuǎn)移概率相同.考慮到節(jié)點間的影響力是有區(qū)別的，我們提出利用鏈接存在概率表示邊的影響力.從用戶到用戶節(jié)點的轉(zhuǎn)移概率設(shè)置如下：

w(p′,p)=

(8)

當(dāng)(p′,p)∈E時，Pp′p=1.否則Pp′p等于邊(p′,p)的存在概率.

根據(jù)Yin等人[7]提出的混合權(quán)重的方法，我們用wp(a)衡量對用戶p而言，屬性a的重要性：

wp(a)=g(a)×lp(a)

(9)

其中，g(a)和lp(a)分別是屬性a的全局重要性和本地重要性：

(10)

(11)

將wp(a)歸一化作為從用戶節(jié)點到屬性節(jié)點的轉(zhuǎn)移概率：

w(p,a)=

(12)

當(dāng)從社團(tuán)Ck重啟的隨機(jī)游走收斂時，各屬性節(jié)點的到達(dá)概率rCka表示社團(tuán)Ck與各屬性的關(guān)聯(lián)強(qiáng)度：

(13)

當(dāng)從K個社團(tuán)重啟的隨機(jī)游走都收斂時，得到社團(tuán)-屬性矩陣AC：

(14)

用社團(tuán)-屬性矩陣AC和用戶-社團(tuán)關(guān)系F的乘積填充用戶-屬性矩陣AV中的缺失項：

(15)

(16)

2.3.4 時間復(fù)雜度分析

LAIC算法的時間復(fù)雜度由鏈接預(yù)測和屬性推斷兩部分構(gòu)成.鏈接預(yù)測的時間復(fù)雜度為O((m+c)n2)，屬性推斷的時間復(fù)雜度為O(t1cm(m+n))，其中m為屬性數(shù)，c為社團(tuán)數(shù)，n為用戶節(jié)點數(shù)，t1為隨機(jī)游走收斂所需的迭代次數(shù).因此LAIC算法的時間復(fù)雜度為O(t2((m+c)n2+t1cm(m+n)))，其中t2為鏈接預(yù)測和屬性推斷過程相互迭代的最大次數(shù).

3 實驗

本節(jié)首先介紹實驗數(shù)據(jù)集，隨后介紹對比方法，最后展示實驗結(jié)果及結(jié)果分析.

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

新浪微博數(shù)據(jù)集：我們從新浪微博上爬取該數(shù)據(jù)集(http://weibo.com)，包括34,199個用戶和691,522個鏈接.我們抽取用戶的標(biāo)簽、學(xué)校及公司作為用戶屬性.隨后刪去度小于20的點和屬性少于3的點以及與這些點相連的邊.最后得到2503個用戶，56,768個鏈接和228個屬性.

表1 數(shù)據(jù)集信息統(tǒng)計

電信數(shù)據(jù)集：該數(shù)據(jù)集來自第一屆中國大數(shù)據(jù)競賽(http://www.bigcloudsys.com/ccf2013/detail2.html)，包括用戶間的電話、短信記錄和用戶信息.我們抽取身份為學(xué)生的77,577個用戶作為備選節(jié)點.用戶的學(xué)校作為用戶屬性.若用戶間相互發(fā)送超過5條短信，則用戶間存在一條鏈接.刪除處理后孤立的節(jié)點得到34,905個用戶，70,495個鏈接和127個不同的學(xué)校id.

兩個數(shù)據(jù)集的統(tǒng)計信息如表1所示.

3.2 對比方法

共同鄰居(CN)：鏈接預(yù)測算法.將與目標(biāo)用戶共同鄰居最多的用戶推薦給他.

共同屬性(CA)：屬性推斷算法.將目標(biāo)用戶的鄰居擁有最多的屬性推薦給他.

帶重啟的隨機(jī)游走(RW)[11]：鏈接預(yù)測算法.設(shè)置重啟概率從目標(biāo)用戶重啟，游走過程收斂后，將到達(dá)概率高的節(jié)點推薦給他.

社會屬性網(wǎng)絡(luò)上的隨機(jī)游走(SAN-RW)[7]：鏈接預(yù)測和屬性推斷聯(lián)合解決方法.根據(jù)用戶的好友關(guān)系和用戶屬性構(gòu)造社會屬性網(wǎng)絡(luò)SAN.在SAN中進(jìn)行帶重啟的隨機(jī)游走，游走過程收斂后，分別將到達(dá)概率高的用戶和屬性節(jié)點作為鏈接預(yù)測與屬性推斷的返回結(jié)果.

3.3 有效性實驗

每次實驗隨機(jī)選取10%的鏈接和用戶屬性作為測試集，即Ed和(AV)d.用剩下的網(wǎng)絡(luò)Gr=(V,Er,(AV)r)訓(xùn)練模型，使用訓(xùn)練出的模型在測試集上進(jìn)行實驗.鏈接預(yù)測和屬性推斷的結(jié)果不斷迭代更新直到收斂或達(dá)到實驗設(shè)置的最大迭代次數(shù)40次.RW，SAN-RW和LAIC的重啟概率α設(shè)為0.8.LAIC和SAN-RW的參數(shù)λ設(shè)為0.3.新浪微博數(shù)據(jù)集和電信數(shù)據(jù)集中LAIC的參數(shù)β分別設(shè)為0.9和0.3.

實驗重復(fù)進(jìn)行50次，鏈接預(yù)測平均結(jié)果如圖3所示，橫坐標(biāo)TOPK表示為用戶推薦鏈接的數(shù)量.圖3中，LAIC在兩個數(shù)據(jù)集上的準(zhǔn)確性始終優(yōu)于其他方法.原因是我們同時使用了網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)和用戶屬性信息且鏈接預(yù)測與屬性推斷之間相互迭代提高，這是其他算法沒有的.

屬性推斷平均結(jié)果如表2所示.由表2知，新浪微博數(shù)據(jù)集中，所有方法的準(zhǔn)確率都偏低，這是因為我們沒有對屬性做語義歸并，如：我們的算法將“北郵”和“北京郵電大學(xué)”看作不同的屬性.并且，新浪微博中除了社會關(guān)系還有一些興趣關(guān)系，在這種社交網(wǎng)絡(luò)中進(jìn)行屬性推斷比較難.電信數(shù)據(jù)集中，用戶的學(xué)校id不存在歧義，且電信網(wǎng)絡(luò)是基于社會關(guān)系的，所以屬性推斷準(zhǔn)確率較高.表2中，LAIC的準(zhǔn)確率總是最高的，原因是同一社團(tuán)的用戶通常具有相同的屬性，我們利用網(wǎng)絡(luò)的結(jié)構(gòu)信息彌補(bǔ)了屬性信息的缺失.并且，LAIC利用鏈接預(yù)測步驟得到的鏈接存在概率彌補(bǔ)遺失的鏈接信息，鏈接信息越充分時，推斷用戶屬性越準(zhǔn)確.

表2 不同方法屬性推斷效果對比

3.4 不同缺失比例對比實驗

我們在兩個數(shù)據(jù)集上擴(kuò)大刪除比例來驗證缺失信息更多的情況下LAIC的適用性.依次選取10%，20%，30%，40%，50%的鏈接和用戶屬性作為測試集，每次為用戶推薦排名第一的鏈接或?qū)傩?相關(guān)參數(shù)設(shè)置如前所述，實驗重復(fù)進(jìn)行50次，平均結(jié)果如圖4所示.圖4中，隨著測試集比例的增大，所有方法的準(zhǔn)確率都在下降，但LAIC在兩個任務(wù)中的準(zhǔn)確率始終最高.原因是LAIC是基于社團(tuán)結(jié)構(gòu)的，網(wǎng)絡(luò)中個別用戶缺失的信息可由該用戶所屬社團(tuán)中其他用戶的信息部分彌補(bǔ).此外，LAIC中鏈接預(yù)測與屬性推斷相互迭代使缺失信息不斷得到補(bǔ)充.

3.5 算法迭代過程實驗

算法迭代過程實驗用于驗證鏈接預(yù)測與屬性推斷相互迭代的效果.相關(guān)參數(shù)設(shè)置如前所述，迭代次數(shù)從5增加至50，每次增加5，對不同的迭代次數(shù)分別進(jìn)行50次實驗，實驗平均結(jié)果如圖5.由圖5可知迭代次數(shù)大約在25～30次時，準(zhǔn)確率的變化趨于平緩.在兩個數(shù)據(jù)集中，隨著迭代次數(shù)的增加，屬性推斷與鏈接預(yù)測的準(zhǔn)確率都在增加，這證實了LAIC能使屬性推斷與鏈接預(yù)測相互提高.

4 結(jié)束語

本文提出利用社團(tuán)結(jié)構(gòu)綜合解決鏈接預(yù)測與屬性推斷問題的框架LAIC.實驗證明，LAIC不僅能同時解決鏈接預(yù)測和屬性推斷問題，使其相互提升，且準(zhǔn)確率高于現(xiàn)有的方法.該框架在一些方面還存在提升的空間.首先，可以通過算法優(yōu)化解決算法時間復(fù)雜度較大的問題.其次，可以通過屬性語義歸并來提高屬性推斷的準(zhǔn)確率.

[1]Chen M,Liu J,Tang X.Clustering via random walk hitting time on directed graphs[A].Proceedings of the 23rd National Conference on Artificial Intelligence[C].Chicago,Illinois,USA:AAAI,2008.616-621.

[2]Rao D,Yarowsky D,Shreevats A,et al.Classifying latent user attributes in twitter[A].Proceedings of the 2nd International Workshop on Search and Mining User-generated Contents[C].Toronto,Canada:ACM,2010.37-44.

[3]Leuski A.Email is a stage:discovering people roles from email archives[A].Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval[C].Sheffield,UK:ACM,2004.502-503.

[4]Mislove A,Viswanath B,Gummadi K P,et al.You are who you know:inferring user profiles in online social networks[A].Proceedings of the Third ACM International Conference on Web Search and Data Mining[C].New York,USA:ACM,2010.251-260.

[5]Coscia M,Rossetti G,Giannotti F,et al.DEMON:a local-first discovery method for overlapping communities[A].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Beijing,China:ACM,2012.615-623.

[6]La Fond T,Neville J.Randomization tests for distinguishing social influence and homophily effects[A].Proceedings of the International World Wide Web Conference[C].Raleigh,NC,USA:Springer,2010.601-610.

[7]Yin Z,Gupta M,Weninger T,et al.A unified framework for link recommendation using random walks[A].IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining[C].Odense,Denmark:IEEE/ACM,2010.152-159.

[8]Yin X,Wu B,Lin X.A unified framework for predicting attributes and links in social networks[A].Proceedings of the 2013 IEEE International Conference on Big Data[C].Santa Clara,CA,USA:IEEE,2013.153-160.

[9]Yang J,McAuley J,Leskovec J.Community detection in networks with node attributes[A].Proceedings of the 13th International Conference on Data Mining[C].Dallas,TX,USA:IEEE,2013.1151-1156.

[10]He J,Hopcroft J,Liang H,et al.Detecting the structure of social networks using (α,β)-communities[A].Proceedings of the 8th International Workshop on Algorithms and Models for the Web-Graph[C].Atlanta,GA,USA:Springer,2011.26-37.

[11]Tong H,Faloutsos C,Pan J Y.Fast random walk with restart and its applications[A].Proceedings of the 6th IEEE International Conference on Data Mining[C].Hong Kong,China:IEEE,2006.613-622.

王 銳 女，1992年6月生于河南洛陽.北京郵電大學(xué)計算機(jī)學(xué)院碩士研究生.研究方向為數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí).

E-mail:aboutstefanie@163.com

吳玲玲 女，1989年4月生于福建漳州.2015年畢業(yè)于北京郵電大學(xué)計算機(jī)學(xué)院.研究方向為數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí).

E-mail:wulingling@bupt.edu.cn

Integrating Link Prediction and Attribute Inference Based on Community Structure

WANG Rui,WU Ling-ling,SHI Chuan,WU Bin

(BeijingKeyLabofIntelligentTelecommunicationSoftwareandMultimedia,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)

Link prediction and attribute inference are two important tasks in social network mining.Most of the previous studies treated link prediction and attribute inference as different problems and sought for solutions separately.However,according to the theory of homophily,there are intrinsic relations between links and attributes in social network.We propose the link and attribute inference based on community (LAIC) solution which utilizes the community structure to connect link prediction and attribute inference.LAIC employs users’ attribute and community structure for link prediction,and takes advantage of link information to get the attributes of communities for attribute inference of users.LAIC is not only able to predict attributes and links simultaneously,but also promotes the precision of link prediction and attribute inference mutually through iterations.Experiments on two real datasets verify the effectiveness of LAIC.

social network;link prediction;attribute inference;community structure

2015-02-05;

2015-05-27;責(zé)任編輯：覃懷銀

國家重點基礎(chǔ)研究發(fā)展計劃(No.2013CB329602)；國家自然科學(xué)基金(No.61375058,No.71231002)；北京市高等教育青年英才項目(No.YETP0444)

TP391

A

0372-2112 (2016)09-2062-06

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.006