宗傳玉 李箬竹 夏秀峰

摘 要：針對當(dāng)前社區(qū)搜索問題不能完全滿足用戶活動位置推薦的需求，提出了屬性地理社會社區(qū)搜索問題（AGCS）。該問題是從帶有屬性的基于位置的社交網(wǎng)絡(luò)中尋找緊密連接的用戶社區(qū)和屬性位置簇的工作。定義一個基于屬性約束和簽到信息的新社區(qū)度量用以衡量結(jié)果質(zhì)量，并提出三種新的搜索算法來解決該問題：一種基本算法，一種基于貪心擴(kuò)展策略的局部算法以及優(yōu)化的局部算法。實驗證明提出的算法能夠在帶有屬性的基于位置的社交網(wǎng)絡(luò)中有效地搜索高質(zhì)量的用戶社區(qū)和屬性位置簇，局部算法社區(qū)分?jǐn)?shù)較基本算法增加近1.5倍，優(yōu)化的局部算法在保證社區(qū)質(zhì)量的基礎(chǔ)上將算法效率提升到原來的近40倍。

關(guān)鍵詞：社區(qū)搜索； 用戶社區(qū)； 屬性位置簇

中圖分類號：TP301.6?? 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2023）09-015-0000-00

doi：10.19734/j.issn.1001-3695.2023.01.0019

User community and attribute location cluster search in

location-based social networks

Zong Chuanyu， Li Ruozhu， Xia Xiufeng

（School of Computer Science， Shenyang Aerospace University， Shenyang Liaoning 110136， China）

Abstract：This paper proposed the attribute geosocial community search problem （AGCS） to address the current community search problem that does not fully satisfy the need for user activity location recommendations. This problem was the work to find closely connected user community and attribute location cluster from location-based social networks with attributes. It defined a new community metric based on attribute constraints and check-in information to measure the quality of results， and proposed three new search algorithms to solve the problem： a basic algorithm， a local algorithm based on a greedy expansion strategy， and an optimized local algorithm. Experiments demonstrate that the proposed algorithms can effectively search user community and attribute location cluster in location-based social networks with attributes. The community score of local algorithm results is nearly 1.5 times higher than that of basic algorithm， and the efficiency of optimization algorithm is improved to nearly 40 times on the basis of ensuring community quality.

Key words：community search; user community; location cluster with attribute

0 引言

社區(qū)是一個內(nèi)部緊密連接、外部稀疏連接的子圖。在圖中搜索社區(qū)是許多圖分析應(yīng)用程序中的基本問題。社區(qū)搜索旨在圖中搜索與一組查詢節(jié)點和一些查詢約束相關(guān)的社區(qū)［1，2］。從網(wǎng)絡(luò)中檢索社區(qū)可以用來組織活動，推薦用戶可能認(rèn)識的人等［3］。

隨著數(shù)據(jù)種類的增加和用戶需求的變化，僅以用戶關(guān)系為搜索條件的社區(qū)搜索已不能完全滿足社區(qū)搜索的需求。屬性社區(qū)搜索是在常規(guī)社區(qū)搜索的基礎(chǔ)上，通過向用戶關(guān)系添加屬性約束，使得可以搜索同時滿足用戶關(guān)系結(jié)構(gòu)和關(guān)鍵字內(nèi)聚性的屬性社區(qū)。然而，單純地添加屬性約束的社區(qū)搜索可能返回一個具有大范圍空間位置的社區(qū)。

隨著基于位置的社交網(wǎng)絡(luò)的出現(xiàn)，社區(qū)搜索不再局限于以用戶之間的密切關(guān)系為搜索標(biāo)準(zhǔn)，還可以在用戶關(guān)系的基礎(chǔ)上添加位置條件?，F(xiàn)有大多數(shù)包含有位置約束的社區(qū)搜索只產(chǎn)生了單個用戶社區(qū)，很少有研究在與用戶社區(qū)對應(yīng)的基于位置的社交網(wǎng)絡(luò)位置上探討用戶社區(qū)和位置簇的搜索問題，因此，基于位置的社交網(wǎng)絡(luò)上的社區(qū)搜索出現(xiàn)了。Kim等人［4］提出的地理社會社區(qū)搜索（GCS）要求搜索到的社區(qū)網(wǎng)絡(luò)和位置簇不僅與用戶關(guān)系密切，而且在地理上也緊密相連。在基于位置的社交網(wǎng)絡(luò)中搜索社區(qū)會產(chǎn)生一個用戶社區(qū)和一個位置簇，簇中包含與用戶社區(qū)對應(yīng)的所有位置。

單一的屬性約束或位置約束并不能完全滿足所有用戶的需求。本文結(jié)合兩者共同作為社區(qū)搜索的約束條件，以獲得在合理空間范圍內(nèi)的理想社區(qū)。為了獲得同時滿足屬性和位置約束的社區(qū)，需要在帶有屬性的基于位置的社交網(wǎng)絡(luò)上同時對位置和屬性進(jìn)行約束。所以本文提出了屬性地理社會社區(qū)搜索（AGCS）問題，AGCS要求在帶有屬性的基于位置的社交網(wǎng)絡(luò)中尋找一個緊密連接的用戶社區(qū)和一個與用戶社區(qū)緊密連接的屬性位置簇。

圖1表示一個帶有屬性的基于位置的社交網(wǎng)絡(luò)，它包含用戶網(wǎng)絡(luò)、具有屬性的位置節(jié)點集和簽到信息。用戶網(wǎng)絡(luò)中的每個節(jié)點代表一個用戶，位置節(jié)點集中的每個節(jié)點表示用戶可能訪問的位置，兩者之間的邊表示用戶曾到達(dá)過該位置，ai表示位置li的屬性/關(guān)鍵字。假設(shè)圖1中的用戶u11想去看電影，他需要一些關(guān)于電影院以及同行人的推薦，這時可以使用AGCS，找到一個用戶社區(qū)和一個具有指定屬性“電影”的空間位置簇。

本文的主要貢獻(xiàn)如下：a）基于屬性約束和簽到信息，定義了一種新的社區(qū)度量。b）提出了在帶有屬性的基于位置的社交網(wǎng)絡(luò)上的屬性地理社會社區(qū)搜索（AGCS）問題。據(jù)調(diào)查，這是第一個找到具有高社區(qū)度量的一個用戶社區(qū)和一個滿足屬性約束的空間位置簇的工作。c）提出基本算法得到屬性地理社會社區(qū)搜索（AGCS）問題的近似解，在基本算法的基礎(chǔ)上提出了局部算法提高了結(jié)果社區(qū)的質(zhì)量。d）提出了優(yōu)化的局部擴(kuò)展算法，在保證了社區(qū)質(zhì)量的基礎(chǔ)上，算法的效率平均提高了近40倍。e）在真實數(shù)據(jù)集和合成數(shù)據(jù)集上進(jìn)行了大量的實驗，結(jié)果表明，本文提出的算法可以有效地在帶有屬性的基于位置的社交網(wǎng)絡(luò)中搜索用戶社區(qū)和屬性位置簇。

1 相關(guān)工作

在基于結(jié)構(gòu)約束的社區(qū)搜索的基礎(chǔ)上，還有以下幾種搜索條件下的研究：

基于地理位置約束的社區(qū)搜索研究，Zhu等人［5］提出了一組滿足最小認(rèn)知約束的地理社會集群查詢（GSGQs），以在LBSN上生成一個有凝聚力的群體。Wang等人［6］提出了一個包含地理半徑約束的社區(qū)搜索問題，在一個基于位置的社會網(wǎng)絡(luò)上尋找一組空間鄰近的群體。

基于屬性約束的社區(qū)搜索研究，F(xiàn)ang等人［7］提出了屬性社區(qū)查詢（ACQ），得到了基于關(guān)鍵字內(nèi)聚性的屬性社區(qū)（AC）。Zhang等人［8］在屬性圖上研究了以關(guān)鍵字為中心的社區(qū)搜索（KCCS），提出了一種不輸入查詢節(jié)點只用查詢關(guān)鍵字來搜索社區(qū)的方法。Chen等人［9］基于屬性社區(qū)搜索提出的無參數(shù)上下文社區(qū)模型只需要一組描述與期望匹配的社區(qū)上下文關(guān)鍵字，就可以返回滿足約束的社區(qū)。Liu等人［10］提出了一個以頂點為中心的屬性社區(qū)（VAC）問題來解決屬性設(shè)置困難和單一查詢屬性類型的問題。Apon等人［11］提出了基于社會和空間文本的靈活的top-k社會空間關(guān)鍵字感知組查詢（SSKGQ）問題。文獻(xiàn)［12］設(shè)計了屬性網(wǎng)絡(luò)中結(jié)合用戶偏好的社區(qū)搜索和離群點檢測方法。

同時基于位置和屬性的社區(qū)搜索的研究，Guo等人［13］提出了多屬性社區(qū)（MAC）搜索，并研究了兩種有效計算top-j多屬性社區(qū)的方法。Chen等人［14］提出了共定位社區(qū)搜索（LCD）問題，其得到的社區(qū)滿足k-truss約束和用戶的空間位置約束。Chen等人［15］還提出了地理社會群體搜索問題，來獲得一個與某一地點相近并且社會關(guān)系密切的一群人，并提出MKCSSG模型，在找到最佳的社區(qū)結(jié)果的同時縮小了搜索空間。文獻(xiàn)［16］提出了異質(zhì)網(wǎng)絡(luò)中基于元路徑P和元結(jié)構(gòu)S的P-距離和S-距離及（k，d，P）-truss和（k，d，S）-truss社區(qū)模型以度量子圖的結(jié)構(gòu)內(nèi)聚性，同時提出了關(guān)鍵詞屬性得分函數(shù)用于度量不同子圖的關(guān)鍵詞屬性相關(guān)性。

在當(dāng)前的社區(qū)搜索研究中，同時基于位置和屬性的社區(qū)搜索只考慮了用戶的需求，返回的結(jié)果只包含獨立的用戶社區(qū)，不能完全滿足用戶活動位置推薦的需求。基于位置的社交網(wǎng)絡(luò)上的社區(qū)搜索［4］的出現(xiàn)為用戶提供了一組緊密聯(lián)系的用戶社區(qū)和位置簇，但當(dāng)用戶對推薦的活動位置有屬性需求，例如用戶希望推薦的位置可以用來舉行一個生日聚會，已有的工作返回的結(jié)果會包含大量與“生日聚會”無關(guān)的位置，不能完全滿足用戶的需求。基于以上情況，本文在帶有屬性的基于位置的社交網(wǎng)絡(luò)上進(jìn)行了基于位置和屬性的社區(qū)搜索的研究，返回同時滿足內(nèi)聚性約束、空間約束和屬性覆蓋率的一組具有高訪問次數(shù)的用戶社區(qū)和屬性位置簇。

2 屬性地理社會社區(qū)搜索

帶有屬性的基于位置的社交網(wǎng)絡(luò)（location-based social network with attributes，LBSNA）：給定一個無向圖G=（V，E），G表示由一組節(jié)點V和一組邊EV×V組成的社交網(wǎng)絡(luò)。VH是V中節(jié)點的子集，H=（VH，EH）表示由VH誘導(dǎo)的G的子圖。簽到圖由一個二分圖GC=（VU，VL，EC）表示，其中VU是一組用戶節(jié)點，VL={（li，A（li））}是一組具有A（li）={a1，a2，a3，…，aj}屬性標(biāo)簽的位置點，（u，l）∈EC是一條簽到邊，代表用戶u到位置l的簽到，W（u，l）∈R表示邊（u，l）∈EC的權(quán)重。簽到權(quán)重W可以用來表示用戶到位置的簽到頻率。LBSNA表示為N=（GU，VL，GC），該網(wǎng)絡(luò)由一個社交網(wǎng)絡(luò)GU、一組帶有屬性標(biāo)簽的位置節(jié)點集VL和一個簽到圖GC組成。

社區(qū)通常是一個滿足結(jié)構(gòu)內(nèi)聚性的子圖，結(jié)構(gòu)內(nèi)聚性是對社區(qū)聯(lián)系緊密程度的度量，有k-core、k-truss和k-clique等［1］。盡管本文方法可以簡單地拓展到別的結(jié)構(gòu)，但在本文中使用k-core作為結(jié)構(gòu)內(nèi)聚性的度量［17］。定義deg（v）為直接連接到節(jié)點v的節(jié)點數(shù)，即節(jié)點v的鄰居數(shù)，deg（v）也被稱為一個節(jié)點的度。此外，給定一個子圖H=（VH，EH），δ（H）返回節(jié)點v∈VH的最小度。k-core的定義如下。

定義1 k-Core。給定正整數(shù)k，當(dāng)圖的子圖Hk滿足v∈Hk，δ（Hk）≥k，并且Hk連通時，稱Hk是一個k-core。

如圖2所示，節(jié)點{u1，u2，u3，u4，u5，u6，u10，u11，u12}誘導(dǎo)的子圖為一個2-core，由{u3，u4，u5，u6，u10，u11，u12}誘導(dǎo)的子圖為一個3-core。

定義2 用戶社區(qū)（user community）。給定一個社交網(wǎng)絡(luò)GU，和一個度閾值k，用戶社區(qū)HU=（VHU，EHU）是圖GU的一個連通子圖，滿足度約束k，即v∈VHU，deg（v）≥k。

定義3 距離可達(dá)（distance reachable）。給定位置節(jié)點集VL中的兩個位置節(jié)點li和lj，距離閾值r，假設(shè)i=1，j=n。若存在節(jié)點集{l1，l2，l3，…，ln}∈VL，任意節(jié)點集中節(jié)點lx和lx+1之間的距離dis（lx，lx+1）≤r（dis（lx，lx+1）表示lx到lx+1之間的距離），則稱li和lj距離可達(dá)。

定義4 屬性位置簇（attribute location cluster）。給定一個位置節(jié)點集VL，一個距離閾值r，一個查詢屬性集AQ={a1，a2，…，an}和一個度閾值k。如果滿足以下條件，則一組位置點LAC構(gòu)成位置簇。

a）li，lj∈LAC，li和lj是距離可達(dá)的；

b）li∈LAC，AQA（li）；

c）LAC按半徑r約束生成的位置網(wǎng)絡(luò)滿足k-core。

基于屬性位置簇的性質(zhì)，需要從屬性位置網(wǎng)絡(luò)中獲取屬性位置簇。通過為滿足屬性約束并且距離小于等于半徑約束的點創(chuàng)建邊，可以得到屬性位置網(wǎng)絡(luò)。

圖3（a）所示是一個屬性位置節(jié)點集，由l1～l18共18個帶有不同屬性標(biāo)簽的位置節(jié)點組成。圖3（b）為圖3（a）中的位置節(jié)點以r=0.5為半徑劃分并創(chuàng)建的屬性位置網(wǎng)絡(luò)?？梢钥闯?，基于位置節(jié)點集和半徑閾值r構(gòu)造的位置網(wǎng)絡(luò)包含{l1，l2，l3，l4，l5，l6，l7}、{l8，l9，l10，l11，l12}和{l14，l15，l16，l17，l28}三個連通分量，連通分量中的任意兩個節(jié)點都是距離可達(dá)的。在距離閾值r=0.5和度閾值k=2約束下，可以得到位置網(wǎng)絡(luò){l8，l9，l10，l11，l12}和{l14，l15，l16，l17，l28}，如圖3（c）。節(jié)點{l14，l15，l16，l17，l28}的集合滿足AQ={a1，a5}屬性約束，該集合構(gòu)成的網(wǎng)絡(luò)就是屬性位置簇。

基于第1章中給出的應(yīng)用和本文模型對屬性覆蓋密度、內(nèi)聚性約束和用戶對滿足屬性要求的位置的高簽到偏好的需求，本文定義了一個社區(qū)質(zhì)量度量。

定義5 社區(qū)分?jǐn)?shù)（community score）。根據(jù)屬性約束和簽到信息，定義社區(qū)分?jǐn)?shù)如下：

SG=x×|Vt||Va|+y×∑μ∈HU，v∈HALW（μ，v）∑μ∈HU，ω∈GALW（μ，ω）（1）

其中：|Vt|表示搜索到的屬性位置簇中位置節(jié)點的個數(shù)；|Va|表示原始位置節(jié)點集中滿足屬性約束的位置節(jié)點的數(shù)量；W（μ，v）是（μ，v）邊的權(quán)重;∑μ∈HU，v∈HALW（μ，v）是用戶社區(qū)中用戶到屬性位置簇的簽到邊的權(quán)重和；∑μ∈HU，ω∈GALW（μ，ω）是用戶社區(qū)中用戶到原始位置節(jié)點集中滿足屬性約束的位置上簽到邊的權(quán)重和；x+y=1。最大化的社區(qū)分?jǐn)?shù)的含義是希望結(jié)果屬性位置簇盡可能多地覆蓋滿足屬性約束的位置點，且結(jié)果用戶社區(qū)盡可能多地在結(jié)果屬性位置簇中簽到。

x和y的取值描繪了用戶對屬性覆蓋和訪問密度的偏好。在本文中設(shè)置系數(shù)x=y=12。邊權(quán)重W（μ，v）=1。圖1所示為一個帶有屬性的基于屬性的社交網(wǎng)絡(luò)，其中存在一個AGCS結(jié)果社區(qū)由{〈u10，u11，u12，u13〉，〈l14，l15，l16，l17，l18〉}組成，該屬性地理社會社區(qū)的社區(qū)分?jǐn)?shù)為SG=1/2×5/16+1/2×8/18=109/288。

問題定義 屬性地理社會社區(qū)搜索（attribute geosocial community search，AGCS）。給定一個帶有屬性的基于位置的社交網(wǎng)絡(luò)N=（GU，VL，GC）、一個查詢節(jié)點集QVGU∪VL、一個距離閾值r、一個度閾值k和查詢屬性集AQ={a1，a2，…，ai}。屬性地理社會社區(qū)搜索問題旨在找到一個滿足所有查詢約束的用戶社區(qū)HUGU和一個屬性位置簇LAC，并且最大化社區(qū)分?jǐn)?shù)。

3 屬性地理社會社區(qū)搜索方法

3.1 基本算法

為了得到一個高質(zhì)量的結(jié)果社區(qū)，首先需要得到一些滿足查詢半徑約束和內(nèi)聚性約束的用戶候選結(jié)果和同時滿足屬性約束的位置候選結(jié)果。然后，通過計算，在候選結(jié)果中找到具有最大社區(qū)分?jǐn)?shù)的社區(qū)。

通過對位置節(jié)點中距離小于半徑約束的節(jié)點創(chuàng)建邊，構(gòu)建了一個位置網(wǎng)絡(luò)。為了加快建立和刪除位置網(wǎng)絡(luò)的過程，在建立網(wǎng)絡(luò)之前需要先刪除不滿足屬性約束的位置節(jié)點。然后找到兩個網(wǎng)絡(luò)圖中度不小于k的所有候選連通分量，這些候選連通分量滿足結(jié)構(gòu)內(nèi)聚性約束。最后對兩組候選連通分量一一進(jìn)行分?jǐn)?shù)計算并得到最大社區(qū)分?jǐn)?shù)的結(jié)果。

算法1 基本算法

輸入：圖N=（GU，VL，GC）;查詢節(jié)點集QVGU∪VL;查詢屬性集AQ;半徑r;度閾值k。

輸出：用戶社區(qū)HU;屬性位置簇LAC;社區(qū)分?jǐn)?shù)Score 。

CU←OCC（GU，Q，k）；

從VL中刪除所有不包含查詢屬性的位置節(jié)點；

for each v∈VL

通過R-tree獲得節(jié)點v的可能鄰居NL；

將節(jié)點v加入到屬性位置網(wǎng)絡(luò)GAL中；

for each nj∈NL

計算v與nj之間的歐式距離Dj；

if Dj

將節(jié)點nj和邊（v，nj）添加到GAL中；

CL←OCC（GAL，Q，k） ；MaxScore←0；

從CU和CL中刪除不包含Q的候選網(wǎng)絡(luò)；

for each ci∈CU

for each cj∈CL

計算由ci、cj組成的社區(qū)的社區(qū)分?jǐn)?shù)Score；

if Score>MaxScore

MaxScore←Score；HU←ci，HAL←cj；

返回HU←ci，HAL←cj，Score。

基本算法由兩個部分組成，用戶社區(qū)搜索和屬性位置網(wǎng)絡(luò)搜索。如算法1所示，首先獲得候選用戶連通分量的集合，利用OCC（GU，Q，k）函數(shù)得到滿足約束條件的節(jié)點集。OCC（）的主要過程是移除所有度小于k的節(jié)點，同時移除因為受刪除其他節(jié)點影響導(dǎo)致度小于k的節(jié)點，直到所有節(jié)點的度大于或等于k。然后刪除位置節(jié)點集中所有不滿足屬性約束的節(jié)點。屬性位置網(wǎng)絡(luò)的生成是借助R-tree完成的，下一步生成候選屬性位置連通分量集，并將不包含查詢節(jié)點的連通分量從兩個連通分量集合中刪除，最后計算每組連通分量（一個用戶連通分量和一個位置連通分量）的社區(qū)得分，社區(qū)分?jǐn)?shù)最大的一對連通分量就是屬性地理社會社區(qū)搜索的結(jié)果。

3.2 局部算法

由于k-core的搜索算法隱含有找最大連通分量的約束，基本算法得到的結(jié)果社區(qū)分?jǐn)?shù)并不是當(dāng)前圖可以得到的最大分?jǐn)?shù)，為了得到具有較高社區(qū)分?jǐn)?shù)的結(jié)果，提出了局部算法。

局部算法的基本思想是從給定的查詢節(jié)點出發(fā)，使用給定的貪心擴(kuò)展策略向當(dāng)前解決方案中迭代的添加節(jié)點，逐步擴(kuò)大當(dāng)前解決方案的規(guī)模。

局部算法初始化當(dāng)前解決方案為查詢節(jié)點構(gòu)成的網(wǎng)絡(luò)，對兩個網(wǎng)絡(luò)分別初始化一個優(yōu)先隊列，優(yōu)先隊列存儲可能要插入到當(dāng)前解決方案中的候選節(jié)點。初始化優(yōu)先隊列為查詢節(jié)點的鄰居節(jié)點，如果不包含任何用戶或位置查詢節(jié)點，則當(dāng)前解決方案對應(yīng)的簽到圖的鄰居節(jié)點將被插入到優(yōu)先隊列中。然后根據(jù)隊列優(yōu)先級標(biāo)準(zhǔn)維護(hù)兩個優(yōu)先隊列。

局部算法的關(guān)鍵在于優(yōu)先隊列的排序標(biāo)準(zhǔn)，如下：a）優(yōu)先隊列中的節(jié)點到當(dāng)前解決方案的簽到邊權(quán)重和;b）優(yōu)先隊列中的節(jié)點在當(dāng)前解決方案的鄰居個數(shù)。

第一個標(biāo)準(zhǔn)隱含的意義是保證插入到當(dāng)前解決方案的節(jié)點對社區(qū)分?jǐn)?shù)的貢獻(xiàn)，可以增加當(dāng)前解決方案的簽到權(quán)重。第二個標(biāo)準(zhǔn)是保證加入的節(jié)點能更快地使解決方案滿足結(jié)構(gòu)內(nèi)聚性。第一個標(biāo)準(zhǔn)的優(yōu)先級高于第二個標(biāo)準(zhǔn)。

性質(zhì)1 給定修剪后的屬性位置網(wǎng)絡(luò)GL，不存在HLGL可以使社區(qū)分?jǐn)?shù)更高。

由性質(zhì)1可以看出基本算法可以直接得到最優(yōu)社區(qū)分?jǐn)?shù)的屬性位置網(wǎng)絡(luò)，因此，局部算法只需要重新生成用戶網(wǎng)絡(luò)即可。

算法2 局部算法

輸入：用戶網(wǎng)絡(luò)圖GU，屬性位置網(wǎng)絡(luò)GAL，查詢節(jié)點集QVGU∪VL，查詢屬性集AQ，度閾值k。

輸出：用戶社區(qū)HU，屬性位置簇LAC，社區(qū)分?jǐn)?shù)Score。

初始化用戶當(dāng)前解決方案HU、位置解決方案HAL、用戶優(yōu)先隊列UWait；

while δ（HU）

for each vi∈UWait

分別計算節(jié)點vi兩個優(yōu)先級標(biāo)準(zhǔn)的分?jǐn)?shù)；

對UWait中節(jié)點按照優(yōu)先級標(biāo)準(zhǔn)進(jìn)行排序；

將UWait中的第一個節(jié)點插入到HU中，并將這個節(jié)點的鄰居插入到UWait中；

reScore←Score←HU和GAL組成的社區(qū)的社區(qū)分?jǐn)?shù)；

while reScore=Score

找到優(yōu)先隊列中優(yōu)先級較高且保證結(jié)構(gòu)內(nèi)聚性的點vu；計算插入vu后的社區(qū)分?jǐn)?shù)reScore；

if reScore>Score

將vu插入HU中；Score←reScore；

else

reScore=0；

返回HU，HAL，Score。

算法2描述如下，初始化解決方案為用戶查詢節(jié)點和輸入的屬性位置網(wǎng)絡(luò)，將查詢節(jié)點的鄰居插入到優(yōu)先隊列中，按照優(yōu)先級a）b）計算優(yōu)先隊列中的節(jié)點標(biāo)準(zhǔn)分?jǐn)?shù)并排序。將優(yōu)先隊列的第一個節(jié)點插入到社區(qū)解決方案中，然后將這個節(jié)點的鄰居插入到優(yōu)先隊列中，迭代以上過程直到社區(qū)解決方案滿足結(jié)構(gòu)內(nèi)聚性，然后計算社區(qū)分?jǐn)?shù)。為保證最終得到的解決方案的社區(qū)分?jǐn)?shù)最大，對優(yōu)先隊列的排序標(biāo)準(zhǔn)進(jìn)行了修改，繼續(xù)對解決方案進(jìn)行擴(kuò)展。

修改后的排序標(biāo)準(zhǔn)如下：a）優(yōu)先隊列中的節(jié)點到當(dāng)前解決方案的簽到邊權(quán)重和/優(yōu)先隊列中的節(jié)點到原始網(wǎng)絡(luò)的簽到邊權(quán)重和;b）優(yōu)先隊列中的節(jié)點在當(dāng)前解決方案的鄰居個數(shù)。

使用新標(biāo)準(zhǔn)重新計算優(yōu)先隊列標(biāo)準(zhǔn)分?jǐn)?shù)，取標(biāo)準(zhǔn)b）分?jǐn)?shù)滿足k約束的節(jié)點并按標(biāo)準(zhǔn)a）降序排序。然后假設(shè)將優(yōu)先隊列中的第一個節(jié)點插入到社區(qū)解決方案，并計算插入后的社區(qū)分?jǐn)?shù)，如果分?jǐn)?shù)變大則更新社區(qū)解決方案和社區(qū)分?jǐn)?shù)。重復(fù)上述過程直到社區(qū)分?jǐn)?shù)不在增長，返回社區(qū)分?jǐn)?shù)最大的結(jié)果社區(qū)。

復(fù)雜度分析：判斷結(jié)果社區(qū)是否滿足結(jié)構(gòu)內(nèi)聚性并且對優(yōu)先隊列進(jìn)行維護(hù)的復(fù)雜度是O（n（c+n log n+m+n）+n），其中對每個點都計算一次優(yōu)先級分?jǐn)?shù)的復(fù)雜度是O（c），c是用戶社區(qū)到位置社區(qū)總簽到次數(shù)。優(yōu)先隊列排序的時間復(fù)雜度為O（n log n），UWait的維護(hù)代價是O（n），k-core判斷的代價是O（m+n），m是用戶社區(qū)中邊的數(shù)量，n是用戶社區(qū)節(jié)點數(shù)量。第二個循環(huán)的代價同上，所以最終時間復(fù)雜度為O（n（c+n log n+m+n）+n）。

3.3 優(yōu)化算法

局部算法優(yōu)化了基本算法的結(jié)果質(zhì)量，但局部算法的執(zhí)行效率不高，為了提升局部算法的執(zhí)行效率，首先通過對圖的結(jié)構(gòu)內(nèi)聚性判斷過程進(jìn)行分析，開發(fā)了一種快速對節(jié)點度進(jìn)行維護(hù)的優(yōu)化策略。然后由于局部算法在每一次優(yōu)先隊列發(fā)生變化時，都需要對優(yōu)先隊列進(jìn)行重排操作維護(hù)其優(yōu)先級。分析算法流程，通過將優(yōu)先隊列重構(gòu)和最佳節(jié)點選擇組合到一起，排序過程可以從局部算法中剔除。結(jié)合以上兩種優(yōu)化策略，最終得到了優(yōu)化的局部算法。

3.3.1 圖結(jié)構(gòu)判斷

局部算法要求在每次插入新節(jié)點后對當(dāng)前解決方案進(jìn)行結(jié)構(gòu)內(nèi)聚性判斷，當(dāng)前最優(yōu)的結(jié)構(gòu)內(nèi)聚性判斷算法時間復(fù)雜度是O（m+n），隨著解決方案規(guī)模的增長，這部分算法的執(zhí)行代價也在持續(xù)增長。為了優(yōu)化這個過程，優(yōu)化算法首先初始化變量kmin為當(dāng)前解決方案中度最小的節(jié)點。每次產(chǎn)生新的節(jié)點插入時，kmin維護(hù)為新解決方案中度最小的節(jié)點，直到kmin大于等于k。合理的數(shù)據(jù)結(jié)構(gòu)設(shè)計使得更新過程中不需要遍歷全圖，只需要比對當(dāng)前插入節(jié)點及受當(dāng)前插入節(jié)點影響導(dǎo)致度增加的節(jié)點的度。優(yōu)化后的時間復(fù)雜度為O（1）。

3.3.2 優(yōu)先隊列維護(hù)

局部算法中，優(yōu)先隊列的維護(hù)要求每次向優(yōu)先隊列插入節(jié)點都需要對優(yōu)先隊列進(jìn)行排序，即使最佳的排序策略也具有O（n log n）的代價，由于每次只需要提取當(dāng)前最佳節(jié)點插入到結(jié)果中，優(yōu)化算法把排序和節(jié)點分?jǐn)?shù)計算結(jié)合，在計算分?jǐn)?shù)時保留了最佳節(jié)點，去掉了排序的過程。

算法3 優(yōu)化算法

輸入：用戶網(wǎng)絡(luò)圖GU，屬性位置網(wǎng)絡(luò)GAL，查詢節(jié)點集QVGU∪VL，查詢屬性集AQ，度閾值k。

輸出：用戶社區(qū)HU，屬性位置簇LAC，社區(qū)分?jǐn)?shù)Score。

初始化用戶當(dāng)前解決方案HU位置解決方案HAL、用戶優(yōu)先隊列UWait，指針m指向待插入節(jié)點及其兩個標(biāo)準(zhǔn)的分?jǐn)?shù)sm1，sm2 ；

kmin←δ（HU）；

while kmin

for each vi∈UWait

計算節(jié)點vi兩個優(yōu)先級標(biāo)準(zhǔn)的分?jǐn)?shù)s1，s2；

if s1

m指向vi，sm1←s1；

else if s1==sm1并且s2>sm2

m指向vi，sm1←s1， sm2←s2

將m指向的節(jié)點插入到HU中，將kmin更新為HU的最小度，

reScore←Score←HU和GAL組成的社區(qū)的社區(qū)分?jǐn)?shù)；

while reScore=Score

找到優(yōu)先隊列中優(yōu)先級較高且保證結(jié)構(gòu)內(nèi)聚性的點vu，計算插入 vu后的社區(qū)分?jǐn)?shù)reScore；

if reScore>Score

將vu插入HU中；Score←reScore；

else

reScore=0；

返回HU，HAL，Score。

算法3描述如下，將用戶查詢節(jié)點插入到社區(qū)結(jié)果HU中，將查詢節(jié)點的鄰居插入到優(yōu)先隊列UWait中，指針m指向隊列中的節(jié)點，sm1為指向節(jié)點的標(biāo)準(zhǔn)a）的分?jǐn)?shù)，sm2為指向節(jié)點的標(biāo)準(zhǔn)b）的分?jǐn)?shù)，記錄社區(qū)結(jié)果HU中節(jié)點的最小度值kmin。當(dāng)kmin

復(fù)雜度分析：記錄并維護(hù)社區(qū)結(jié)果的最小度和可能插入結(jié)果社區(qū)的節(jié)點，這個過程的復(fù)雜度是O（n×c+n），其中對用戶社區(qū)中每個點都計算一次優(yōu)先級分?jǐn)?shù)的代價是c，c是用戶社區(qū)到位置社區(qū)總簽到次數(shù)。n是用戶社區(qū)節(jié)點數(shù)量。第二個循環(huán)同上，所以最終時間復(fù)雜度為O（n×c+n）。

4 實驗與評價

4.1 數(shù)據(jù)描述與實驗設(shè)置

本文使用了以下三個數(shù)據(jù)集進(jìn)行實驗：

a）Yelp（YP）［3］。Yelp數(shù)據(jù)集包括1 987 897名用戶，177 969個商家，908 915次簽到記錄，以及超過120 000個屬性。本文從中隨機(jī)抽取了100 000個用戶節(jié)點，177 969個商家和908 915條簽到信息生成數(shù)據(jù)集。

b）Gowalla（GL）［17］。Gowalla是一個基于位置的社交網(wǎng)站，Gowalla數(shù)據(jù)集包括196 591名用戶，172 979個地點，6 442 890條簽到信息。從中隨機(jī)抽取了100 000用戶，100 000位置，6 442 890條簽到信息生成數(shù)據(jù)集。

c）Brightkite（BK）［18］。Brightkite數(shù)據(jù)集包括58 227個用戶和772 967個地點，4 491 143條簽到信息。從中隨機(jī)抽取一個了58 227個用戶和100 000個帶有183 384條簽到記錄的位置節(jié)點生成數(shù)據(jù)集。

因為數(shù)據(jù)集Gowalla、Brightkite不包含屬性，所以將數(shù)據(jù)集進(jìn)行分組，給每組位置節(jié)點，隨機(jī)分配數(shù)量不等的10種屬性，由此合成需要的數(shù)據(jù)集。

實驗設(shè)置各參數(shù)默認(rèn)值為：k=20，|Q|=2（一個用戶查詢點，一個位置查詢點），|A|=1，r=50 m。

實驗首先研究了三個算法在同樣的參數(shù)設(shè)置下、不同數(shù)據(jù)集上的社區(qū)質(zhì)量，然后研究了優(yōu)化策略的有效性。參數(shù)的變化可能會對算法的執(zhí)行效率產(chǎn)生影響，所以接下來通過改變參數(shù)k、參數(shù)r和屬性個數(shù)研究了算法的執(zhí)行效率變化，最后通過改變數(shù)據(jù)集的大小，證明了算法的可伸縮性。

所有算法使用GNU C++實現(xiàn)。實驗運行在一臺Windows 10系統(tǒng)、3.9 GHz CPU、256 GB RAM和1 TB磁盤的PC上。

4.2 實驗評估

a）模型差異。與本文模型最相近的工作是文獻(xiàn)［4］中的地理社會社區(qū)搜索（GCS），在同樣的內(nèi)聚性和半徑約束下，通過設(shè)置不同的查詢點進(jìn)行實驗，地理社會社區(qū)搜索中質(zhì)量最佳的GRA算法推薦的位置簇中滿足屬性需求的位置點覆蓋率最多達(dá)到了32.3%，所以GCS并不能滿足用戶對屬性的需求。任意條件下，AGCS都可以在保證內(nèi)聚性和緊密的空間關(guān)系的同時，保證提供的位置簇100%的屬性覆蓋。

b）社區(qū)分?jǐn)?shù)評估。如圖4所示，通過設(shè)置k，r及查詢屬性數(shù)量為默認(rèn)值，本文評估了三個算法在三個數(shù)據(jù)集上的社區(qū)得分表現(xiàn)，可以發(fā)現(xiàn)local和optimization算法的社區(qū)分?jǐn)?shù)都在basic算法的基礎(chǔ)上獲得了提升，實際通過觀察實驗結(jié)果和實驗過程，local和optimization的最終結(jié)果社區(qū)簽到貢獻(xiàn)相較basic更加緊密，規(guī)模也縮小了。

優(yōu)化策略有效性評估：如圖5所示，通過設(shè)置各項參數(shù)為默認(rèn)值，在YP、BK和GL數(shù)據(jù)集上，分別取出10組不同的查詢點，并在實驗后取均值評估了本文提出的優(yōu)化策略的有效性，觀察實驗圖可以發(fā)現(xiàn)，在真實世界的數(shù)據(jù)集Yelp上效率提升了約14倍，在Gowalla和Brightkite數(shù)據(jù)集上效率各提升了約44和55倍，平均下來optimization相較local獲得了約40倍的效率提升。

d）參數(shù)k對效率影響評估。參數(shù)k衡量了用戶對查詢結(jié)果內(nèi)聚程度的偏好，k從結(jié)構(gòu)內(nèi)聚性方面約束查詢結(jié)果，通常情況下越高的k值帶來越少的圖節(jié)點數(shù)量。

為了研究內(nèi)聚性變化對算法執(zhí)行效率的影響。如圖6所示，通過設(shè)置r和查詢屬性數(shù)量為默認(rèn)值，在YP和GL數(shù)據(jù)集上設(shè)置k為20～40，在BK數(shù)據(jù)集上設(shè)置k為5～20。分別研究了參數(shù)k的變化對實驗效率的影響，k取值范圍的差異是因為數(shù)據(jù)集平均節(jié)點度不一致。一種直覺是隨著參數(shù)k的增大，算法效率應(yīng)該獲得提高，因為參與運算的點和邊的數(shù)量可能減少。但實際上通過實驗發(fā)現(xiàn)k并不與local和optimization需要運算的社區(qū)規(guī)模正相關(guān)，k的變化導(dǎo)致Basic獲得不同規(guī)模的用戶社區(qū)，用戶社區(qū)規(guī)模越大，local和optimization算法的執(zhí)行時間就越長，但總體來說optimization在不同規(guī)模的社區(qū)下都能獲得較好的執(zhí)行效率。

參數(shù)r對效率影響評估：參數(shù)r衡量了用戶對位置網(wǎng)絡(luò)構(gòu)建半徑的偏好，r的變化影響位置網(wǎng)絡(luò)構(gòu)造的范圍，通常情況下越大的r值會帶來越高的圖平均節(jié)點度，進(jìn)而帶來越多的待處理節(jié)點數(shù)量和邊數(shù)量。

為了研究r的變化對算法執(zhí)行效率的影響。如圖7所示，通過設(shè)置k和查詢屬性數(shù)量為默認(rèn)值，在YP和GL數(shù)據(jù)集上設(shè)置r為30～70，在BK數(shù)據(jù)集上設(shè)置r為25～125。分別研究了參數(shù)r的變化對實驗效率的影響，r取值范圍的差異是因為數(shù)據(jù)集節(jié)點分布密度的不一致。通過實驗發(fā)現(xiàn)r的變化幾乎不對local和optimization算法的執(zhí)行效率造成影響，因為基于性質(zhì)1，local和optimization不再對位置網(wǎng)絡(luò)進(jìn)行運算，而r的變化改變了位置網(wǎng)絡(luò)的內(nèi)聚性，但幾乎不改變用戶社區(qū)。

e）查詢屬性數(shù)量對效率影響評估。屬性變化衡量了用戶對具有某一類特殊標(biāo)簽的位置的喜好，一種直覺是越多、越精細(xì)的屬性要求可能導(dǎo)致越少的待處理位置節(jié)點。

如圖8所示，通過設(shè)置k和r為默認(rèn)值，在三個數(shù)據(jù)集上設(shè)置查詢屬性數(shù)量為1～3，分別研究了查詢屬性數(shù)量的變化對實驗效率的影響，觀察實驗圖發(fā)現(xiàn)隨著查詢屬性數(shù)量的增長，算法總體效率呈現(xiàn)增長趨勢，這是因為查詢屬性數(shù)量的增長導(dǎo)致待運算的位置網(wǎng)絡(luò)節(jié)點數(shù)量大幅降低，盡管用戶社區(qū)規(guī)模變化不大，但是位置網(wǎng)絡(luò)節(jié)點數(shù)量的減少造成算法運算代價的降低，圖8（b）體現(xiàn)出了這種代價的降低。圖8（a）（c）屬性數(shù)量從1～2時算法運算時間變化不大是因為候選位置網(wǎng)絡(luò)節(jié)點數(shù)量并未因?qū)傩詳?shù)量的變化產(chǎn)生太大的波動。

f）算法可伸縮性評估。如圖9所示，通過設(shè)置k和r和查詢屬性數(shù)量為默認(rèn)值，分別伸縮三個數(shù)據(jù)集的規(guī)模為20%～100%，研究了算法的可伸縮性，也研究了規(guī)模變化對算法執(zhí)行效率的影響。觀察圖9（a），算法執(zhí)行效率的波動是因為數(shù)據(jù)集規(guī)模的變化導(dǎo)致結(jié)果社區(qū)大小一直在不規(guī)律波動，這是因為basic算法找到的社區(qū)作為local和optimization的待處理社區(qū)。這導(dǎo)致basic的結(jié)果規(guī)?？赡茈S著數(shù)據(jù)集規(guī)模的變化產(chǎn)生無序的變化。也就造成了local和optimization效率的波動，但在GL和BK上，隨著數(shù)據(jù)集規(guī)模的變化，盡管local和optimization的待處理節(jié)點產(chǎn)生了變化，但處理的規(guī)模并沒有劇烈波動，這導(dǎo)致了整個算法的執(zhí)行代價趨于平穩(wěn)。

4.3 實例研究

通過在真實世界的Yelp數(shù)據(jù)集上，設(shè)置k=15，r=0.05 km，使用得到的社區(qū)質(zhì)量最佳的優(yōu)化算法。本文進(jìn)行了一個案例研究來證明AGCS的有效性。

組織活動：用戶準(zhǔn)備舉行一個聚會，并希望得到一群人和一個特定地點的推薦來幫助用戶舉辦活動。被邀請參加活動的人應(yīng)該和用戶關(guān)系密切，并且他們相互間的聯(lián)系也很密切。推薦舉辦活動的地點應(yīng)該被參加活動的人群頻繁訪問，并且滿足活動主題。在本例中推薦地點需要能夠提供聚會的相關(guān)服務(wù)。

為了找到這樣的受邀人員和舉辦活動的候選地點，本文發(fā)出了一個AGCS查詢，它由組織者、用戶訪問過的地點以及用戶需要地點滿足的功能“相關(guān)服務(wù)”組成。AGCS找到了一組由150個用戶組成的社區(qū)和69個可以用來舉辦聚會的地點，這些地點共被用戶社區(qū)進(jìn)行過652次歷史訪問，且在空間上鄰近。最終社區(qū)分?jǐn)?shù)為0.151。

5 結(jié)束語

本文提出了屬性地理社區(qū)搜索問題（AGCS），該問題可以在包含屬性的基于位置的社交網(wǎng)絡(luò)文中找到一個緊密連接的用戶社區(qū)和一個屬性位置簇。定義了一個衡量社區(qū)質(zhì)量的社區(qū)分?jǐn)?shù)計算函數(shù)并設(shè)計了一個基本算法、一個局部算法和一個優(yōu)化的局部算法。最后基于三個數(shù)據(jù)集對提出的算法進(jìn)行了效率和有效性的評估。

AGCS需要用戶提供k、r、查詢點和查詢屬性四個查詢參數(shù)，由于用戶并不一定具備相關(guān)專業(yè)知識，或者對網(wǎng)絡(luò)不甚熟悉。提供合適的參數(shù)以獲取一組滿足用戶需求的社區(qū)對于用戶來說可能是困難的。在未來的工作中，將研究如何以有限的時間成本，通過查詢參數(shù)推薦的方法有效地幫助用戶探索符合用戶需求的一組社區(qū)及其對應(yīng)的查詢參數(shù)。

參考文獻(xiàn)：

[1]Fang Yixiang，Huang Xin，Qin Lu，et al.A survey of community search over big graphs［J］.The VLDB Journal，2020，29（1）：353-392.

［2]Sozio M，Gionis A.The community-search problem and how to plan a successful cocktail party［C］//Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2010：939-948.

［3]Liu Yiding，Pham T，Cong Gao，et al.An experimental evaluation of point-of-interest recommendation in location-based social networks［C］//Proc of the VLDB Endowment.New York：ACM Press，2017，10（10）：1010-1021.

［4]Kim J，Guo Tao，F(xiàn)eng Kaiyu，et al.Densely connected user community and location cluster search in location-based social networks［C］//Proc of the 29th ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2020：2199-2209.

［5]Zhu Qijun，Hu Haibo，Xu Cheng，et al.Geo-social group queries with minimum acquaintance constraints［J］.The VLDB Journal，2017，26（5）：709-727.

［6]Wang Kai，Wang Shuting，Cao Xing，et al.Efficient radius-bounded community search in geo-social networks［J］.IEEE Trans on Knowledge and Data Engineering，2022，34（9）：4186-4200.

［7]Fang Yixiang，Reynold C，Chen Yankai，et al.Effective and efficient attributed community search［J］.The VLDB Journal，2017，26（6）：803-828.

［8]Zhang Zhiwei，Huang Xin，Xu Jianliang，et al.Keyword-centric community search［C］//Proc of the 35th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2019：422-433.

［9]Chen Lu，Liu Chengfei，Liao Kewen，et al.Contextual community search over large social networks［C］//Proc of the 35th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2019：88-99.

［10]Liu Qing，Zhu Yifan，Zhao Minjun，et al.VAC：vertex-centric attributed community search［C］//Proc of the 36th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2020：937-948.

［11]Apon S H，Ali M E，Ghosh B，et al.Social-spatial group queries with keywords［J］.ACM Trans on Spatial Algorithms and Systems，2021，8（1）：1-32.

［12]楊成波，周麗華，黃亞群，等.異質(zhì)網(wǎng)絡(luò)中基于關(guān)鍵詞屬性的Truss社區(qū)搜索［J］.計算機(jī)應(yīng)用研究，2023，40（6）：1708-1714.（Yang Chengbo，Zhou Lihua，Huang Yaqun，et al.Truss community search based on keyword attributes in heterogeneous networks［J］.Application Research of Computers，2023，40（6）：1708-1714.）

［13]Guo Fangda，Yuan Ye，Wang Guoren，et al.Multi-attributed community search in road-social networks［C］//Proc of the 37th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2021：109-120.

［14]Chen Lu，Liu Chengfei，Zhou Rui，et al.Maximum co-located community search in large scale social networks［C］//Proc of the VLDB Endowment.New York：ACM Press，2018，11（10）：1233-1246.

［15]Chen Lu，Liu Chengfei，Zhou Rui，et al.Finding effective geo-social group for impromptu activities with diverse demands［C］//Proc of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2020：698-708.

［16]李青青，馬慧芳，李舉，等.屬性網(wǎng)絡(luò)中結(jié)合用戶偏好的社區(qū)搜索和離群點檢測［J］.電子學(xué)報，2022，50（9）：2172-2180.（Li Qingqing，Ma Huifang，Li Ju，et al.Community search and outlier detection combining user preferences in attribute networks［J］.Acta Electronica Sinica，2022，50（9）：2172-2180.）

［17]Cho E，Myers S，Leskovec J.Friendship and mobility：user movement in location-based social networks［C］//Proc of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2011：1082-1090.

［18]Cui Wanyun，Xiao Yanghua，Wang Haixun，et al.Local search of communities in large graphs［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2014：991-1002.

收稿日期：2023-01-28；

修回日期：2023-03-20

基金項目：國家自然科學(xué)基金資助項目（61802268）；遼寧省自然科學(xué)基金面上項目（2022-MS-303）

作者簡介：宗傳玉（1985-），男，山東濰坊人，副教授，CCF會員，博士，主要研究方向為數(shù)據(jù)清洗、數(shù)據(jù)溯源、查詢處理與優(yōu)化；李箬竹（1997-），女（蒙古族）（通信作者），遼寧朝陽人，碩士研究生，主要研究方向為查詢處理與優(yōu)化（liruozhu@stu.sau.edu.cn）；夏秀峰（1964-），男，山東膠南人，教授，CCF會員，博士，主要研究方向為數(shù)據(jù)庫、數(shù)據(jù)倉庫.