帶有節(jié)點(diǎn)屬性的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法綜述

帶有節(jié)點(diǎn)屬性的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法綜述社區(qū)發(fā)現(xiàn)算法綜述動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法綜述ChunaevP.Communitydetectioninnode-attributedsocialnetworks:asurvey[J].ComputerScienceReview,2020,37:100286.一、背景介紹??文章首先指出社區(qū)發(fā)現(xiàn)（communitydetection）是社交網(wǎng)絡(luò)分析中的一個(gè)基本問題。一類經(jīng)典的社區(qū)發(fā)現(xiàn)方法是僅處理網(wǎng)絡(luò)的結(jié)構(gòu)（即節(jié)點(diǎn)之間的聯(lián)系），而忽略節(jié)點(diǎn)的特征。然而，大多數(shù)現(xiàn)實(shí)世界的社交網(wǎng)絡(luò)提供了更多關(guān)于參與者的信息，而不僅僅是他們之間的聯(lián)系。當(dāng)存在參與者的信息時(shí)，網(wǎng)絡(luò)被稱為是有節(jié)點(diǎn)屬性的（node-attributed）。另一類經(jīng)典的社區(qū)發(fā)現(xiàn)方法是只使用節(jié)點(diǎn)屬性來發(fā)現(xiàn)社區(qū)，完全忽略參與者之間的聯(lián)系，代表方法有k-means聚類算法。顯然，只處理結(jié)構(gòu)或只處理屬性的方法不能夠完全利用網(wǎng)絡(luò)中所有的可用信息。因此，研究能同時(shí)利用結(jié)構(gòu)和屬性的社區(qū)發(fā)現(xiàn)方法成為社會(huì)網(wǎng)絡(luò)分析的一個(gè)新領(lǐng)域。??其次，文章提到了在過去的十年中，該領(lǐng)域出現(xiàn)了許多基于不同的思想和技術(shù)的方法。文章的目的是描述和闡明該領(lǐng)域的總體情況。此外，文章還提出了一種基于何時(shí)以及如何使用和融合網(wǎng)絡(luò)結(jié)構(gòu)和屬性的分類方法，并給出了每個(gè)類的描述以及每個(gè)方法背后的一般技術(shù)思想。進(jìn)一步地，文章還關(guān)注哪些方法優(yōu)于其他方法，以及使用哪些數(shù)據(jù)集和質(zhì)量度量來評(píng)估它們的性能。根據(jù)收集到的信息，作者總結(jié)了該領(lǐng)域的現(xiàn)狀，并揭示了幾個(gè)在未來需要解決的重要問題。二、帶有節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題及網(wǎng)絡(luò)結(jié)構(gòu)與屬性融合的影響1.社區(qū)發(fā)現(xiàn)問題陳述??圖1展示了一個(gè)帶有節(jié)點(diǎn)屬性的網(wǎng)絡(luò)。在該網(wǎng)絡(luò)中進(jìn)行社區(qū)發(fā)現(xiàn)需要實(shí)現(xiàn)了以下兩個(gè)屬性之間的某種平衡：（1）結(jié)構(gòu)上的緊密性（structuralcloseness），即一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)在結(jié)構(gòu)上彼此接近，而不同社區(qū)的節(jié)點(diǎn)在結(jié)構(gòu)上不接近；（2）屬性上的同質(zhì)性（attributehomogeneity），即一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)具有同質(zhì)屬性，而不同社區(qū)的節(jié)點(diǎn)沒有。2.結(jié)構(gòu)緊密性和屬性同質(zhì)性，結(jié)構(gòu)與屬性融合的效果??什么是結(jié)構(gòu)緊密型呢？結(jié)構(gòu)緊密性的要求是基于社交網(wǎng)絡(luò)中的社區(qū)的概念。例如在GirvanandNewman(2002)中，社區(qū)被認(rèn)為是節(jié)點(diǎn)的子集，子集內(nèi)部連接緊密，子集之間連接稀疏。一個(gè)常見的度量方法是Newman’sModularity。實(shí)際上，每個(gè)社區(qū)發(fā)現(xiàn)方法中結(jié)構(gòu)緊密性的確切含義是由所選擇的度量方法決定的。??什么是屬性同質(zhì)性呢？屬性同質(zhì)性要求是基于節(jié)點(diǎn)的特征能夠反映和影響社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)的社會(huì)科學(xué)基礎(chǔ)。常見的社交網(wǎng)絡(luò)中的同質(zhì)性原則是志趣相投的節(jié)點(diǎn)更有可能被聯(lián)系起來。屬性同質(zhì)性通常用Entropy來衡量。??接下來文章討論了結(jié)構(gòu)和屬性融合的效果的不同觀點(diǎn)。一方面，多個(gè)實(shí)驗(yàn)和許多論文表明網(wǎng)絡(luò)的結(jié)構(gòu)和屬性往往提供互補(bǔ)的信息，能夠提高社區(qū)發(fā)現(xiàn)質(zhì)量。另一方面，一些實(shí)驗(yàn)表明，這并不總是正確的，網(wǎng)絡(luò)結(jié)構(gòu)和屬性可能是正交的，相互矛盾的，從而導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果不明確。文章認(rèn)為對(duì)于融合結(jié)構(gòu)和屬性的效果以及這種融合如何影響社區(qū)發(fā)現(xiàn)的質(zhì)量，目前還沒有廣泛接受的觀點(diǎn)。關(guān)于結(jié)構(gòu)和屬性的融合何時(shí)對(duì)社區(qū)發(fā)現(xiàn)有價(jià)值以及何時(shí)沒有價(jià)值的理論研究似乎是一件極其重要的事情。三、相關(guān)工作及相關(guān)文獻(xiàn)的整理??作者在這一章總結(jié)了之前關(guān)于社區(qū)發(fā)現(xiàn)綜述的文章存在的問題，并介紹了他們關(guān)于相關(guān)文獻(xiàn)搜索的過程以及方法和數(shù)據(jù)集的引用格式。此外，作者還提出了三點(diǎn)note：（1）本次調(diào)查不考慮多層網(wǎng)絡(luò)（multi-layernetworks）的社區(qū)發(fā)現(xiàn)方法；（2）本次調(diào)查主要考慮利用全屬性空間尋找覆蓋整個(gè)網(wǎng)絡(luò)的社區(qū)的方法，不考慮探索屬性的子空間和處理初始圖的子圖的方法；（3）本次調(diào)查不考慮文獻(xiàn)網(wǎng)絡(luò)聚類方法。四、對(duì)與帶有節(jié)點(diǎn)屬性的社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法分類??作者根據(jù)社區(qū)發(fā)現(xiàn)過程中的結(jié)構(gòu)和屬性何時(shí)融合來對(duì)方法進(jìn)行分類。如圖2所示，將其分為了三類，分別是：（1）早期融合方法（earlyfusionmethods），即在社區(qū)發(fā)現(xiàn)過程之前融合結(jié)構(gòu)和屬性；（2）同時(shí)融合方法（simultaneousfusionmethods），即在社區(qū)發(fā)現(xiàn)的同時(shí)融合結(jié)構(gòu)和屬性；（3）后期融合方法（latefusionmethods），即首先分別對(duì)結(jié)構(gòu)和屬性進(jìn)行分區(qū)，然后進(jìn)一步融合獲得的分區(qū)。并且在第6-8章針對(duì)上述三個(gè)分類對(duì)其使用的社區(qū)發(fā)現(xiàn)算法、輸入以及輸出的社區(qū)類型（是否重疊）、數(shù)據(jù)集以及評(píng)估方法等方面進(jìn)行了簡(jiǎn)要介紹。五、最常用的帶有節(jié)點(diǎn)屬性的網(wǎng)絡(luò)數(shù)據(jù)集和社區(qū)發(fā)現(xiàn)評(píng)估的質(zhì)量度量1.數(shù)據(jù)集??作者收集并簡(jiǎn)要描述了該領(lǐng)域常用的數(shù)據(jù)集，包含社交網(wǎng)絡(luò)數(shù)據(jù)集（例如Facebook、LastFM和Twitter），引文網(wǎng)絡(luò)數(shù)據(jù)集（例如DBLP、Wiki和專利）等。為了方便起見，作者按照數(shù)據(jù)集中節(jié)點(diǎn)的多少進(jìn)行區(qū)分，劃分為了表1小型數(shù)據(jù)集（<），表2中型數(shù)據(jù)集（），表3大型數(shù)據(jù)集（>）。2.評(píng)估方法??對(duì)于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的結(jié)果，需要評(píng)估它們的質(zhì)量。根據(jù)所使用的數(shù)據(jù)集，可以分為兩種情況。如果該數(shù)據(jù)集沒有真實(shí)的社區(qū)，則可以使用各種結(jié)構(gòu)接近度和屬性同質(zhì)性的度量，例如，模塊度、密度、傳導(dǎo)性、持久性、簇內(nèi)和簇間密度等。如果存在真實(shí)社區(qū)情況，可以通過以下常用的度量方法來將檢測(cè)到的社區(qū)與真實(shí)情況進(jìn)行比較。例如：準(zhǔn)確度、歸一化互信息（NMI）、調(diào)整后的蘭德指數(shù)（ARI）或蘭德指數(shù)（RI）和F度量。六、早期融合方法（Earlyfusionmethods）1.基于權(quán)重的方法（Weight-basedmethods）??這些方法（具體可見文中表4和表5）將屬性轉(zhuǎn)換為加權(quán)屬性圖，并以某種方式將其與結(jié)構(gòu)圖合并。結(jié)果得到一個(gè)加權(quán)圖，它代替了節(jié)點(diǎn)屬性圖，如圖3所示。的邊權(quán)通常分配如下：其中和分別代表結(jié)構(gòu)相似函數(shù)和屬性相似函數(shù)，超參數(shù)控制結(jié)構(gòu)和屬性之間的平衡。??一旦構(gòu)建了加權(quán)圖，就可以在其上使用經(jīng)典的圖聚類算法，例如WeightedLouvain。有時(shí)，會(huì)被轉(zhuǎn)換成一定的距離矩陣，通過基于距離的聚類算法（如k-means或k-medoids）進(jìn)一步用于發(fā)現(xiàn)社區(qū)。??調(diào)試通常是人工執(zhí)行的。相似函數(shù)和的選擇通常是由特定方法的作者的偏好決定的。對(duì)于這種選擇如何影響社區(qū)發(fā)現(xiàn)結(jié)果的系統(tǒng)研究尚待進(jìn)行。2.基于距離的方法（Distance-basedmethods）??前一小節(jié)中討論的方法旨在以統(tǒng)一的圖形式表示結(jié)構(gòu)和屬性，以便于進(jìn)一步的圖聚類。相反，基于距離的方法（具體可見文中表6）有意地放棄圖的表示，而采用包含結(jié)構(gòu)和屬性信息的距離矩陣表示。距離矩陣通常是通過結(jié)構(gòu)和屬性感知的距離函數(shù)融合組件得到的，如圖4所示。矩陣可通過基于距離的聚類算法（如k-means和k-medoids）進(jìn)一步用于發(fā)現(xiàn)社區(qū)。融合結(jié)構(gòu)與屬性的距離函數(shù)通常是如下形式：其中和分別是結(jié)構(gòu)和屬性距離函數(shù)。和(6.1)相同，(6.2)中的控制各組分之間的平衡，如何恰當(dāng)?shù)剡x擇它似乎也是一個(gè)懸而未決的問題3.基于節(jié)點(diǎn)增廣圖的方法（Node-augmentedgraph-basedmethods）??本小節(jié)的方法（具體可見文中表7）將初始節(jié)點(diǎn)屬性圖G轉(zhuǎn)換為另一個(gè)節(jié)點(diǎn)增廣圖，其中節(jié)點(diǎn)來自V和新的代表屬性的屬性節(jié)點(diǎn)，如圖5所示。然后進(jìn)一步在上進(jìn)行社區(qū)發(fā)現(xiàn)。??注意，上述的增廣并不適用于連續(xù)屬性。特別是當(dāng)屬性維度和屬性的取值很多時(shí)，這種方法計(jì)算起來相當(dāng)昂貴。4.基于嵌入的方法（Embedding-basedmethods）??眾所周知，圖作為網(wǎng)絡(luò)的傳統(tǒng)表示形式給網(wǎng)絡(luò)分析帶來了一些困難。新的嵌入技術(shù)旨在通過學(xué)習(xí)節(jié)點(diǎn)嵌入來解決這一問題，即網(wǎng)絡(luò)節(jié)點(diǎn)的低維連續(xù)向量表示，從而有效地編碼主網(wǎng)絡(luò)信息。粗略地說，節(jié)點(diǎn)嵌入技術(shù)允許將一個(gè)有n個(gè)節(jié)點(diǎn)的圖轉(zhuǎn)換成一個(gè)有n個(gè)向量的集合。有了節(jié)點(diǎn)嵌入（即向量），就可以使用經(jīng)典的基于距離的聚類算法，如k-means，來檢測(cè)社區(qū)，見圖6。具體可見文中表8列舉的方法。5.基于模式挖掘（早期融合）方法（Patternmining-based(earlyfusion)methods）??Motif被認(rèn)為是復(fù)雜網(wǎng)絡(luò)的構(gòu)建模塊。我們發(fā)現(xiàn)使用這種模式對(duì)節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)的方法只有一種，即AHMotif(Lietal.,2018)，見文中表9。該方法根據(jù)motif中涉及的節(jié)點(diǎn)屬性，為網(wǎng)絡(luò)中識(shí)別的結(jié)構(gòu)motif配備所謂的同質(zhì)性值。該信息存儲(chǔ)在一個(gè)特殊的鄰接矩陣中，該矩陣可以作為經(jīng)典社區(qū)發(fā)現(xiàn)算法的輸入。七、同時(shí)融合方法（Simultaneousfusionmethods）??同時(shí)融合方法在社區(qū)發(fā)現(xiàn)的過程中同時(shí)融合結(jié)構(gòu)和屬性。由于這個(gè)原因，這些方法通常需要特殊的社區(qū)發(fā)現(xiàn)方法來實(shí)現(xiàn)，而早期和晚期的融合方法在一定程度上允許使用經(jīng)典社區(qū)發(fā)現(xiàn)算法來實(shí)現(xiàn)。1.改進(jìn)經(jīng)典聚類算法的目標(biāo)函數(shù)的方法（Methodsmodifyingobjectivefunctionsofclassicalclusteringalgorithms）??文章中的表10包含了同時(shí)融合方法的簡(jiǎn)短描述，這些方法修改了常用的聚類算法的目標(biāo)函數(shù)，如Louvain、NormalizedCut、k-means、k-medoids和kNN。他們的主要想法是采用經(jīng)典的方法在優(yōu)化過程中同時(shí)使用結(jié)構(gòu)和屬性。2.基于元啟發(fā)式的方法（Metaheuristic-basedmethods）??這類方法在思想上與第7.1節(jié)中的方法相似。然而，他們并沒有修改常用的社區(qū)發(fā)現(xiàn)算法的目標(biāo)函數(shù)和迭代過程，而是直接應(yīng)用元啟發(fā)式算法以找到一個(gè)節(jié)點(diǎn)屬性網(wǎng)絡(luò)分區(qū)，為某些結(jié)構(gòu)緊密度和屬性同質(zhì)性度量提供最優(yōu)值。文中表11給出了這類方法的簡(jiǎn)短描述。3.基于非負(fù)矩陣分解和矩陣壓縮的方法（Methodsbasedonnon-negativematrixfactorizationandmatrixcompression）??非負(fù)矩陣分解（non-negativematrixfactorization，NNMF）是一種矩陣分解技術(shù)，它是用秩較低的非負(fù)矩陣的乘積來近似高秩的非負(fù)矩陣，，從而使Frobenius范數(shù)的近似誤差最小。眾所周知，NNMF能夠在輸入數(shù)據(jù)中找到簇。要將NNMF應(yīng)用于節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)，需要對(duì)結(jié)構(gòu)和屬性進(jìn)行適當(dāng)?shù)娜诤?。有人提出了這種改編的不同版本，見文中表12。4.基于模式挖掘（同時(shí)融合）方法（Patternmining-based(simultaneousfusion)methods）??在節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)中進(jìn)行的模式挖掘主要是在網(wǎng)絡(luò)結(jié)構(gòu)和屬性中提取特定屬性子集或連接子集等模式。除此之外，這有助于理解網(wǎng)絡(luò)并理解它是如何形成的。在社區(qū)發(fā)現(xiàn)的背景下，提取的模式被用作社區(qū)的構(gòu)建塊。相關(guān)方法見文中表13。5.基于概率模型的方法（Probabilisticmodel-basedmethods）??在假設(shè)網(wǎng)絡(luò)結(jié)構(gòu)和屬性是根據(jù)選定的參數(shù)分布生成的情況下，該類方法從概率上推斷節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)中節(jié)點(diǎn)的社區(qū)成員分布。生成模型和判別模型主要用于推理。值得一提的是，正確選擇結(jié)構(gòu)和屬性的先驗(yàn)分布是一項(xiàng)非常重要的任務(wù)。表14給出了這類方法的簡(jiǎn)短描述。6.基于動(dòng)態(tài)系統(tǒng)和基于代理的方法（Dynamicalsystem-basedandagent-basedmethods）??該類方法（見文中表15）將節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)視為一個(gè)動(dòng)態(tài)系統(tǒng)，并假設(shè)其社區(qū)結(jié)構(gòu)是節(jié)點(diǎn)之間某些交互的結(jié)果。有些方法假設(shè)交互發(fā)生在信息傳播過程中，即當(dāng)信息發(fā)送到或從每個(gè)節(jié)點(diǎn)接收時(shí)。其他方法將每個(gè)節(jié)點(diǎn)理解為一個(gè)自治的代理，并開發(fā)一個(gè)多代理系統(tǒng)來檢測(cè)社區(qū)。需要注意的是，這些方法都是最近才出現(xiàn)的，從一個(gè)新的角度考慮了節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)。此外，它們對(duì)于大型網(wǎng)絡(luò)似乎是有效的，因?yàn)榭梢院苋菀椎夭⑿谢?。八、后期融合方法（Latefusionmethods）??后期融合方法旨在社區(qū)發(fā)現(xiàn)過程之后融合結(jié)構(gòu)和屬性信息。更準(zhǔn)確地說，社區(qū)發(fā)現(xiàn)首先針對(duì)結(jié)構(gòu)（例如Louvain）和屬性（例如k-means）分別執(zhí)行。之后，獲得的分區(qū)以某種方式融合以獲得結(jié)構(gòu)和屬性感知分區(qū)，如圖7所示。后期融合方法通常允許研究人員/數(shù)據(jù)科學(xué)家使用經(jīng)典社區(qū)發(fā)現(xiàn)和共識(shí)聚類算法的現(xiàn)有實(shí)現(xiàn)來獲得所需的分區(qū)。1.基于共識(shí)的方法（Consensus-basedmethods）??給定一組分區(qū)，共識(shí)聚類算法的一般目標(biāo)是找到一個(gè)單一的合并分區(qū)，該分區(qū)聚合集合中的信息。如果一個(gè)人有一組單獨(dú)（甚至聯(lián)合）的結(jié)構(gòu)和屬性分區(qū)，共識(shí)聚類背后的想法顯然適用于節(jié)點(diǎn)屬性社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)。表16包含了應(yīng)用該思想的方法的簡(jiǎn)短描述。2.基于替換的方法（Switch-basedmethods）??這類方法中包含的唯一方法（見文中表17）也是處理根據(jù)結(jié)構(gòu)和屬性分別獲得的分區(qū)，但不同的是選擇更可取的分區(qū)而不是尋找共識(shí)。即當(dāng)結(jié)構(gòu)分區(qū)不明確時(shí)，方法從基于結(jié)構(gòu)的分區(qū)切換到基于屬性的分區(qū)。九、整體情況分析??作者使用PageRank來尋找該領(lǐng)域最有影響力的方法。如圖8所示，綠色越深表示該節(jié)點(diǎn)的PageRank越高。作者認(rèn)為這些方法可能會(huì)被研究人員進(jìn)一步研究?；跈?quán)重的SAC2和CODICIL基于節(jié)點(diǎn)增強(qiáng)圖的SA-Cluster、Inc-Cluster和SA-Cluster-Opt修改Louvain目標(biāo)函數(shù)的SAC1基于NNMF的SCI和基于矩陣壓縮的PICS基于模式挖掘（同時(shí)融合）的DCM基于概率模型的PCL-DC、BAGC、GBAGC、CESNA和Circles??從圖8中，可以看出網(wǎng)絡(luò)是相當(dāng)稀疏甚至是不連貫的。說明該領(lǐng)域的方法的比較研究還遠(yuǎn)未完成。接下來將從幾個(gè)角度對(duì)方法評(píng)估問題進(jìn)行討論。（1）假設(shè)兩種方法對(duì)許多數(shù)據(jù)集和度量顯示相同的社區(qū)發(fā)現(xiàn)質(zhì)量，提出應(yīng)該考慮每種方法使用多少時(shí)間/空間。特別地，作者提出可以根據(jù)節(jié)點(diǎn)屬性圖中的頂點(diǎn)數(shù)、邊數(shù)和屬性維數(shù)來考慮方法的計(jì)算復(fù)雜度。但目前論文的作者經(jīng)常省略對(duì)復(fù)雜度的估計(jì)。這使得無法在計(jì)算復(fù)雜度方面對(duì)各種方法進(jìn)行整體比較。（2）作者使用不同的數(shù)據(jù)集和評(píng)估措施來測(cè)試他們的方法，因此無法對(duì)不同論文中的實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)一比較。并且很多論文沒有提供源代碼，使結(jié)果復(fù)現(xiàn)成為難題。（3）作者在文中討論了具體的評(píng)估方法，并且按照有沒有真實(shí)的社區(qū)結(jié)構(gòu)，劃分為了兩種評(píng)估策略。并分別對(duì)兩種評(píng)估策略目前的發(fā)展和存在的問題進(jìn)行了闡述。十、結(jié)論??本文對(duì)帶有節(jié)點(diǎn)屬性的社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)方法進(jìn)行研究，簡(jiǎn)要描述了75種