異質網絡中基于關鍵詞屬性的Truss社區搜索

摘 要：社區搜索旨在信息網絡中尋找與用戶指定的查詢節點高度相關的稠密連通子圖，是社會網絡分析的重要研究內容。現有的社區搜索方法大多是針對同質網絡，但現實中的信息網絡通常是包含多種節點類型和多種關系類型的屬性異質網絡。提出了異質網絡中基于元路徑P和元結構S的P-距離和S-距離及（k，d，P）-truss和（k，d，S）-truss社區模型以度量子圖的結構內聚性，同時提出了關鍵詞屬性得分函數用于度量不同子圖的關鍵詞屬性相關性，最后提出了搜索具有最高關鍵詞屬性得分的（k，d，P）-truss和（k，d，S）-truss的社區搜索算法。搜索算法能夠找到同時具有結構內聚性和關鍵詞屬性相關性的個性化社區，并且支持限制查詢節點與社區內任意節點的最大距離d來控制社區搜索的范圍。在真實數據集上與相關的社區搜索算法進行了實驗對比，結果證明了所提算法的有效性和可行性。

關鍵詞：異質網絡；Truss；社區搜索；關鍵詞屬性；元路徑；元結構

中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695（2023）06-017-1708-07

doi： 10.19734/j.issn.1001-3695.2022.10.0512

Truss community search based on keyword attributes over heterogeneous networks

Yang Chengbo Zhou Lihua Huang Yaqun Yang Yudi

（1.School of Information Science amp; Engineering， Yunnan University， Kunming 650500， China; 2.Dianchi College of Yunnan University， Kunming 650228， China）

Abstract：

Community search， as an important research content of social network analysis， aims to find densely connected subgraphs that highly relate to the query node given by users. Most community search methods currently available focus on homogeneous networks. However， in reality， information networks are often attribute-heterogeneous. This paper proposed P-distance and S-distance based on meta-path P and meta-structure S in heterogeneous networks， as well as （k，d，P）-truss and （k，d，S）-truss community models， to measure the structural cohesion of subgraphs. Additionally， it proposed a keyword attribute score function to measure the keyword attribute correlation of different subgraphs， and presented algorithms which could find communities with the highest keyword attribute score of （k，d，P）-truss and （k，d，S）-truss. Search algorithms could find a personalized community with both structural cohesion and keyword attribute correlation， and support to limit the maximum distance d between the query node and any node in the community to control the scope of community search. Compared with the related community search algorithms on real-world datasets， the experimental results prove the effectiveness and feasibility of the proposed algorithms.

Key words：heterogeneous networks; Truss; community search; keyword attributes; meta-path; meta-structure

0 引言

隨著科學技術的迅猛發展，許多領域都會產生大量的信息網絡，如學術合作網絡、社交信息網絡、電影評分網絡等。網絡中的節點用于描述數據對象，邊用于描述數據對象之間的復雜關系。社區作為信息網絡的一個重要屬性，本質上是一個密集連接的連通子圖，社區內的節點連接緊密，而社區間的節點連接稀疏。社區搜索（community search，CS）［1～3］是社會網絡分析的一個重要研究方向，其目標是從信息網絡中根據用戶指定的查詢節點搜索出與該節點相關性較高的聯通子圖。目前，社區搜索已經被應用到推薦系統［4］、生物數據分析［5］和活動組織［6］等不同的現實世界場景中。社區搜索問題由Sozio等人［6］在2010年首次提出，之后研究人員對該問題進行了廣泛研究，并提出了多種社區搜索方法。許多方法［6～9］利用k-core［10］、k-truss［11］和k-clique［12］等結構度量社區的結構內聚性，其中k-core要求子圖中每個節點的度數至少為k；k-truss要求子圖中每條邊至少被包含在k-2個三角形中；k-clique要求子圖的節點個數為k且子圖中每對節點都有邊相連，內聚性越高說明社區內的節點連接越緊密。Fang等人［1］指出k-core、k-truss和k-clique的結構內聚性依次遞增，但計算效率依次遞減。基于k-core、k-truss和k-clique的方法僅考慮了社區的結構內聚性，為了充分利用信息網絡中節點的屬性信息，一些研究者對社區搜索提出了更多的約束，要求搜索的社區同時具有結構內聚性和屬性相關性，例如基于位置屬性的方法［13］、基于影響力屬性的方法［14］和基于關鍵詞屬性的方法［15，16］。

異質信息網絡社區搜索根據用戶輸入的查詢節點搜索出與查詢節點類型相同且緊密連接的節點集作為目標社區。為此，Fang等人［17］利用元路徑捕獲異質信息網絡的語義信息，將k-core與元路徑結合設計了適用于異質網絡的內聚子圖結構（k，P）-core，并基于（k，P）-core提出了FastBCore等一系列的社區搜索方法。（k，P）-core只考慮了社區的結構內聚性，沒有考慮社區的屬性相關性，Qiao等人［18］提出了異質信息網絡中以關鍵詞為中心的社區搜索問題，設計了kKP-core結構，要求連接社區內節點的元路徑實例都要包含給定的關鍵詞，以提升社區的屬性相關性，同時設計了Basic-kKP-core等以關鍵詞為中心的搜索方法。由于k-core的結構內聚性較弱， FastBCore和Basic-kKP-core等算法搜索到的社區結構內聚性還可以進一步提高。為了在屬性異質網絡中搜索結構內聚性和屬性相關性都高的社區，本文提出了異質信息網絡中基于關鍵詞屬性的社區搜索問題。該問題存在如下挑戰：a）如何保證社區具有較高的結構內聚性；b）如何度量不同社區的屬性相關性，將屬性相關性最高的內聚子圖作為社區搜索的結果。對于挑戰a），本文將k-truss與元路徑結合設計了適用于異質網絡的內聚子圖結構（k，d，P）-truss，利用元路徑捕獲異質網絡中的語義信息，不僅繼承了k-truss的高內聚性，還支持限制查詢節點與社區內任意節點的最大距離來控制社區搜索的范圍；對于挑戰b），本文設計了一個關鍵詞屬性得分函數，用于度量不同社區與查詢關鍵詞屬性的相關性，然后將（k，d，P）-truss和關鍵詞屬性得分函數結合提出了基于關鍵詞屬性的元路徑Truss社區（keyword-based meta-path truss community，KPTC）模型。相對于Qiao等人［18］提出的以關鍵詞為中心的Basic-kKP-core方法，該模型同時兼顧了社區的結構內聚性和關鍵詞屬性相關性，在保證社區具有較高結構內聚性的同時使得社區內盡可能多的節點都與查詢關鍵詞相關。由于元路徑的結構單一，在捕獲復雜的語義信息時往往受限，而由多條元路徑融合而成的元結構能夠方便地捕獲復雜語義信息。為了進一步提升社區的語義信息，本文設計了（k，d，S）-truss內聚子圖結構，并將其與關鍵詞屬性得分函數結合提出了基于關鍵詞屬性的元結構Truss社區（keyword-based meta-structure truss community，KSTC）模型。

本文的主要貢獻如下：a）設計了（k，d，P）-truss和（k，d，S）-truss內聚子圖結構度量社區的結構內聚性，同時設計了關鍵詞屬性得分函數來度量社區的關鍵詞屬性相關性；b）將（k，d，P）-truss和（k，d，S）-truss分別與關鍵詞屬性得分函數結合，提出了KPTC和KKSTC模型，并設計了KPTC和KSTC算法用于識別具有最大關鍵詞屬性得分的（k，d，P）-truss和（k，d，S）-truss。在五個真實數據集IMDB、Foursquare、Freebase、DBLP和S-DBLP上進行了大量的實驗，實驗結果證明了本文方法的有效性和可行性。

1 相關工作

1.1 基本概念

1.2 異質信息網絡中基于關鍵詞屬性的社區搜索問題定義

在異質信息網絡G={V，E}中，給定一個查詢節點q∈V和一組查詢關鍵詞Kq，將查詢節點的類型稱為目標類型，基于關鍵詞屬性的社區搜索問題是要找到一個包含查詢節點并且同時具有結構內聚性和關鍵詞屬性相關性的同質社區，社區內所有節點的類型都與目標類型相同。解決上述問題的關鍵在于如何從異質信息網絡中搜索具有高內聚性的子圖，并從搜索出的內聚子圖中選擇和查詢關鍵詞相關性最高的子圖作為社區。

2 KPTC與KSTC模型

2.1 內聚子圖結構

為了能夠從異質信息網絡中搜索出包含查詢節點且具有高內聚性的子圖，本節提出了（k，d，P）-truss和（k，d，S）-truss內聚子圖結構來度量社區的結構內聚性。

2.1.1 （k，d，P）-truss

目前，已經存在許多應用于同質信息網絡的內聚子圖結構，如k-core、k-truss、k-clique等，其中Cohen［11］提出的k-truss已經被證明了具有較高的內聚性和計算效率，但是k-truss不能直接用于度量異質信息網絡中同質社區的內聚性，因為異質信息網絡中相同類型的節點往往沒有直接相連。為了使k-truss能夠適用于異質信息網絡，Yang等人［22］利用元路徑來捕獲異質信息網絡中的語義信息和連接兩個相同類型節點，將元路徑和k-truss結合提出了（k，P）-Btruss內聚子圖結構，其定義如下：

2.1.2 （k，d，S）-truss

2.2 關鍵詞屬性得分函數

3 異質信息網絡中基于關鍵詞屬性的社區搜索算法

4 實驗與結果

本文采用多種評價指標在真實的異質信息網絡數據集上驗證KPTC和KSTC算法的有效性和效率。首先在IMDB、Foursquare、Freebase和DBLP數據集上比較了算法搜索結果的PathCount、PathSim、直徑和密度；其次在 S-DBLP數據集上通過F₁分數評估了算法搜索結果的質量；最后研究了參數變化和數據集的大小對算法運行時間的影響。

4.1 實驗環境和數據集

本文算法都用Java語言實現，所有實驗都是在Ubuntu 16.04.6，2.50 GHz四核CPU，16 GB內存的Linux系統上進行。

實驗使用了五個真實的數據集，分別是IMDB、Foursquare、Freebase、DBLP和S-DBLP。IMDB是由2000年以來的電影評價記錄組成的星型結構數據集，包含演員（actor）、導演（director）、作家（writer）和電影（movie）四種對象類型和三種關系類型；Foursquare是由用戶在美國的簽到記錄組成，包含簽到場所（venue）、場所類別（category）、城市（city）、日期（date）和用戶（user）五種對象類型和四種關系類型；Freebase是由音樂領域中的多種對象類型和關系類型組成的數據集；DBLP是由計算機領域的出版記錄組成的網狀結構數據集，包含作者（author）、論文（paper）、會議或期刊（venue）和時間（time）四種對象類型和三種關系類型；S-DBLP是DBLP的小型子數據集，該數據集由2017—2020年數據庫、數據挖掘、信息檢索和人工智能四個領域的主要會議的論文組成，根據作者發表的論文所屬領域，將至少發表過三篇同一領域論文的作者劃分成四個真實社區，可以通過對比不同社區搜索算法在S-DBLP上運行所得結果的F₁分數來評估搜索算法的質量。五個數據集的詳細描述如表1所示。

4.2 算法的有效性評估

4.2.1 社區質量的評估

a）PathCount定義為社區中兩個節點之間形成的元路徑或元結構實例數，它能夠評估異質信息網絡中社區內節點間的緊密度。PathCount的值越大，表示連接兩個節點的實例數越多，兩個節間的聯系就越緊密。圖4是三種算法分別在不同數據集上輸入100個不同的搜索條件所得社區的平均PathCount值。Basic-kKP-core所得社區的平均PathCount值低于KPTC和KSTC所得社區的平均PathCount值，這是因為Basic-kKP-core的搜索條件是最嚴格的，它要求連接社區內任意兩個節點間的元路徑實例必須包含查詢關鍵詞，而KPTC和KSTC只要求所得社區的關鍵詞得分最高，不要求連接社區內任意兩個節點的元路徑或元結構實例包含查詢關鍵詞。

b）PathSim是Sun等人［19］提出并用來評估社區內節點間在結構上的相似性，PathSim值越接近1，節點間相似度越高。圖5是三種算法分別在不同數據集上輸入100個不同的搜索條件所得社區的平均PathSim值。KPTC和KSTC所得社區的平均PathSim值高于Basic-kKP-core所得社區的平均PathSim值，因此KPTC和KSTC所得社區內節點間的相似性更高。

c）直徑。同質信息網絡社區搜索中常用直徑來度量社區的緊密度，直徑定義為社區中任意兩個節點之間的最大最短距離。為了能夠適用于異質信息網絡中的社區，將直徑重新定義為社區中連接任意兩個節點的最短元路徑或元結構實例鏈的最大長度。圖6是三種算法分別在不同數據集上輸入100個不同的搜索條件所得社區的平均直徑。KPTC和KSTC所得社區的平均直徑低于Basic-kKP-core所得社區的平均直徑，原因是KPTC和KSTC可以通過調整參數d來控制社區的搜索規模，而Basic-kKP-core需要進行全局搜索，因此KPTC和KSTC所得社區的直徑更短，社區內節點之間的關系更密切。

d）密度。通常同質信息網絡中社區的密度定義為邊的數量除以節點的數量。為了能夠適用于異質信息網絡中的社區，將密度重新定義為社區中節點間形成的元路徑或元結構實例的數量除以節點的數量。圖7是三種算法分別在不同數據集上輸入100個不同的搜索條件所得社區的平均密度。KPTC和KSTC所得社區的平均密度高于Basic-kKP-core所得社區的平均密度，因此KPTC和KSTC所得社區內的節點之間連接更緊密。

e）F₁分數。社區搜索研究工作常通過對比不同搜索方法結果的F₁分數來評估搜索方法的質量，社區的F₁分數是準確率和召回率的加權平均值。本文從S-DBLP數據集的每個真實社區中隨機選取10個作者作為查詢節點，將作者所屬領域作為查詢關鍵詞，將元路徑設置為APA，然后在S-DBLP上運行KPTC、KSTC、（k，P）-core及其變種（k，P）-core和Basic-kKP-core及其變種Basic-kKP-core方法各50次并計算F₁分數的平均值，實驗結果如表2所示。從表2可以發現，六種方法中（k，P）-core的召回率是最高的，但是其F₁分數是最低的，因為該方法僅考慮了社區的結構內聚性，只保證結果的召回率，而沒有保證準確率，在搜索時會將許多其他領域社區的節點包括在結果社區內；（k，P）-core在（k，P）-core的基礎上考慮了關鍵詞屬性的相關性，F₁分數有了明顯的提升；Basic-kKP-core的準確率是最高的，而F₁分數明顯低于KPTC和KSTC，該方法注重結果的準確率，在搜索時要求連接社區中任意一對節點的元路徑實例都要包含給定的查詢關鍵詞，意味著社區內的節點都是和查詢節點同一領域的，但是這并不能保證結果的召回率，因為真實社區中有的節點之間是通過其他領域節點連接的；Basic-kKP-core的F₁分數相較于Basic-kKP-core出現了略微的下降，這是因為在提升了Basic-kKP-core的結構內聚性之后，在搜索時會過濾掉一些滿足k-core但不滿足k-truss要求的節點；KPTC和KSTC的F₁分數明顯高于其他方法，并且隨著參數d的增大，結果的準確率出現下降且召回率增大，原因是它們在保證社區結構內聚性的同時選擇和查詢關鍵詞相關性最高的社區，讓盡可能多的與查詢關鍵詞相關的節點包含在結果社區中，這樣同時保證了結果的準確率和召回率都不會非常低；KSTC的F₁分數相較于KPTC的F₁分數有所降低，原因是KSTC使用元結構來捕獲更精確的語義信息，在搜索時條件更嚴格，從而導致了社區的召回率降低。

4.2.2 應用案例

4.3 算法的效率評估

為了評估KPTC和KSTC算法的運行效率，分別在IMDB、Foursquare、Freebase和DBLP數據集上進行了相應的實驗。

a）在DBLP數據集上分別進行了在不同正整數k和不同正整數d情況下的實驗。實驗結果如圖8所示。觀察實驗結果可以發現，算法的運行時間隨著k的增大在緩慢降低，原因是k越大，能夠滿足（k，d，P）-truss和（k，d，S）-truss結構的節點就越少，也就過濾掉了更多的節點，使得運行時間減少；算法的運行時間與d的大小成正比，原因是隨著d的增大，會搜索到更多的節點，算法需要耗費更多的時間去計算節點的支持度和關鍵詞屬性得分；KPTC的運行時間總是比KSTC算法多，原因是元結構相比元路徑結構更復雜，在搜索元結構時需要耗費更多的時間。

b）分別隨機抽取了IMDB、Foursquare、Freebase和DBLP數據集20%、40%、60%、80%和100%的節點生成子數據集，并在這些不同規模的數據集上評估了KPTC和KSTC算法的運行時間，實驗結果如圖9所示。可以看出，兩個算法的運行時間都隨著數據集規模的增加而增長，數據集的規模越大，算法需要處理的節點就越多，算法的運行時間也會隨之增加。

5 結束語

本文主要研究異質信息網絡中基于關鍵詞屬性的社區搜索問題，利用元結構和元路徑捕獲異質信息網絡中豐富的語義信息，定義了（k，d，P）-truss與（k，d，S）-truss兩個內聚子圖結構和關鍵詞屬性得分函數；其次提出了KPTC和KSTC兩個社區模型并設計了相應的算法；最后在五個真實數據集上對本文算法進行了效果和效率的評估。

本文社區搜索算法需要用戶指定k和d兩個參數，這對于不太熟悉網絡的用戶而言是一個比較困難的任務。在未來工作中，將考慮引入深度學習中的注意力機制等技術自適應地選擇最佳參數，同時引入異質圖神經網絡來提取更全面的異質信息。

參考文獻：

［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］竺俊超，王朝坤. 復雜條件下的社區搜索方法 ［J］. 軟件學報，2019，30（3）： 552-572. （Zhu Junchao，Wang Chaokun. Approaches to community search under complex conditions ［J］. Journal of Software，2019，30（3）： 552-572.）

［3］顧天凱，王朝坤，樓昀愷. 時序網絡中短時社區搜索方法研究 ［J］. 計算機學報，2022，45（2）： 334-353. （Gu Tiankai，Wang Chaokun，Lou Yunkai. Research on short-time community search in temporal networks ［J］. Chinese Journal of Computers，2022，45（2）： 334-353. ）

［4］Sourabh V，Chowdary C R. Peer recommendation in dynamic attributed graphs ［J］. Expert Systems with Applications，2019，120（4）： 335-345.

［5］Pesántez-Cabrera P，Kalyanaraman A. Efficient detection of communities in biological bipartite networks ［J］. IEEE/ACM Trans on Computational Biology and Bioinformatics，2017，16（1）：258-271.

［6］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.

［7］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.

［8］Cui Wanyun，Xiao Yanghua，Wang Haixun，et al. Online search of overlapping communities ［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press，2013： 277-288.

［9］Huang Xin，Cheng Hong，Qin Lu，et al. Querying k-truss community in large and dynamic graphs ［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press，2014： 1311-1322.

［10］Batagelj V，Zaversnik M. An O（m） algorithm for cores decomposition of networks ［EB/OL］. （2003-10-25）. https：//arxiv.org/pdf/cs/0310049.pdf.

［11］Cohen J. Trusses： cohesive subgraphs for social network analysis ［J］. National Security Agency Technical Report，2008，16（3）：1-29.

［12］Palla G，Derényi I，Farkas I，et al. Uncovering the overlapping community structure of complex networks in nature and society ［J］. Nature，2005，435（7043）： 814-818.

［13］Fang Yixiang，Wang Zheng，Cheng R，et al. On spatial-aware community search ［J］. IEEE Trans on Knowledge and Data Enginee-ring，2018，31（4）： 783-798.

［14］Zheng Zibin，Ye Fanghua，Li Ronghua，et al. Finding weighted k-truss communities in large networks ［J］. Information Sciences，2017，417（11）： 344-360.

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

［16］李青青，馬慧芳，李舉，等. 屬性網絡中相似性增強隨機游走的多社區搜索 ［J］. 電子學報，2021，49（11）： 2096-2100. （Li Qingqing，Ma Huifang，Li Ju，et al. Multi-community search using similarity enhanced random walk in attributed networks ［J］. Acta Electronica Sinica，2021，49（11）： 2096-2100. ）

［17］Fang Yixiang，Yang Yixing，Zhang Wenjie，et al. Effective and efficient community search over large heterogeneous information networks ［J］. Proceedings of the VLDB Endowment，2020，13（6）：854-867.

［18］Qiao Lianpeng，Zhang Zhiwei，Yuan Ye，et al. Keyword-centric community search over large heterogeneous information networks ［C］// Proc of the 26th International Conference on Database Systems for Advanced Applications. Cham： Springer，2021： 158-173.

［19］Sun Yizhou，Han Jiawei，Yan Xifeng，et al. PathSim： meta path-based top-k similarity search in heterogeneous information networks ［J］. Proceedings of the VLDB Endowment，2011，4（11）： 992-1003.

［20］Huang Zhipeng，Zheng Yudian，Cheng R，et al. Meta structure： computing relevance in large heterogeneous information networks ［C］// Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2016：1595-1604.

［21］Zhao Huan，Yao Quanming，Li Jianda，et al. Meta-graph based recommendation fusion over heterogeneous information networks ［C］// Proc of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2017：635-644.

［22］Yang Yixing，Fang Yixiang，Lin Xuemin，et al. Effective and efficient truss computation over large heterogeneous information networks ［C］// Proc of the 36th IEEE International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2020： 901-912.

［23］陳亦琦，錢鐵云，李萬理，等. 基于復合關系圖卷積的屬性網絡嵌入方法 ［J］. 計算機研究與發展，2020，57（8）： 1674-1682. （Chen Yiqi，Qian Tieyun，Li Wanli，et al. Exploiting composite relation graph convolution for attributed network embedding ［J］. Journal of Computer Research and Development，2020，57（8）： 1674-1682.）

［24］Sun Yizhou，Barber R，Gupta M，et al. Co-author relationship prediction in heterogeneous bibliographic networks ［C］// Proc of International Conference on Advances in Social Networks Analysis and Mi-ning. Washington DC： IEEE Computer Society，2011： 121-128.

［25］Huang Xin，Lakshmanan L V，Yu J X，et al. Approximate closest community search in networks ［J］. Proceedings of the VLDB Endowment，2015，9（4）： 276-287.

［26］Wu Yubao，Jin Ruoming，Li Jing，et al. Robust local community detection： on free rider effect and its elimination ［J］. Proceedings of the VLDB Endowment，2015，8（7）： 798-809.