廖國(guó)瓊王汀利鄧 琨萬(wàn)常選

1(江西財(cái)經(jīng)大學(xué)信息管理學(xué)院 南昌 330013)2(江西省高校數(shù)據(jù)與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室(江西財(cái)經(jīng)大學(xué)) 南昌 330013) (liaoguoqiong@163.com)

?

離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中的多用戶位置鄰近預(yù)測(cè)

廖國(guó)瓊1,2王汀利1鄧 琨1,2萬(wàn)常選1,2

1(江西財(cái)經(jīng)大學(xué)信息管理學(xué)院 南昌 330013)2(江西省高校數(shù)據(jù)與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室(江西財(cái)經(jīng)大學(xué)) 南昌 330013) (liaoguoqiong@163.com)

離線瞬態(tài)社會(huì)網(wǎng)絡(luò)(offline ephemeral social network, OffESN)是一種在特定時(shí)間通過參加特定事件臨時(shí)組建的新型社會(huì)網(wǎng)絡(luò).隨著移動(dòng)智能終端的普及和短距離通信技術(shù)(如藍(lán)牙、RFID技術(shù)等)的發(fā)展，該類型網(wǎng)絡(luò)得到工業(yè)界和學(xué)術(shù)界越來(lái)越多的關(guān)注.位置鄰近(location proximity)關(guān)系是指用戶在離線網(wǎng)絡(luò)中的相遇關(guān)系.針對(duì)位置鄰近關(guān)系的動(dòng)態(tài)變化性及持續(xù)時(shí)間短等特征，主要研究離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中多用戶鄰近關(guān)系預(yù)測(cè)問題.首先，給出離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中的相關(guān)概念及問題定義；然后，設(shè)計(jì)多用戶鄰近關(guān)系預(yù)測(cè)總體框架，包括網(wǎng)絡(luò)片段收集、疊加網(wǎng)絡(luò)構(gòu)建、網(wǎng)絡(luò)過濾及極大緊密子圖發(fā)現(xiàn)等步驟.由于多鄰近關(guān)系的數(shù)量及每個(gè)鄰近關(guān)系中用戶的數(shù)量不能事先確定，基于分裂思想提出了一種極大緊密子圖挖掘策略，以預(yù)測(cè)多用戶位置鄰近關(guān)系.該挖掘算法是以加權(quán)邊介數(shù)為網(wǎng)絡(luò)分裂依據(jù)，以聚集密度為分裂結(jié)束條件.在2個(gè)真實(shí)數(shù)據(jù)集上完成了實(shí)驗(yàn)，驗(yàn)證了所提出預(yù)測(cè)策略的可行性及效率.

社會(huì)網(wǎng)絡(luò)；瞬態(tài)社會(huì)網(wǎng)絡(luò)；位置鄰近；極大緊密子圖；鏈接預(yù)測(cè)

近年來(lái)，隨著Internet技術(shù)的快速發(fā)展，在線社會(huì)網(wǎng)絡(luò)(online social networks)，如Facebook,Linkin,Twitter,QQ等已成為人們即時(shí)通信、分享消息及交友的方便快捷平臺(tái)[1].與此同時(shí)，隨著移動(dòng)智能終端的普及和短距離通信技術(shù)(如藍(lán)牙、RFID等)的快速發(fā)展，離線瞬態(tài)社會(huì)網(wǎng)絡(luò)(offline ephe-meral social network, OffESN)開始得到越來(lái)越多的關(guān)注[2-6].

OffESN是人們?cè)谔囟〞r(shí)間通過參加特定事件(如參加學(xué)術(shù)會(huì)議、博覽會(huì)等[4])臨時(shí)組建的社會(huì)網(wǎng)絡(luò).不同于在線社會(huì)網(wǎng)絡(luò)中相對(duì)穩(wěn)定的朋友關(guān)系(friendship)，OffESN中的社會(huì)關(guān)系主要是通過藍(lán)牙、RFID等短距離通信技術(shù)收集到的位置鄰近(location proximity)關(guān)系[3]，即用戶相遇關(guān)系.不同于基于位置社會(huì)網(wǎng)絡(luò)(location-based social network, LBSN)，OffESN更多關(guān)注的是用戶是否相遇，而不關(guān)心用戶在何處相遇.OffESN中的位置鄰近關(guān)系主要具有4個(gè)特征：

1) 面對(duì)面接觸(face-to-face contact).不同于在線社會(huì)網(wǎng)絡(luò)，OffESN中的位置鄰近關(guān)系是通過離線的面對(duì)面接觸形成.

2) 事件驅(qū)動(dòng)(event-driven).OffESN主要包含2類事件：預(yù)定事件(prescheduled events)和自發(fā)事件(spontaneous events)[6].位置鄰近關(guān)系是伴隨著這些事件的開始而產(chǎn)生、事件的結(jié)束而消失.

3) 動(dòng)態(tài)性.OffESN中的位置鄰近關(guān)系是動(dòng)態(tài)變化的，即用戶的相遇關(guān)系隨時(shí)間的變化而變化.

4) 持續(xù)時(shí)間短.OffESN中事件的持續(xù)時(shí)間通常較短.例如，在由參加學(xué)術(shù)會(huì)議形成的OffESN中，預(yù)定事件(如主題報(bào)告或分組討論)的持續(xù)時(shí)間一般為0.5～1 h， 而自發(fā)事件的持續(xù)時(shí)間通常在0.5 h之內(nèi).

在離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中，一群人常常聚集在一起參加活動(dòng)或交流.例如在參加學(xué)術(shù)會(huì)議時(shí)，幾個(gè)人可能結(jié)伴一起去聽學(xué)術(shù)報(bào)告，也可能聚集在一起討論感興趣的話題.因此，分析OffESN中多個(gè)用戶之間的鄰近關(guān)系，對(duì)進(jìn)一步揭示該類型網(wǎng)絡(luò)的特征具有重要意義.同時(shí)，由于短距離通信技術(shù)的局限，如信號(hào)不穩(wěn)定、信號(hào)遮擋及電量不足等原因，可能會(huì)導(dǎo)致一些位置鄰近關(guān)系未被探測(cè)到，預(yù)測(cè)多用戶鄰近關(guān)系可用于幫助發(fā)現(xiàn)缺失的位置鄰近關(guān)系.

鏈接預(yù)測(cè)(link prediction)是社會(huì)網(wǎng)絡(luò)分析的重要研究方向之一，最早由Liben-Nowell和Kleinberg提出[7]，其任務(wù)是利用網(wǎng)絡(luò)中的已知信息預(yù)測(cè)未來(lái)可能發(fā)生的鏈接.鏈接預(yù)測(cè)在實(shí)際應(yīng)用中具有重要意義，如推薦商品、發(fā)現(xiàn)缺失鏈接、識(shí)別錯(cuò)誤鏈接等，得到了研究者的廣泛關(guān)注.目前在線社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)取得了較多研究成果，主要有基于相似性度量[7-9]、基于分類模型[10-11]、基于概率關(guān)系模型[12-14]，基于時(shí)間序列模型[15-16]等方法.

針對(duì)OffESN的鏈接預(yù)測(cè)研究已開始得到學(xué)者們的關(guān)注.文獻(xiàn)[4]基于學(xué)術(shù)會(huì)議數(shù)據(jù)集的分析結(jié)果及社會(huì)關(guān)系理論對(duì)OffESN的特征進(jìn)行了分析，并利用因子圖模型預(yù)測(cè)用戶兩兩之間的地理巧遇.文獻(xiàn)[5]通過分析OffESN鏈接預(yù)測(cè)的影響因素，基于位置鄰近概念提出了新鄰近關(guān)系和重復(fù)鄰近關(guān)系預(yù)測(cè)策略.然而，這些方法只能預(yù)測(cè)OffESN中用戶兩兩之間的位置鄰近關(guān)系.由于OffESN缺乏用戶偏好以及用戶對(duì)事件的評(píng)論信息，文獻(xiàn)[6]提出了一種潛在網(wǎng)絡(luò)融合模型(latent network fusion)進(jìn)行用戶潛在偏好分析，通過預(yù)測(cè)用戶興趣進(jìn)行事件推薦.該模型只能預(yù)測(cè)用戶與事件之間的鏈接.

與上述預(yù)測(cè)兩兩之間是否可能產(chǎn)生鏈接不同，多用戶鄰近關(guān)系預(yù)測(cè)是預(yù)測(cè)多個(gè)用戶在未來(lái)是否可能相遇，已有鏈接預(yù)測(cè)策略不能直接應(yīng)用于多用戶鄰近關(guān)系預(yù)測(cè).就筆者所知，目前尚無(wú)文獻(xiàn)對(duì)OffESN中的多用戶鄰近關(guān)系進(jìn)行預(yù)測(cè)，其主要挑戰(zhàn)包括：

1) 如何衡量OffESN中多個(gè)用戶的緊密程度；

2) 在給定時(shí)刻，發(fā)生的多用戶鄰近關(guān)系數(shù)量及參與每個(gè)鄰近關(guān)系的用戶數(shù)量事先不確定；

3) 多用戶鄰近關(guān)系持續(xù)時(shí)間較短，且隨時(shí)間的變化而發(fā)生變化.

1 問題定義

Fig. 1 An example of multi-user location proximity.圖1 多用戶位置鄰近關(guān)系示例

定義1. 多用戶位置鄰近.在任意時(shí)間段，如果探測(cè)到N(N≥2)個(gè)用戶兩兩相遇(相互鄰近時(shí)間超過指定時(shí)間閾值)，則稱這N個(gè)用戶在該時(shí)間段發(fā)生多用戶位置鄰近.

我們將OffESN按時(shí)間段建模成不同的網(wǎng)絡(luò)片段(network fragment).

假設(shè)(時(shí)間依賴性): 若2個(gè)用戶在時(shí)刻t相遇，則他們?cè)跁r(shí)刻t+1很可能再次相遇.

ACM SIGCOMM國(guó)際學(xué)術(shù)會(huì)議于2009-08-17—2009-08-21在西班牙巴塞羅那召開.會(huì)議組織方通過藍(lán)牙設(shè)備收集了76位參會(huì)代表會(huì)議召開期間的位置鄰近數(shù)據(jù)[17].我們探測(cè)到的所有兩兩位置鄰近關(guān)系按天劃分為0～4共5個(gè)時(shí)間段.

圖2為第1～4個(gè)時(shí)間段中的鄰近關(guān)系對(duì)前一個(gè)時(shí)間段的時(shí)間依賴性.其中，Independent表示在上一個(gè)時(shí)間段未發(fā)生位置鄰近的用戶在下一個(gè)時(shí)間段發(fā)生位置鄰近的比例，Dependent表示上一個(gè)時(shí)間段發(fā)生位置鄰近的用戶在下一個(gè)時(shí)間段仍然鄰近的比例.

Fig. 2 Time dependency of location proximity.圖2 位置鄰近關(guān)系的時(shí)間依賴性

從圖2可以看出，在不同的時(shí)間段，Dependent值都高于Independent，驗(yàn)證了如果用戶在上一個(gè)時(shí)間段發(fā)生位置鄰近則他們?cè)诋?dāng)前時(shí)間段發(fā)生位置鄰近的可能性較高，即位置鄰近行為具有時(shí)間依賴性.于是，利用用戶的歷史鄰近信息，將多個(gè)連續(xù)網(wǎng)絡(luò)片段進(jìn)行疊加，形成1個(gè)保存歷史鄰近關(guān)系的完整網(wǎng)絡(luò).

Fig. 3 An example of overlay network.圖3 疊加網(wǎng)絡(luò)示例

(1)

為滿足位置鄰近關(guān)系的時(shí)間依賴特征，式(1)引入了衰減思想，以保證距離當(dāng)前時(shí)間較近的鄰近關(guān)系對(duì)疊加網(wǎng)絡(luò)的權(quán)重影響較大.

圖3為圖1的疊加網(wǎng)絡(luò)實(shí)例.由于疊加網(wǎng)絡(luò)為無(wú)向圖，故wi j=wj i.

密度(density)是用來(lái)衡量社會(huì)網(wǎng)絡(luò)中不同結(jié)點(diǎn)之間聚集程度的重要指標(biāo)之一.我們利用該指標(biāo)度量疊加網(wǎng)絡(luò)中子圖的聚集程度.

定義4. 聚集密度.若S為疊加網(wǎng)絡(luò)G中的任意一子圖，|US|和|ES|分別為S擁有的結(jié)點(diǎn)數(shù)和鏈接數(shù)，dens(S)為S的聚集密度,則有：

(2)

其中，nS=(|US|×(|US|-1))/2，表示S中的最大鏈接數(shù).

根據(jù)聚集密度，可提取疊加網(wǎng)絡(luò)中聚集程度較為緊密的最大子圖，稱之為極大緊密子圖(maximal close subgraph).

定義5. 極大緊密子圖.設(shè)ε為給定聚集密度閾值，S為G中的任意子圖且|US|≥2，若稱S為極大緊密子圖，當(dāng)且僅當(dāng)2個(gè)條件同時(shí)滿足：

1)den(S)≥ε；

2) 對(duì)于任意v∈U且v?S,e={ev u|u∈S}，den(S∪(v,e))<ε成立，即在S中加入新結(jié)點(diǎn)v及其相連的邊e后，所形成子圖的聚集密度小于ε.

因此，極大緊密子圖中包含了聚集關(guān)系較為密切的結(jié)點(diǎn).

根據(jù)觀察，在學(xué)術(shù)會(huì)議離線網(wǎng)絡(luò)中，多個(gè)用戶發(fā)生位置鄰近的可能性主要有：1)共同去參加感興趣的學(xué)術(shù)報(bào)告或分組討論；2)新舊朋友聚在一起聊天交流、喝咖啡或用餐.因此，相對(duì)于研究興趣不相同的會(huì)議代表，研究興趣相同的代表發(fā)生位置鄰近的頻率較高且時(shí)間較長(zhǎng).同樣，相對(duì)于非朋友關(guān)系的代表，具有朋友關(guān)系的代表發(fā)生位置鄰近的頻率較高且時(shí)間較長(zhǎng).因此，總體上，具有相同研究興趣的代表和具有朋友關(guān)系的代表更易于在疊加網(wǎng)絡(luò)中形成極大緊密子圖.因此，我們可推測(cè)：存在于一個(gè)極大緊密子圖的會(huì)議代表在未來(lái)發(fā)生位置鄰近的可能性較大，即可將離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中的多用戶鄰近預(yù)測(cè)問題轉(zhuǎn)化為從疊加網(wǎng)絡(luò)中挖掘極大緊密子圖問題.

本研究的預(yù)測(cè)策略為：在當(dāng)前疊加網(wǎng)絡(luò)中，屬于一個(gè)極大緊密子圖中的用戶將在下一個(gè)時(shí)間段可能發(fā)生位置鄰近.

定義6. 多用戶鄰近預(yù)測(cè).G是由n個(gè)連續(xù)網(wǎng)絡(luò)片段{g1,g2,…,gn}形成的疊加網(wǎng)絡(luò).若S為G中的極大緊密子圖，則預(yù)測(cè)S中的用戶在第n+1個(gè)網(wǎng)絡(luò)片段gn+1中將發(fā)生位置鄰近.

2 預(yù)測(cè)總體框架

根據(jù)上述定義，首先給出多用戶鄰近預(yù)測(cè)的總體框架，如圖4所示：

Fig. 4 The overall framework of multi-user proximity prediction.圖4 多用戶鄰近關(guān)系預(yù)測(cè)總體框架

從圖4可以看出，多用戶位置鄰近關(guān)系預(yù)測(cè)包括4個(gè)步驟：

步驟1. 收集網(wǎng)絡(luò)片段.首先，將短距離通信設(shè)備探測(cè)到的相遇關(guān)系按給定時(shí)間段進(jìn)行劃分；然后，對(duì)每個(gè)劃分進(jìn)行統(tǒng)計(jì)，生成網(wǎng)絡(luò)片段g1,g2,…,gn，其中每個(gè)片段包括用戶集、鄰近邊集及權(quán)重集.

步驟2. 網(wǎng)絡(luò)疊加.將g1,g2,…,gn中的用戶集和鄰近關(guān)系集進(jìn)行疊加，并按照式(1)計(jì)算每條邊的疊加權(quán)重，從而得到疊加網(wǎng)絡(luò)G.

步驟3. 網(wǎng)絡(luò)過濾.由于疊加網(wǎng)絡(luò)中存在噪聲鄰近邊，因此根據(jù)邊權(quán)重閾值過濾G中的噪聲關(guān)系.

步驟4. 極大緊密子圖發(fā)現(xiàn).對(duì)過濾后得到的每個(gè)獨(dú)立網(wǎng)絡(luò)子圖，計(jì)算其聚集密度，判斷其是否為極大緊密子圖.若是，則預(yù)測(cè)該子圖中的用戶在下一個(gè)時(shí)間片段發(fā)生位置鄰近；若不是，則對(duì)子圖進(jìn)行分裂，直到剩余結(jié)點(diǎn)為孤立結(jié)點(diǎn).

3 構(gòu)建疊加網(wǎng)絡(luò)

疊加網(wǎng)絡(luò)是進(jìn)行預(yù)測(cè)的基礎(chǔ)，在挖掘最大緊密子圖之前，需要構(gòu)建疊加網(wǎng)絡(luò).

OffESN中的位置鄰近信息隨著時(shí)間的增長(zhǎng)不斷增加.在預(yù)測(cè)開始時(shí)，我們選取前n個(gè)網(wǎng)絡(luò)片段進(jìn)行疊加網(wǎng)絡(luò)初始化.初始化過程如算法1所示：

算法1. 疊加網(wǎng)絡(luò)初始化.

輸入：{g1,g2,…,gn};

輸出：疊加網(wǎng)絡(luò)G=(U,E,W).

①k=1;

②U=?，E=?;

③ for eachuiinUk(k=1,2,…,n)

④U=ui∪U; /*合并結(jié)點(diǎn)集*/

⑤ end for

⑥ for eachei jinEk(k=1,2,…,n)

⑦E=ei j∪E; /*合并邊集*/

⑧ end for

⑨ for eachei j∈Edo

⑩ setwi j=0; /*初始化邊的權(quán)重*/

衰減公式計(jì)算*/

初始化之后，每次只需將新時(shí)間片段產(chǎn)生的邊及結(jié)點(diǎn)添加到疊加網(wǎng)絡(luò)中，同時(shí)更新邊的權(quán)重，以獲得最新疊加網(wǎng)絡(luò).

4 極大緊密子圖發(fā)現(xiàn)

本研究擬通過發(fā)現(xiàn)極大緊密子圖來(lái)判斷網(wǎng)絡(luò)中多用戶是否位置鄰近.但是，由于事先無(wú)法知道不同時(shí)刻疊加網(wǎng)絡(luò)中極大緊密子圖數(shù)量及每個(gè)子圖中的用戶數(shù)量，因此擬采用基于分裂的思想發(fā)現(xiàn)極大緊密子圖.

GN算法[18]是一種分裂型的社區(qū)發(fā)現(xiàn)算法.該算法根據(jù)網(wǎng)絡(luò)中社區(qū)內(nèi)部高內(nèi)聚、社區(qū)之間低內(nèi)聚的特點(diǎn)，逐步去除社區(qū)之間的邊，以得到相對(duì)內(nèi)聚的社區(qū)結(jié)構(gòu).該算法按邊介數(shù)大小隨機(jī)刪除邊進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)分裂，無(wú)需在執(zhí)行算法之前指定子圖目標(biāo)個(gè)數(shù)及規(guī)模.但是，利用GN算法不能直接用于極大緊密子圖提取，其原因主要有：

1) GN算法是為靜態(tài)無(wú)權(quán)圖設(shè)計(jì)，它是將邊介數(shù)作為網(wǎng)絡(luò)分裂的依據(jù)，而未考慮邊的權(quán)重、圖的結(jié)構(gòu)和權(quán)重的動(dòng)態(tài)變化；

2) 該算法是為社區(qū)發(fā)現(xiàn)而設(shè)計(jì)，網(wǎng)絡(luò)分裂終止條件為社區(qū)模塊度Q，未考慮離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中疊加網(wǎng)絡(luò)特征.

針對(duì)以上問題及OffESN特征，我們?cè)谶M(jìn)行網(wǎng)絡(luò)分裂時(shí)做了3點(diǎn)擴(kuò)充：

1) 為支持OffESN的動(dòng)態(tài)特征，實(shí)時(shí)更新疊加網(wǎng)絡(luò)中的結(jié)點(diǎn)、邊及權(quán)重；

2) 利用加權(quán)邊介數(shù)代替邊介數(shù)作為網(wǎng)絡(luò)分裂的依據(jù)，即每次選取加權(quán)邊介數(shù)最大的邊刪除；

3) 利用聚集密度作為網(wǎng)絡(luò)分裂的終止條件，即當(dāng)分裂子圖的聚集密度大于閾值時(shí)停止分裂.

4.1 加權(quán)邊介數(shù)

邊介數(shù)(edge betweenness,EB)是用來(lái)衡量邊在網(wǎng)絡(luò)中重要性程度的度量指標(biāo)，它表示網(wǎng)絡(luò)中所有最短路徑中經(jīng)過一條邊的路徑數(shù)目占最短路徑總數(shù)的比例.邊介數(shù)值較高的邊，它們最有可能占據(jù)連接不同子網(wǎng)絡(luò)的“橋”位置[18].例如，圖3中邊e26具有較高的邊介數(shù)，因?yàn)樗B接了分別由用戶1～5和用戶6～9組成的2個(gè)子網(wǎng)絡(luò).

定義7. 邊介數(shù).邊介數(shù)為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過一條邊的路徑數(shù)量占全部最短路徑數(shù)量的比例.設(shè)EB(ei j)為邊ei j的邊介數(shù)，其計(jì)算為

(3)

其中，σ(s,t)為從結(jié)點(diǎn)s到結(jié)點(diǎn)t的最短路徑數(shù)量，σ(s,t|ei j)為從結(jié)點(diǎn)s到結(jié)點(diǎn)t經(jīng)過邊ei j的最短路徑數(shù).

由于疊加網(wǎng)絡(luò)中的鄰近關(guān)系具有權(quán)重，故其為無(wú)向有權(quán)圖.為保證重要的邊(具有較高權(quán)重的邊)不被輕易刪除，于是提出加權(quán)邊介數(shù)(weighted edge betweenness,WEB)概念.

定義8. 加權(quán)邊介數(shù).加權(quán)邊介數(shù)為一條邊的邊介數(shù)與該邊權(quán)重的比值.設(shè)WEB(ei j)為ei j的加權(quán)邊介數(shù)，其計(jì)算為

(4)

4.2 極大緊密子圖發(fā)現(xiàn)算法

由于短距離通信技術(shù)的不穩(wěn)定性，可能存在噪聲數(shù)據(jù)，故在進(jìn)行挖掘極大緊密子圖之前，需先去除疊加網(wǎng)絡(luò)中權(quán)重小于指定閾值的邊，然后再進(jìn)行分裂.算法2是極大緊密子圖發(fā)現(xiàn)算法描述.

算法2. 極大緊密子圖發(fā)現(xiàn)算法.

輸入：疊加網(wǎng)絡(luò)G=(U,E,W)、邊權(quán)重閾值θ.

① for eachei jinEdo /*網(wǎng)絡(luò)過濾*/

② ifwi j<θ

③delete(ei j,G); /*刪除權(quán)重小于權(quán)重閾值θ的邊*/

④ end if

⑤ end for

⑥split(G). /*網(wǎng)絡(luò)分裂*/

網(wǎng)絡(luò)分裂函數(shù)split(G)是極大緊密子圖發(fā)現(xiàn)算法的核心.當(dāng)網(wǎng)絡(luò)聚集密度小于閾值ε時(shí)，則去除加權(quán)邊介數(shù)最大的邊，將網(wǎng)絡(luò)分裂為2個(gè)子網(wǎng)絡(luò).當(dāng)網(wǎng)絡(luò)只有1個(gè)結(jié)點(diǎn)或其聚集密度大于閾值ε時(shí)，則停止分裂.算法3為網(wǎng)絡(luò)分裂算法.

算法3. 網(wǎng)絡(luò)分裂算法split(G).

輸入：待分裂的網(wǎng)絡(luò)G=(U,E,W)；

輸出：極大緊密子圖集合.

① if |U|=1

②remove(G)；

③ end if

④dens(G)=|EG|/nG; /*計(jì)算G的聚集密度*/

⑤ ifdens(G)>ε

⑥ returnG；

⑦ else

⑧ for eachei jinEdo

⑩ end for

極大緊密子圖發(fā)現(xiàn)算法的核心是計(jì)算邊的加權(quán)邊介數(shù).設(shè)圖中結(jié)點(diǎn)數(shù)為n，邊數(shù)為m，則計(jì)算單條邊加權(quán)邊介數(shù)的時(shí)間復(fù)雜度為O(mn).因此，在最差情況下，對(duì)于具有m條邊的圖而言，極大緊密子圖發(fā)現(xiàn)算法的時(shí)間復(fù)雜度為O(m2n).

5 實(shí)驗(yàn)及結(jié)果分析

5.1 實(shí)驗(yàn)準(zhǔn)備

本實(shí)驗(yàn)采用的2個(gè)數(shù)據(jù)集sigcomm 2009[17]和mobility 2011[19]均來(lái)自CRAWDAD網(wǎng)站.我們分別從這2個(gè)數(shù)據(jù)集中提取12 153和1 339條鄰近關(guān)系記錄.2個(gè)數(shù)據(jù)集均以天為時(shí)間段進(jìn)行網(wǎng)絡(luò)片段劃分，并以位置鄰近的頻率數(shù)作為邊權(quán)重.

本實(shí)驗(yàn)所選擇的性能評(píng)價(jià)指標(biāo)為預(yù)測(cè)準(zhǔn)確率(precision rate,PR)和召回率(recall rate,RR).設(shè)X為預(yù)測(cè)的多用戶鄰近關(guān)系數(shù)，Y為在第n+1個(gè)網(wǎng)絡(luò)片段中實(shí)際多用戶鄰近關(guān)系數(shù)，Z為X中實(shí)際包含的多用戶鄰近關(guān)系數(shù)，則有：PR=ZX；RR=ZY.

本文所提出的多用戶鄰近關(guān)系預(yù)測(cè)策略(記為MPP)是基于分裂思想進(jìn)行極大緊密子圖提取.由于尚未見離線瞬態(tài)社會(huì)網(wǎng)絡(luò)多用戶鄰近預(yù)測(cè)算法，故擬選擇采用相似的分裂思想進(jìn)行社區(qū)發(fā)現(xiàn)的GN算法及Radicchi算法[20]進(jìn)行比較.與GN算法不同的是，Radicchi算法引入了邊聚集系數(shù)進(jìn)行網(wǎng)絡(luò)分裂，減低了算法的時(shí)間復(fù)雜度，但當(dāng)網(wǎng)絡(luò)中三角環(huán)數(shù)量較少時(shí)準(zhǔn)確率會(huì)下降.對(duì)于社區(qū)發(fā)現(xiàn)算法，我們預(yù)測(cè)位于相同社區(qū)中的多個(gè)用戶在下一個(gè)時(shí)刻可能相遇.

本實(shí)驗(yàn)的硬件環(huán)境為處理器Intel?Xeon?CPU E5645@2.40 GHz、內(nèi)存4 GB，操作系統(tǒng)為Windows 7.

Fig. 5 Influence of the weight threshold on precision rates.圖5 權(quán)重閾值對(duì)準(zhǔn)確率的影響

5.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)1. 邊權(quán)重閾值對(duì)準(zhǔn)確率和召回率的影響.

圖5顯示了不同邊權(quán)重閾值θ下(固定ε=0.6)多用戶鄰近關(guān)系預(yù)測(cè)結(jié)果.可以看出，當(dāng)邊權(quán)重閾值較小時(shí)，2個(gè)數(shù)據(jù)集精確度都不高.從sigcomm 2009數(shù)據(jù)集的結(jié)果可以看出，當(dāng)θ從0.04增加到0.10時(shí)，準(zhǔn)確率略微上升后基本保持不變；當(dāng)θ從0.06增加到0.10時(shí)，mobility 2011數(shù)據(jù)集的精確度整體變化不大.圖6為召回率變化情況，總體趨勢(shì)與圖5相同.

Fig. 6 Influence of the weight threshold on recall rates.圖6 權(quán)重閾值對(duì)召回率的影響

實(shí)驗(yàn)2. 聚集密度閾值對(duì)準(zhǔn)確率和召回率的影響.

圖7和圖8展示了在不同聚集密度閾值ε下(固定θ=0.06)預(yù)測(cè)準(zhǔn)確率和召回率的變化情況.

Fig. 7 Influence of the density threshold on precision rates.圖7 聚集密度閾值對(duì)準(zhǔn)確率的影響

Fig. 8 Influence of the density threshold on recall rates.圖8 聚集密度閾值對(duì)召回率的影響

從圖7和圖8可以看出，當(dāng)ε從0.4變化到0.6時(shí)，2個(gè)數(shù)據(jù)集的準(zhǔn)確率和召回率都呈上升趨勢(shì);而當(dāng)ε達(dá)到 0.6時(shí)，2個(gè)指標(biāo)的變化不大.這是由于當(dāng)ε較大時(shí)，極大緊密子圖規(guī)模相對(duì)較小，指標(biāo)值變化相對(duì)固定.

實(shí)驗(yàn)3. 加權(quán)邊介數(shù)對(duì)準(zhǔn)確率和召回率的影響.

圖9和圖10展示了固定θ=0.06，ε=0.6時(shí)，分別利用加權(quán)邊介數(shù)(WEB)和普通邊介數(shù)(EB)作為分裂依據(jù)時(shí)的準(zhǔn)確率和召回率比較.可以看出，采用加權(quán)邊介數(shù)的準(zhǔn)確率和召回率均高于采用普通邊介數(shù)的準(zhǔn)確率和召回率，其原因是加權(quán)邊介數(shù)考慮了邊的權(quán)重，避免了鄰近關(guān)系較為緊密的邊被刪除.

Fig. 9 Influence of edge betweennesses on precision >rates.圖9 邊介數(shù)對(duì)準(zhǔn)確率的影響

Fig. 10 Influence of edge betweennesses on recall rates.圖10 邊介數(shù)對(duì)召回率的影響

Fig. 11 Precision rate comparison of different algorithms.圖11 不同算法準(zhǔn)確率比較

實(shí)驗(yàn)4. 比較不同算法對(duì)準(zhǔn)確率和召回率的影響.

圖11和圖12分別是3種算法預(yù)測(cè)的準(zhǔn)確率和召回率的比較結(jié)果，其中固定θ=0.06，ε=0.6.

Fig. 12 Recall rate comparison of different algorithms.圖12 不同算法召回率比較

可以看出，MPP算法的準(zhǔn)確率和召回率都高于GN算法和Radicchi算法.在學(xué)術(shù)會(huì)議的離線網(wǎng)絡(luò)中，每次同時(shí)發(fā)生位置鄰近的用戶數(shù)通常不多(常常幾個(gè)人碰面在一起交流和討論)；而社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)的社區(qū)規(guī)模往往較大，不易發(fā)現(xiàn)規(guī)模比較小的多用戶位置鄰近，故它們的準(zhǔn)確率和召回率都比MPP算法低.

實(shí)驗(yàn)5. 分析不同算法的挖掘時(shí)間開銷.

圖13是3種算法的挖掘時(shí)間開銷比較結(jié)果.可以看出，MPP算法所需時(shí)間開銷小于GN算法，其原因是GN算法計(jì)算分裂終止判斷條件——模塊度的時(shí)間開銷高于MPP算法計(jì)算聚集密度的開銷.但是，由于Radicchi算法只需計(jì)算局部邊聚集系數(shù)作為分裂條件，故其所需時(shí)間最少.

Fig. 13 Time overhead comparison of different algorithms.圖13 不同算法的時(shí)間開銷比較

6 結(jié) 論

本文針對(duì)離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中的多用戶鄰近關(guān)系預(yù)測(cè)問題展開研究，主要?jiǎng)?chuàng)新之處在于考慮了離線瞬態(tài)社會(huì)網(wǎng)絡(luò)特征，提出了極大緊密子圖概念及其挖掘策略，能有效地解決多鄰近關(guān)系數(shù)及規(guī)模不確定問題.全文主要工作總結(jié)如下：

1) 設(shè)計(jì)了離線瞬態(tài)社會(huì)網(wǎng)絡(luò)中多用戶鄰近關(guān)系預(yù)測(cè)的總體框架；

2) 考慮到用戶鄰近關(guān)系的強(qiáng)度不同，提出了采用加權(quán)邊介數(shù)作為網(wǎng)絡(luò)分裂依據(jù)，以避免重要邊不被刪除；

3) 提出了基于分裂思想的極大緊密子圖提取算法；

4) 在真實(shí)數(shù)據(jù)集上進(jìn)行了性能測(cè)試，測(cè)試結(jié)果驗(yàn)證了所提出算法的可行性.

在后續(xù)的研究中，我們將進(jìn)一步研究離線瞬態(tài)社會(huì)網(wǎng)絡(luò)的特征，以期發(fā)現(xiàn)更多特征指標(biāo)及更有效的算法幫助提高預(yù)測(cè)的準(zhǔn)確率.

[1]Kong Xiangnan, Zhang Jiawei, Yu P S. Inferring anchor links across multiple heterogeneous social networks[C] //Proc of the 22nd ACM Int Conf on Information & Knowledge Management (CIKM 2013). New York: ACM, 2013: 179-188

[2]Chin A, Wang Hao, Xu Bin, et al. Connecting people in the workplace through ephemeral social networks[C] //Proc of the 3rd IEEE Int Conf on Privacy, Security, Risk and Trust and Social Computing. Piscataway, NJ: IEEE, 2011: 527-530

[3]Chin A, Zhang Daqing. Ephemeral social networks[M] //Mobile Social Networking. Berlin: Springer, 2014: 25-64

[4]Zhuang Honglei, Chin A, Wu Sen, et al. Inferring geographic coincidence in ephemeral social networks[M] //Machine Learning and Knowledge Discovery in Databases. Berlin: Springer, 2012: 613-628

[5]Scholz C, Atzmueller M, Stumme G. On the predictability of human contacts: Influence factors and the strength of stronger ties[C] //Proc of the 4th IEEE Int Conf on Privacy, Security, Risk and Trust and Social Computing. Piscataway, NJ: IEEE, 2012: 312-321

[6]Liao Guoqiong, Zhao Yuchen, Xie Sihong, et al. An effective latent networks fusion based model for event recommendation in offline ephemeral social networks[C] //Proc of the 22nd ACM Int Conf on Information & Knowledge Management(CIKM 2013). New York: ACM, 2013: 1655-1660

[7]Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031

[8]Lichtenwalter R N, Lussier J T, Chawla N V. New perspectives and methods in link prediction[C] //Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining (KDD 2010). New York: ACM, 2010: 243-252

[9]Bliss C A, Frank M R, Danforth C M, et al. An evolutionary algorithm approach to link prediction in dynamic social networks[J]. Journal of Computational Science, 2014, 5(5): 750-764

[10]Hasan M A, Chaoji V, Salem S, et al. Link prediction using supervised learning[C] //Proc of the 6th SIAM Int Conf on Data Mining: Workshop on Link Analysis, Counter-terrorism and Security. Philadelphia, PA: SIAM, 2006: 531-540

[11]Benchettara N, Kanawati R, Rouveirol C. Supervised machine learning applied to link prediction in bipartite social networks[C] //Proc of 2010 IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining. Los Alamitos, CA: IEEE Computer Society, 2010: 326-330

[12]Wang Chao, Satuluri V, Parthasarathy S. Local probabilistic models for link prediction[C] //Proc of the 7th IEEE Int Conf on Data Mining (ICDM 2007). Los Alamitos, CA: IEEE Computer Society, 2007: 322-331

[13]Kashima H, Abe N. A parameterized probabilistic model of network evolution for supervised link prediction[C] //Proc of the 6th IEEE Int Conf on Data Mining (ICDM 2006). Los Alamitos, CA: IEEE Computer Society, 2006: 340-349

[14]Lü Linyuan. Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(5): 651-661 (in Chinese)

(呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)[J]. 電子科技大學(xué)學(xué)報(bào), 2010, 39(5): 651-661)

[15]Huang Zan, Lin D K J. The time-series link prediction problem with applications in communication surveillance[J]. INFORMS Journal on Computing, 2009, 21(2): 286-303

[16]Silva Soares da P R, Cavalcante Prudencio R B. Time series based link prediction[C] //Proc of the 6th Int Joint Conf on Neural Networks. Piscataway, NJ: IEEE, 2012: 1-7

[17]Pietilainen A K, Diot C. The thlab/sigcomm2009 dataset[EB/OL]. (2012-07-15)[2015-02-20]. https://crawdad.cs.dartmouth.edu/thlab/sigcomm2009/20120715

[18]Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826

[19]Ciobanu R I, Dobre C. The upb/mobility2011 dataset[EB/OL]. (2012-06-18)[2015-02-20]. http://www.crawdad.org/upb/mobility2011 /20120618

[20]Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences, 2004, 101(9): 2658-2663

Liao Guoqiong, born in 1969. PhD. Professor at the School of Information Technology, Jiangxi University of Finance and Economics. Senior member of China Computer Federation. His main research interests include database, data mining and social networks.

Wang Tingli, born in 1990. Master from the School of Information Technology, Jiangxi University of Finance and Economics. Her main research interests include data mining and social networks.

Deng Kun, born in 1980. PhD candidate at the School of Information Technology, Jiangxi University of Finance and Economics. His main research interests include data mining and social networks.

Wan Changxuan, born in 1962. PhD. Professor and PhD supervisor at the School of Information Technology, Jiangxi University of Finance and Economics. Senior member of China Computer Federation. His main research interests include Web data management and Web information retrieval.

Multi-User Location Proximity Prediction in Offline Ephemeral Social Networks

Liao Guoqiong1,2, Wang Tingli1, Deng Kun1,2, and Wan Changxuan1,2

1(SchoolofInformationTechnology,JiangxiUniversityofFinanceandEconomics,Nanchang330013)2(JiangxiProvinceKeyLaboratoryofDataandKnowledgeEngineering(JiangxiUniversityofFinanceandEconomics),Nanchang330013)

Offline ephemeral social network (OffESN) is defined as a new kind of offline social networks created at a specific location for a specific purpose temporally, and lasting for a short period of time. With the popularity of mobile intelligent terminals and the development of short distance communication technologies such as Bluetooth and RFID, the OffESN is receiving more and more attentions from industry and academic communities. Location proximity relations are encounter relations of the users in the OffESN. Aiming to the characteristics such as dynamic change and short duration time, this paper intends to study the problem of multi-user location proximity in the OffESN. First of all, the paper puts forward relevant concepts in the OffESN and defines the problem to be solved. Then, it designs the overall framework of multi-user location proximity prediction, including network segments collection, overlay networks construction, network filter and maximal close subgraphs discovery. Based on the framework and the splitting idea, the paper suggests a maximal close subgraph discovery algorithm for predicting multi-user location proximity. The algorithm uses weighted edge betweenness (WEB) as the basis of splitting, and uses the aggregate density as the termination condition of spitting, which can effectively solve the problem that both numbers of location proximity relations and the users in each location proximity are uncertain. Finally, the experiments on two real datasets verify the feasibility and efficiency of the suggested prediction strategy.

social networks; ephemeral social networks; location proximity; maximal close subgraphs; link prediction

2015-05-21；

2016-02-16

國(guó)家自然科學(xué)基金項(xiàng)目(61262009)；江西省自然科學(xué)基金項(xiàng)目(20151122040083)；江西省優(yōu)勢(shì)科技創(chuàng)新團(tuán)隊(duì)建設(shè)計(jì)劃項(xiàng)目(20113BCB24008)

TP18

This work was supported by the National Natural Science Foundation of China (61262009), the Natural Science Foundation of Jiangxi Province (20151122040083), and the Jiangxi Foundation of Superiority Science and Technology Innovation Team Building Program (20113BCB24008).