宗傳玉 李箬竹 夏秀峰

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

同時(shí)基于位置和屬性的社區(qū)搜索的研究，Guo等人［13］提出了多屬性社區(qū)（MAC）搜索，并研究了兩種有效計(jì)算top-j多屬性社區(qū)的方法。Chen等人［14］提出了共定位社區(qū)搜索（LCD）問題，其得到的社區(qū)滿足k-truss約束和用戶的空間位置約束。Chen等人［15］還提出了地理社會(huì)群體搜索問題，來獲得一個(gè)與某一地點(diǎn)相近并且社會(huì)關(guān)系密切的一群人，并提出MKCSSG模型，在找到最佳的社區(qū)結(jié)果的同時(shí)縮小了搜索空間。文獻(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)聚性，同時(shí)提出了關(guān)鍵詞屬性得分函數(shù)用于度量不同子圖的關(guān)鍵詞屬性相關(guān)性。

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

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

帶有屬性的基于位置的社交網(wǎng)絡(luò)（location-based social network with attributes，LBSNA）：給定一個(gè)無向圖G=（V，E），G表示由一組節(jié)點(diǎn)V和一組邊EV×V組成的社交網(wǎng)絡(luò)。VH是V中節(jié)點(diǎn)的子集，H=（VH，EH）表示由VH誘導(dǎo)的G的子圖。簽到圖由一個(gè)二分圖GC=（VU，VL，EC）表示，其中VU是一組用戶節(jié)點(diǎn)，VL={（li，A（li））}是一組具有A（li）={a1，a2，a3，…，aj}屬性標(biāo)簽的位置點(diǎn)，（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ò)由一個(gè)社交網(wǎng)絡(luò)GU、一組帶有屬性標(biāo)簽的位置節(jié)點(diǎn)集VL和一個(gè)簽到圖GC組成。

社區(qū)通常是一個(gè)滿足結(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é)點(diǎn)v的節(jié)點(diǎn)數(shù)，即節(jié)點(diǎn)v的鄰居數(shù)，deg（v）也被稱為一個(gè)節(jié)點(diǎn)的度。此外，給定一個(gè)子圖H=（VH，EH），δ（H）返回節(jié)點(diǎn)v∈VH的最小度。k-core的定義如下。

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

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

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

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

定義4 屬性位置簇（attribute location cluster）。給定一個(gè)位置節(jié)點(diǎn)集VL，一個(gè)距離閾值r，一個(gè)查詢屬性集AQ={a1，a2，…，an}和一個(gè)度閾值k。如果滿足以下條件，則一組位置點(diǎn)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ò)中獲取屬性位置簇。通過為滿足屬性約束并且距離小于等于半徑約束的點(diǎn)創(chuàng)建邊，可以得到屬性位置網(wǎng)絡(luò)。

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

基于第1章中給出的應(yīng)用和本文模型對屬性覆蓋密度、內(nèi)聚性約束和用戶對滿足屬性要求的位置的高簽到偏好的需求，本文定義了一個(gè)社區(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é)點(diǎn)的個(gè)數(shù)；|Va|表示原始位置節(jié)點(diǎn)集中滿足屬性約束的位置節(jié)點(diǎn)的數(shù)量；W（μ，v）是（μ，v）邊的權(quán)重;∑μ∈HU，v∈HALW（μ，v）是用戶社區(qū)中用戶到屬性位置簇的簽到邊的權(quán)重和；∑μ∈HU，ω∈GALW（μ，ω）是用戶社區(qū)中用戶到原始位置節(jié)點(diǎn)集中滿足屬性約束的位置上簽到邊的權(quán)重和；x+y=1。最大化的社區(qū)分?jǐn)?shù)的含義是希望結(jié)果屬性位置簇盡可能多地覆蓋滿足屬性約束的位置點(diǎn)，且結(jié)果用戶社區(qū)盡可能多地在結(jié)果屬性位置簇中簽到。

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

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

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

3.1 基本算法

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

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

算法1 基本算法

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

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

CU←OCC（GU，Q，k）；

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

for each v∈VL

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

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

for each nj∈NL

計(jì)算v與nj之間的歐式距離Dj；

if Dj

將節(jié)點(diǎn)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

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

if Score>MaxScore

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

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

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

3.2 局部算法

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

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

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

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

第一個(gè)標(biāo)準(zhǔn)隱含的意義是保證插入到當(dāng)前解決方案的節(jié)點(diǎn)對社區(qū)分?jǐn)?shù)的貢獻(xiàn)，可以增加當(dāng)前解決方案的簽到權(quán)重。第二個(gè)標(biāo)準(zhǔn)是保證加入的節(jié)點(diǎn)能更快地使解決方案滿足結(jié)構(gòu)內(nèi)聚性。第一個(gè)標(biāo)準(zhǔn)的優(yōu)先級(jí)高于第二個(gè)標(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é)點(diǎn)集QVGU∪VL，查詢屬性集AQ，度閾值k。

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

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

while δ（HU）

for each vi∈UWait

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

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

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

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

while reScore=Score

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

if reScore>Score

將vu插入HU中；Score←reScore；

else

reScore=0；

返回HU，HAL，Score。

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

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

使用新標(biāo)準(zhǔn)重新計(jì)算優(yōu)先隊(duì)列標(biāo)準(zhǔn)分?jǐn)?shù)，取標(biāo)準(zhǔn)b）分?jǐn)?shù)滿足k約束的節(jié)點(diǎn)并按標(biāo)準(zhǔn)a）降序排序。然后假設(shè)將優(yōu)先隊(duì)列中的第一個(gè)節(jié)點(diǎn)插入到社區(qū)解決方案，并計(jì)算插入后的社區(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)先隊(duì)列進(jìn)行維護(hù)的復(fù)雜度是O（n（c+n log n+m+n）+n），其中對每個(gè)點(diǎn)都計(jì)算一次優(yōu)先級(jí)分?jǐn)?shù)的復(fù)雜度是O（c），c是用戶社區(qū)到位置社區(qū)總簽到次數(shù)。優(yōu)先隊(duì)列排序的時(shí)間復(fù)雜度為O（n log n），UWait的維護(hù)代價(jià)是O（n），k-core判斷的代價(jià)是O（m+n），m是用戶社區(qū)中邊的數(shù)量，n是用戶社區(qū)節(jié)點(diǎn)數(shù)量。第二個(gè)循環(huán)的代價(jià)同上，所以最終時(shí)間復(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é)點(diǎn)度進(jìn)行維護(hù)的優(yōu)化策略。然后由于局部算法在每一次優(yōu)先隊(duì)列發(fā)生變化時(shí)，都需要對優(yōu)先隊(duì)列進(jìn)行重排操作維護(hù)其優(yōu)先級(jí)。分析算法流程，通過將優(yōu)先隊(duì)列重構(gòu)和最佳節(jié)點(diǎn)選擇組合到一起，排序過程可以從局部算法中剔除。結(jié)合以上兩種優(yōu)化策略，最終得到了優(yōu)化的局部算法。

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

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

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

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

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

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

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

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

kmin←δ（HU）；

while kmin

for each vi∈UWait

計(jì)算節(jié)點(diǎn)vi兩個(gè)優(yōu)先級(jí)標(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é)點(diǎn)插入到HU中，將kmin更新為HU的最小度，

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

while reScore=Score

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

if reScore>Score

將vu插入HU中；Score←reScore；

else

reScore=0；

返回HU，HAL，Score。

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

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

4 實(shí)驗(yàn)與評價(jià)

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

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

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

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

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

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

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

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

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

4.2 實(shí)驗(yàn)評估

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

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

優(yōu)化策略有效性評估：如圖5所示，通過設(shè)置各項(xiàng)參數(shù)為默認(rèn)值，在YP、BK和GL數(shù)據(jù)集上，分別取出10組不同的查詢點(diǎn)，并在實(shí)驗(yàn)后取均值評估了本文提出的優(yōu)化策略的有效性，觀察實(shí)驗(yàn)圖可以發(fā)現(xiàn)，在真實(shí)世界的數(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é)點(diǎn)數(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的變化對實(shí)驗(yàn)效率的影響，k取值范圍的差異是因?yàn)閿?shù)據(jù)集平均節(jié)點(diǎn)度不一致。一種直覺是隨著參數(shù)k的增大，算法效率應(yīng)該獲得提高，因?yàn)閰⑴c運(yùn)算的點(diǎn)和邊的數(shù)量可能減少。但實(shí)際上通過實(shí)驗(yàn)發(fā)現(xiàn)k并不與local和optimization需要運(yùn)算的社區(qū)規(guī)模正相關(guān)，k的變化導(dǎo)致Basic獲得不同規(guī)模的用戶社區(qū)，用戶社區(qū)規(guī)模越大，local和optimization算法的執(zhí)行時(shí)間就越長，但總體來說optimization在不同規(guī)模的社區(qū)下都能獲得較好的執(zhí)行效率。

參數(shù)r對效率影響評估：參數(shù)r衡量了用戶對位置網(wǎng)絡(luò)構(gòu)建半徑的偏好，r的變化影響位置網(wǎng)絡(luò)構(gòu)造的范圍，通常情況下越大的r值會(huì)帶來越高的圖平均節(jié)點(diǎn)度，進(jìn)而帶來越多的待處理節(jié)點(diǎn)數(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的變化對實(shí)驗(yàn)效率的影響，r取值范圍的差異是因?yàn)閿?shù)據(jù)集節(jié)點(diǎn)分布密度的不一致。通過實(shí)驗(yàn)發(fā)現(xiàn)r的變化幾乎不對local和optimization算法的執(zhí)行效率造成影響，因?yàn)榛谛再|(zhì)1，local和optimization不再對位置網(wǎng)絡(luò)進(jìn)行運(yùn)算，而r的變化改變了位置網(wǎng)絡(luò)的內(nèi)聚性，但幾乎不改變用戶社區(qū)。

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

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

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

4.3 實(shí)例研究

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

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

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

5 結(jié)束語

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

AGCS需要用戶提供k、r、查詢點(diǎn)和查詢屬性四個(gè)查詢參數(shù)，由于用戶并不一定具備相關(guān)專業(yè)知識(shí)，或者對網(wǎng)絡(luò)不甚熟悉。提供合適的參數(shù)以獲取一組滿足用戶需求的社區(qū)對于用戶來說可能是困難的。在未來的工作中，將研究如何以有限的時(shí)間成本，通過查詢參數(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ì)算機(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ū)搜索和離群點(diǎn)檢測［J］.電子學(xué)報(bào)，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

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

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