基于FIUHM模型的興趣社區(qū)檢測方法研究

收稿日期：2020-04-20

基金項目：安徽省高校人文社會科學重點項目“大數(shù)據(jù)背景下醫(yī)療糾紛事件的語義識別及其對網(wǎng)絡(luò)輿情預警影響的研究”（項目編號：SK2018A1064）。

作者簡介：王凱（1985-），男，講師，碩士，研究方向：社會網(wǎng)絡(luò)分析。

摘 要：[目的/意義]構(gòu)建基于用戶興趣標簽的網(wǎng)絡(luò)社團識別模型（Fuzzy Interests and User Hybrid Model，F(xiàn)IUHM），揭示用戶興趣與社團形式概念間的模糊層級關(guān)系，實現(xiàn)多粒度屬性與社團拓撲結(jié)構(gòu)的層次聚類。[方法/過程]通過抽取豆瓣電影社區(qū)數(shù)據(jù)，實現(xiàn)基于用戶標簽的興趣強度語義標注，利用用戶相似度，獲取社區(qū)用戶間興趣語義距離;將網(wǎng)絡(luò)社區(qū)的領(lǐng)接矩陣映射為社團形式背景，構(gòu)建社團模糊概念格，建立社團形式概念及其偏序關(guān)系集，完成社團形式概念建模;通過計算社團穩(wěn)定指數(shù)，識別網(wǎng)絡(luò)社團邊界，并聚類最大獨立社團，實現(xiàn)興趣社團的在線檢測。[結(jié)果/結(jié)論]通過對比實驗，驗證了FIUHM模型的有效性，實驗表明將模糊形式概念分析引入網(wǎng)絡(luò)社團識別研究，利用模糊概念格的偏序關(guān)系建模用戶節(jié)點間的興趣相似度，有利于提高社團識別的分辨率。

關(guān)鍵詞：FIUHM模型;興趣社區(qū);模糊形式概念分析;社團識別;穩(wěn)定指數(shù);社團形式概念

DOI：10.3969/j.issn.1008-0821.2021.01.005

〔中圖分類號〕TP391 〔文獻標識碼〕A 〔文章編號〕1008-0821（2021）01-0039-11

Research on Interest Community Detection Based on FIUHM

Wang Kai

（School of Health Management，Bengbu Medical College，Bengbu 233000，China）

Abstract：[Purpose/Significance]This paper builds a network community recognition model（FIUHM）based on user interest tags，which reveals the fuzzy hierarchical relationship between user interest and community formal concepts.The aim is to realize hierarchical clustering of multi-granularity attributes and community topology.[Method/Process]By extracting Douban movie community data，this paper implemented semantic annotation based on the interest intensity of user tags.The semantic distance among community users was obtained by calculating user similarity.Afterwards，the community matrix of the online community was mapped to the community formal context，based on which the fuzzy concept lattice of the community was constructed.Meanwhile，the community formal concepts and their partial order relation set were established.Finally，the boundary of the online community can be identified by computing the community stability index as well as clustering the largest independent community，to achieve the online detection of the interest community.[Result/Conclusion]The validity of the FIUHM model was evaluated through comparative experiments.The experiments showed that it was helpful to combine the partial order relationship of fuzzy concept lattices and the interest similarity between user nodes，which improved the resolution of community identification.

Key words：FIUHM model;interest community;fuzzy formal concept analysis;community identification;stability index;community formal concept

伴隨著信息通信技術(shù)的快速發(fā)展，以Facebook、Twitter為代表的社交網(wǎng)絡(luò)日漸成為人們資訊傳遞、情感交流的主要信息載體。社交網(wǎng)絡(luò)中用戶往往依據(jù)自身的興趣，找尋與其具有相似偏好的“好友圈”或“推薦社區(qū)”，從而逐漸形成社會性網(wǎng)絡(luò)（Social Network）。社會性網(wǎng)絡(luò)可以依據(jù)其內(nèi)部成員間邊連接的緊密程度，劃分成多個具有不同網(wǎng)絡(luò)拓撲的社團結(jié)構(gòu)[1]。因此，從海量文本中挖掘用戶的興趣特征，構(gòu)建面向用戶興趣屬性的社區(qū)檢測模型，已成為改善資源推薦質(zhì)量、提升社區(qū)服務(wù)精準度的關(guān)鍵。

多數(shù)背景下，社交網(wǎng)絡(luò)中興趣社區(qū)是由某些具有相似興趣愛好的用戶所構(gòu)成的社會群體，興趣是網(wǎng)絡(luò)社區(qū)形成的內(nèi)在誘因。網(wǎng)絡(luò)社區(qū)往往隨著用戶的“興趣漂移”而不斷變化。考慮到用戶興趣的多樣性與差異性，不同興趣社區(qū)間可能存在重疊用戶。此外，由于興趣本身的不確定性，興趣社區(qū)的識別需要解決用戶聚類的模糊性建模問題。

本文提出一種基于FIUHM模型的興趣社區(qū)識別方法，該方法將模糊形式概念分析（Fuzzy Formal Concept Lattice，F(xiàn)FCA）引入興趣社區(qū)的建模中，以用戶自定義標簽為基礎(chǔ)，利用用戶間的模糊關(guān)系聚類，動態(tài)刻畫社區(qū)用戶之間的興趣聚集程度;建模面向多粒度視角的興趣社區(qū)模糊概念格，實現(xiàn)網(wǎng)絡(luò)社團的模糊結(jié)構(gòu)識別;通過計算社團穩(wěn)定指數(shù)，識別網(wǎng)絡(luò)社團邊界，并聚類最大獨立社團，實現(xiàn)社交網(wǎng)絡(luò)的在線檢測。

1 相關(guān)研究概述

社交網(wǎng)絡(luò)是由對象節(jié)點集及邊集所構(gòu)成的虛擬社區(qū)。網(wǎng)絡(luò)社團是通過網(wǎng)絡(luò)中隱藏的關(guān)聯(lián)關(guān)系，將社交網(wǎng)絡(luò)劃分為若干具有現(xiàn)實意義的子社區(qū)[2]。網(wǎng)絡(luò)社團的內(nèi)部節(jié)點間聯(lián)系較緊密，而外部節(jié)點間的關(guān)聯(lián)則相對稀疏。真實網(wǎng)絡(luò)中，不同社團中可能包含重復的用戶節(jié)點以及相互包含的關(guān)系，由此衍生出重疊社團。社區(qū)檢測技術(shù)依據(jù)是否具備重疊社團的檢測能力，可分為非重疊社區(qū)檢測算法和重疊社區(qū)檢測算法。非重疊社區(qū)檢測算法假設(shè)用戶節(jié)點僅屬于單一社團，即社團間不存在交集。該類算法可大致分為基于模塊度的方法[3-4]、基于譜分析的方法[5-6]以及基于標號傳播的方法[7-8]。比較具有代表性的算法有Newman M E J[9]算法、Donetti L等[10]算法、Raghavan U N等[11]。該類算法雖然優(yōu)化了算法的時間復雜度，但社團劃分未考慮到社團固有的層次性以及節(jié)點間的屬性相似性，使得識別結(jié)果缺乏必要的可解釋性。

隨著研究的深入，重疊社團因其具有的現(xiàn)實意義而逐漸成為人們研究的熱點，該類算法大致可分為基于局部延展的方法[12]、基于聚類的方法[13]以及基于團滲透的方法[14]。首先，基于局部延展的方法主要通過定義節(jié)點適應(yīng)度評價函數(shù)或密度函數(shù)，對社團種子節(jié)點及其相鄰節(jié)點進行合并操作，以獲取局部最優(yōu)的社團函數(shù)，代表性算法包括LFM[15]、FMMN[16]等。該類方法由于過度依賴初始節(jié)點以及延展決策函數(shù)，容易引起局部最優(yōu)。其次，基于聚類的方法將重疊社團的劃分視為加權(quán)線圖中的共享節(jié)點識別，使用邊聚類的方法獲取社團的層次關(guān)系，代表性算法包括UEOC[17]、ELC[18]等。該類方法雖然能夠利用非重疊社團的方法解決重疊社團的層次結(jié)構(gòu)沖突，但通過將網(wǎng)絡(luò)映射為邊圖，增加了算法的系統(tǒng)開銷。最后，基于團滲透的方法融入網(wǎng)絡(luò)動態(tài)演化的分析思想，將社團視為若干連通的完全子圖，通過計算k團的權(quán)值，捕獲近鄰社團的結(jié)構(gòu)性差異，并以此為基礎(chǔ)實現(xiàn)社團演化的預測，代表性算法包括CPM[19]、SCP[20]等。所述方法主要基于網(wǎng)絡(luò)社團的拓撲特征，忽略了用戶節(jié)點固有的屬性信息，缺乏節(jié)點間的關(guān)系識別;無法有效融合重疊用戶的模糊關(guān)系與層次關(guān)聯(lián)，容易引起社團的語義失真。

2 背景理論

2.1 社交網(wǎng)絡(luò)

社交網(wǎng)絡(luò)是由對象節(jié)點集及邊集所構(gòu)成的虛擬社區(qū)。網(wǎng)絡(luò)社團是通過網(wǎng)絡(luò)中隱藏的關(guān)聯(lián)關(guān)系，將社交網(wǎng)絡(luò)劃分為若干具有現(xiàn)實意義的子社區(qū)。相關(guān)概念定義如下：

定義1：（網(wǎng)絡(luò)社團）[21]復雜網(wǎng)絡(luò)G=（V，E）是定義在節(jié)點V和邊E上的無向圖，若G中含有k個節(jié)點的子集QV，其任意兩個節(jié)點vi，vj∈Q，均存在1條邊（vi，vj）∈E，則集合Q為網(wǎng)絡(luò)G上的1個社團。

定義2：（最大獨立社團）[21]對于網(wǎng)絡(luò)G中的社團Qm=（（v1，…，vm），E），若滿足以下約束條件，則為最大獨立社團：①對任意vkQm，均不存在（vi，vk）∈E;②vi∈Qm，vi∈G-Qm，均有（vi，vj）E。

定義3：（切割）[22]在網(wǎng)絡(luò)G=（V，E）中，對于任意集合CV，=V-C，（C，）={eij=（vi，vj）∈E，vi∈C，vj∈}，（C，）定義為網(wǎng)絡(luò)G中的一個切割劃分，eij∈（C，）E稱為一條切割邊。

定義4：（非平凡切割邊）[22]當頂點vi、vj的鄰居數(shù)大于2時，定義（vi，vj）∈E是網(wǎng)絡(luò)G=（V，E）中的非平凡切割邊，記為（vi，vj），其中頂點的鄰居數(shù)是與其存在直接連接關(guān)系的邊數(shù)量。

圖1是一個加權(quán)網(wǎng)絡(luò)社團，邊的權(quán)值表示相鄰節(jié)點在標簽上的興趣相似度。在不考慮權(quán)重的條件下，集合Q1={f，g，h，i}代表1個節(jié)點數(shù)為4的社團，Q2={j，k，l}表示1個節(jié)點數(shù)為3的最大獨立社團。此外，圖1中共含有23條切割邊，其中邊（d，e）為1條非平凡切割邊。

2.2 模糊形式概念分析

Quan T T等[23]在形式概念分析理論的基礎(chǔ)上引入模糊集，提出基于模糊形式概念分析（Fuzzy Formal Concept Analysis）的數(shù)據(jù)建模方法。該理論將原本基于二元偏序關(guān)系的Galois概念集拓展到基于隸屬關(guān)系的模糊形式背景知識庫，極大地拓展了概念格理論的應(yīng)用場景。相關(guān)概念定義如下。

定義5：（模糊形式背景）[23]三元組K=（O，A，Iμ）是由對象集O和屬性集A，以及關(guān)系集O×A所構(gòu)成的模糊形式背景，其中Iμ是O×A上的模糊二元關(guān)系，且對任意o∈O，a∈A，存在模糊關(guān)系映射μ（o，a）∈[0，1]，滿足μ∶（O×A）→[0，1]。

定義6：（模糊形式概念）[23]對于模糊形式背景K=（O，A，Iμ），任意子集MO，NA，均存在如式（1）、式（2）所示的映射關(guān)系（式中α為置信閾值），且滿足M′μ=N，N′μ=M，則二元組（M，N）為模糊形式背景K上的一組模糊形式概念，記為cμ（M，N）。

M′μ={a∈A|o∈M，（μ（a，o）≥α）∈Iμ}（1）

N′μ={o∈O|a∈N，（μ（a，o）≥α）∈Iμ}（2）

定義7：（模糊概念格）[23]對模糊形式背景K=（O，A，Iμ）中的任意模糊形式概念cμ1（M1，N1），cμ2（M2，N2），若滿足如式（3）所示的偏序關(guān)系，則稱cμ2（M2，N2）是cμ1（M1，N1）的上層概念（父概念），cμ1（M1，N1）是cμ2（M2，N2）的下層概念（子概念），即cμ1（M1，N1）≤cμ2（M2，N2）;若CAμα（K）為模糊形式背景K中所有滿足置信閾值α的模糊形式概念集，則（CAμα（K），≤）表示一個滿足偏序關(guān)系的模糊概念格。

M1M2N2N1（3）

3 基于FIUHM模型的社交網(wǎng)絡(luò)檢測方法

興趣社區(qū)中，社區(qū)—用戶—興趣間存在著較強的語義關(guān)聯(lián)性，即用戶與興趣間具有有限個模糊關(guān)系依賴，社區(qū)通過興趣聚類用戶群體。所以，本文利用FFCA理論對不確定性數(shù)據(jù)的描述思想，提出一種基于FIUHM模型的社交網(wǎng)絡(luò)檢測方法，該方法將興趣社區(qū)的識別轉(zhuǎn)變成社區(qū)用戶間在興趣度上的語義關(guān)系聚類，生成帶有格結(jié)構(gòu)的興趣層次序，再通過社團穩(wěn)定指數(shù)識別社團邊界，實現(xiàn)網(wǎng)絡(luò)社區(qū)的多粒度劃分。

興趣社區(qū)中的用戶在興趣上具有一定的相似性，因此，興趣社區(qū)的建?？梢暈橛脩粼谂d趣維上的關(guān)聯(lián)關(guān)系度量。然而，由于用戶興趣的模糊性，需要在用戶—興趣—關(guān)系的聯(lián)合識別過程中，建立針對社區(qū)興趣的“程度刻畫”，實現(xiàn)社區(qū)結(jié)構(gòu)的可視化建模。

3.1 模型框架

基于FIUHM模型的興趣社區(qū)劃分方法主要包含用戶興趣強度標注、社團形式概念建模以及重疊社團語義識別3個步驟。該模型將用戶間的興趣相似度作為興趣社區(qū)中用戶節(jié)點間的關(guān)系邊權(quán)值，通過構(gòu)建模糊形式概念格，獲取帶有模糊關(guān)系和偏序關(guān)系的社團形式概念集合，通過計算社團穩(wěn)定指數(shù)，識別最大獨立社團，最終得到最優(yōu)興趣社團。模型的構(gòu)建流程如圖2所示。

1）用戶興趣強度標注。首先統(tǒng)計預分標簽的頻次，獲取頻次較高的前M個標簽集合L=（l1，l2，…，lm）;使用信息增益計算標簽權(quán)重，計算用戶集合U=（u1，u2，…，un）的加權(quán)標簽向量集合Li={（di，1，wi，1），（di，2，wi，2），…，（di，k，wi，k）}，1≤i≤m，建立用戶—興趣標簽矩陣P;最后，依據(jù)余弦相似度計算用戶對（ui，uj）的興趣相似距離，得到用戶興趣相似矩陣Q。

2）社團形式概念建模。該模塊首先將用戶集合轉(zhuǎn)換為網(wǎng)絡(luò)用戶節(jié)點集V=（v1，v2，…，vn），從相似矩陣Q中抽取數(shù)值大于興趣閾值θ的用戶節(jié)點對（ui，uj），并在網(wǎng)絡(luò)G=（V，E）中添加相應(yīng)的加權(quán)邊，并將其對應(yīng)的領(lǐng)接矩陣映射成社團形式背景;依據(jù)概念偏序關(guān)系，建立基于興趣聚類的模糊概念格，得到社團形式概念及其上層父類概念集合。

3）重疊社團語義識別。計算模糊概念格中所有社團形式概念的社團穩(wěn)定指數(shù)，實現(xiàn)最大獨立社團的識別;利用社團形式概念間的偏序關(guān)系識別含有兩個外延對象的非平凡切割邊，實現(xiàn)重疊社團的節(jié)點劃分。

3.2 模型定義

本文首先將網(wǎng)絡(luò)社區(qū)中用戶—關(guān)系所構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)映射成具有模糊依賴關(guān)系的社團形式背景，并在此基礎(chǔ)上定義社團穩(wěn)定指數(shù)，給出興趣社區(qū)的邊界識別方法。模型中相關(guān)概念表示如下：

定義8：（社團形式背景）對于模糊形式背景K=（O，A，Iμ），其中O為用戶集，A為屬性集，且O≡A，Iμ是O×A上的模糊二元關(guān)系;對任何oi，oj∈O，均有（oi，oj）∈Iμ。

社團形式背景的本質(zhì)是用一組三元關(guān)系（用戶—用戶—模糊關(guān)系）表示網(wǎng)絡(luò)社團的二元關(guān)系（節(jié)點，邊）。為簡化表示，可將社團形式背景表示為Kc=（O，O，Iμ），其中O表示社團用戶節(jié)點，Iμ為O×O上的模糊二元關(guān)系，可用社團用戶節(jié)點間的帶權(quán)邊表示。

定義9：（社團形式概念）設(shè)cμ（M，N）為模糊形式背景K=（O，A，Iμ）上的模糊形式概念，Kc=（O，O，Iμ）是基于模糊形式背景K的社團形式背景，若M=N，則稱cμ（M，N）為社團形式背景Kc上的一組社團形式概念，記為cμi（M，N）。

文獻[24]基于形式背景的依存關(guān)系定義了形式概念穩(wěn)定度，通過估計概念的內(nèi)涵屬性對外延對象的依賴程度，實現(xiàn)概念集合的約簡。該理論基于一個假設(shè)，即如果一個形式概念的內(nèi)涵屬性不依賴于其包含的任意外延對象，則該概念是相對穩(wěn)定的。形式概念的穩(wěn)定指數(shù)定義如下。

定義10：（形式概念穩(wěn)定指數(shù)）[24]設(shè)形式概念c=（M，N）是形式背景K=（O，A，I）上的一組形式概念，形式概念c的穩(wěn)定指數(shù)為σ（M，N），如式（4）所示。

σ（M，N）={cM|c′=N}2|M|（4）

文獻[25]將聚類思想引入形式概念分析理論，證明了定義10所描述的形式概念穩(wěn)定指數(shù)存在最大值，且該數(shù)值與概念本身所含的對象數(shù)有關(guān)，給出形式概念的極大穩(wěn)定值判定方法（定義11）。

定義11：（形式概念極大穩(wěn)定值）[25]形式概念c=（M，N）是形式背景K=（O，A，I）上的一組形式概念，且M>2，則形式概念c的極大穩(wěn)定值為σmax（M，N），如式（5）所示。

σmax（M，N）=2|M|-12|M|（5）

本文以定義11為基礎(chǔ)，引入社團穩(wěn)定指數(shù)，旨在將網(wǎng)絡(luò)社團中節(jié)點間的邊切割問題轉(zhuǎn)換成概念格中的節(jié)點間層次關(guān)系的聚類分析。通過計算社團形式概念所含有外延對象的概率，建立社團穩(wěn)定指數(shù)與社團形式概念間概化與例化的強關(guān)聯(lián)關(guān)系，同時利用模糊概念格的偏序關(guān)系實現(xiàn)興趣社團序列的動態(tài)劃分。社團穩(wěn)定指數(shù)定義如式（6）所示。

定義12：（社團穩(wěn)定指數(shù)）設(shè)cμi（M，M）為社團形式背景Kc=（O，O，Iμ）上的一組社團形式概念，且M=k>2，則cμi（M，M）的社團穩(wěn)定指數(shù)定義如式（6）所示。

σc=2k-Supc（M）2k（6）

式中Supc（M）表示社團形式概念cμi（M，M）的所有上層父概念所含有的外延對象數(shù)量。當k=2時，該社團形式概念僅含有兩個外延對象（cμi（{M1，M2}，{M1，M2}）），則其上層父概念所含有的外延對象為（{M1}，{M2}，），故Supc（M）=3，所以σc=22-322=14。

3.3 模型分析

3.3.1 用戶興趣強度標注

基于內(nèi)容的興趣標簽能夠客觀反映用戶對知識服務(wù)的偏好，而興趣標簽的權(quán)重則能夠衡量用戶對不同興趣的偏好程度。通常情況下，用戶使用興趣標簽的頻率與其對相關(guān)知識的偏好程度存在正相關(guān)?；诩訖?quán)興趣標簽的用戶相似度計算能夠建立不同用戶間的興趣關(guān)聯(lián)映射，實現(xiàn)群用戶的興趣聚類。因此，本文首先借鑒信息增益（Information Divergence）[26]的思想定義用戶興趣標簽權(quán)重，利用增益的變化動態(tài)刻畫標簽特征集合，得到用戶—興趣關(guān)系矩陣。用戶uj對興趣標簽集合L的平均信息增益如式（7）所示，用戶uj的歸一化權(quán)重如式（8）所示。

E（uj）=-∑mi=1fre（uj，li）log2（fre（uj，li））（7）

w（uj）=1k∑ki=1E（uj）（8）

其中，k表示第j個興趣標簽中所含有的特征詞數(shù);li表示第i個興趣標簽;uj表示第j個用戶;m表示興趣標簽集合所含的標簽總數(shù)。

依據(jù)用戶的興趣標簽集合P，計算用戶興趣余弦相似度，構(gòu)建興趣相似矩陣Q。用戶興趣相似度的計算公式如式（9）所示。

sim（ui，uj）=∑kt=1（w（ui），lt）*（w（uj），lt）∑kt=1（w（ui），lt）2*∑kt=1（w（uj），lt）2（9）

其中，w（ui）表示用戶ui的興趣標簽權(quán)重，li表示第i個興趣標簽。

3.3.2 社團形式概念建模

FIUHM模型在建模興趣社團時基于如下假設(shè)，即對于興趣相似度較低的一組用戶視為社團稀疏節(jié)點。在社區(qū)劃分時，上述節(jié)點間視為無語義關(guān)聯(lián)，即用戶間的相似度為0。因此，為降低算法的時間復雜度，引入興趣閾值θ，篩選出關(guān)系矩陣中wi，j不小于θ的用戶（ui，uj）加入用戶集U，同時在領(lǐng)接矩陣J中的第i行j列添加wi，j。從J中依次選取用戶ui的最近鄰興趣相似用戶節(jié)點，并將其映射為社團形式背景的外延對象，加入對象集O。將領(lǐng)接矩陣J中的元素映射為對象間的模糊關(guān)系矩陣，構(gòu)建社團形式背景。若圖1表示一個基于用戶興趣標簽的無向有權(quán)網(wǎng)絡(luò)，將其對應(yīng)的領(lǐng)接矩陣轉(zhuǎn)化為如表1所示的社團形式背景。

為了獲取具有實際含義的社團形式概念，F(xiàn)IUHM模型引入置信閾值α用于控制模糊概念的數(shù)量。依據(jù)模糊概念間偏序關(guān)系，采用文獻[27]的建格算法建立模糊概念格，得到社團形式概念及其上層父類概念集合?；诒?所構(gòu)建的社團模糊概念格如圖3所示（α=0.4）。圖3中共有20個模糊形式概念，依據(jù)定義9可得到7個社團形式概念（圖中灰色節(jié)點）。圖3中相應(yīng)模糊概念的外延與內(nèi)涵如表2所示。圖4是基于社團形式概念的興趣社團劃分結(jié)果。

3.3.3 重疊社團語義識別

通過調(diào)整置信閾值，建模具有實際意義的社團模糊概念格，獲取模糊形式概念及其偏序關(guān)系，得到社團形式概念以及各自上層父類節(jié)點，并分別計算其社團穩(wěn)定指數(shù)σc。依據(jù)圖4得到最終的興趣社團識別結(jié)果，如圖5所示。基于社團穩(wěn)定指數(shù)將上述社團分化為3種類型，首先，若該社團是最大獨立社團，且社團穩(wěn)定指數(shù)等于該模糊概念對應(yīng)的概念極大穩(wěn)定值（定義11），則將其加入最大獨立興趣社團集合。如興趣社團4（概念C11）的社團穩(wěn)定指數(shù)為23-{}23=23-123=0.875，而概念C11的極大穩(wěn)定值為23-123，則興趣社團4為最大獨立社團。其次，若該社團僅含有兩個用戶節(jié)點，且社團穩(wěn)定指數(shù)為0.25，則識別出該社團所含的無向加權(quán)邊為節(jié)點間的非平凡連接，刪除社團的邊連接。如興趣社團2（概念C7）含有兩個節(jié)點{d，e}且社團穩(wěn)定指數(shù)為22-{d，e，}22=22-122=0.25，則邊（d，e）為非平凡連接。最后，對任意含有M、N個節(jié)點的兩個社團，若其共享至少min（M，N）-1個公共用戶節(jié)點，則合并上述社團，并刪除重疊節(jié)點間的邊連接。如興趣社團6（概念C13）和興趣社團7（概念C12）分別含有3個節(jié)點，共享2個公共用戶節(jié)點{m，n}，則應(yīng)該合并興趣社團6和興趣社團7，并刪除邊（m，n）。圖6為最終識別出的興趣社團。

3.4 算法描述

FIUHM算法首先基于用戶的標簽權(quán)重，計算用戶興趣相似度，獲取用戶興趣度矩陣;然后抽取矩陣中相似度大于興趣閾值的用戶節(jié)點，并依據(jù)用戶間的模糊關(guān)系，構(gòu)建社團模糊概念格;最后，計算社團穩(wěn)定指數(shù)，識別重疊社團，得到最優(yōu)興趣社團。相關(guān)算法描述如下：

4 實驗結(jié)果及分析

4.1 數(shù)據(jù)來源

實驗選取豆瓣電影社區(qū)中22個類別的6 500部電影的11 436個“豆瓣成員標簽”作為數(shù)據(jù)來源。經(jīng)過詞頻統(tǒng)計，共篩選出2 000個頻率較高的電影分類標簽加入預分標簽集。用戶對象確定為觀影超過100次（含已看過、在看以及想看的電影）且發(fā)表在線短評不少于200條的6 326個注冊用戶。

4.2 置信閾值取值分析

在興趣社團的識別過程中，由于置信閾值α會影響用戶節(jié)點的數(shù)量以及節(jié)點間關(guān)系邊的相似依賴程度，所以需要分析α的取值與有效社團形式概念個數(shù)的關(guān)系。實驗使用平均絕對偏差（MAE），計算實際社團數(shù)量與預測模糊形式概念數(shù)之間的偏差程度。興趣閾值θ=0.375，通過調(diào)整多組α值，分別計算MAE值，結(jié)果如圖7所示。圖7表明，當α取值在0.6時，MAE取值最?。?.674），偏差程度最低。

4.3 結(jié)果分析

FIUHM模型參數(shù)θ設(shè)置為0.375（收集用戶相似度大于興趣閾值的關(guān)系邊作為興趣社區(qū)的有效邊連接），置信閾值θ選取最優(yōu)值0.6，模型共識別出32個興趣社團。考慮到識別出的興趣社團數(shù)量較多，表3僅列出結(jié)果中含有用戶節(jié)點較多的4個興趣社團，其中每個社團列出相似度最高的10個用戶組，同時選取社團內(nèi)所有用戶的平均信息增益最高的10個屬性標簽作為社團興趣標簽。圖8為部分興趣社團的劃分結(jié)果，圖中不同節(jié)點間的連線長度與其端點用戶間的興趣相似度有關(guān)，即用戶間的興趣相似值越高，節(jié)點間的連線越短。分析表3與圖8可得出以下結(jié)論：①同一個社團內(nèi)存在多個風格迥異的電影類型標簽，體現(xiàn)了用戶興趣的模糊性。②不同的社團間存在重疊用戶，體現(xiàn)了用戶興趣的多樣性，如用戶節(jié)點U1742與U2631。③用戶間的相似度僅僅體現(xiàn)了個體間選擇相同興趣標簽的可能性，而不能作為用戶“出入”某個興趣社團的依據(jù)。如圖8中的用戶U691雖然與U775、U1660間的相似度較高，但依然被劃分為兩個不同的社區(qū)。FIUHM模型通過定義用戶節(jié)點間的非平凡連接，降低了因局部最優(yōu)而提升了社團的抗噪能力。

4.4 算法比較分析

為驗證算法的有效性，本文將11 436個“豆瓣成員標簽”隨機均分成5個子數(shù)據(jù)集（標記為D1～D5），并對比了CMP算法[19]、FCA-k算法[28]和ACDC算法[29]。相關(guān)實驗在準確率上的結(jié)果如圖9所示。此外，為了驗證模型對于公開數(shù)據(jù)集的識別精度，本文采用文獻[30]提出的擴展模塊度EQ（Extended Quality of Modularity）評價指標，在American College Football[31]數(shù)據(jù)集上分析了重疊社團的劃分效果，如表4所示。

綜合分析圖9可知，F(xiàn)IUHM模型在5個數(shù)據(jù)集上的平均準確率為80.25%，高于其余3種方法（依次為74.95%、75.74%、78.66%）。其中，F(xiàn)IUHM與ACDC算法的識別效果明顯優(yōu)于FCA-k算法，主要是因為雖然FCA-k算法基于形式背景構(gòu)建了與社團等價的形式概念，并依據(jù)概念間的偏序關(guān)系實現(xiàn)了重疊社團的劃分，但沒有考慮到概念節(jié)點間的屬性關(guān)聯(lián)。ACDC算法在FCA-k算法的基礎(chǔ)上，考慮了節(jié)點的相似屬性特征，利用概念格間的同構(gòu)關(guān)系，識別具有相似節(jié)點屬性的網(wǎng)絡(luò)社團。FIUHM模型相比于上述模型具有兩處改進，首先，F(xiàn)IUHM模型將節(jié)點間的興趣屬性相似度作為社團間連接的“牽引力”，通過引入標簽權(quán)重，用戶相似度以及非平凡連接等因子，在一定程度上改善了社區(qū)檢測中節(jié)點屬性傳遞的準確性。同時，從形式概念分析的角度，F(xiàn)IUHM模型將社團固有的層次性與重疊性特征轉(zhuǎn)化為模糊形式概念間的伽羅瓦關(guān)系建模，利用社團形式概念間的模糊關(guān)系依賴，實現(xiàn)了局部社團間的多粒度層次聚類，從而提升了重疊社團識別的分辨率。

此外，American College Football數(shù)據(jù)集所含的真實社團數(shù)為12（含有115個對象，615條邊），結(jié)合表4可知，F(xiàn)IUHM模型識別出的社團數(shù)相對較少，主要原因是該模型雖然能夠在平均絕對偏差最優(yōu)時，得到用戶節(jié)點的數(shù)量以及節(jié)點間關(guān)系邊的相似依賴關(guān)系，但采用人工的方式對興趣閾值賦值，雖然能夠保證局部最優(yōu)，但抗噪能力相對不足，無法實現(xiàn)社團節(jié)點間的模糊關(guān)系與偏序關(guān)系的聯(lián)合識別。后期可通過提高模型參數(shù)的可變自適應(yīng)性，實現(xiàn)模型的自動調(diào)參。

5 結(jié)束語

本文針對在線網(wǎng)絡(luò)社區(qū)的劃分問題，提出了一種基于FIUHM模型的興趣社團識別方法，并對豆瓣社區(qū)的真實電影標簽數(shù)據(jù)進行了實驗驗證。通過用戶興趣強度標注，在用戶節(jié)點間加載了一種語義關(guān)聯(lián)，利用社團形式概念建模，設(shè)計了一種基于模糊形式概念分析的社團層次化聚類算法。此外，基于社團穩(wěn)定指數(shù)以及社團形式概念間的偏序關(guān)系，實現(xiàn)重疊社團的語義識別。本文的下一步研究可在用戶短期興趣發(fā)現(xiàn)、動態(tài)社交網(wǎng)絡(luò)演化分析等方面提高興趣社區(qū)檢測的準確性。

參考文獻

[1]辛宇，楊靜，謝志強.一種面向語義重疊社區(qū)發(fā)現(xiàn)的Link-Block算法[J].軟件學報，2016，27（2）：363-380.

[2]吳小蘭，章成志.社會化媒體中的社區(qū)發(fā)現(xiàn)研究綜述[J].現(xiàn)代圖書情報技術(shù)，2013，（10）：36-42.

[3]Waltman，Ludo，Van Eck，et al.A Smart Local Moving Algorithm for Large-scale Modularity-based Community Detection[J].European Physical Journal B，2013，86（11）：471-180.

[4]Xiang J，Hu T，Zhang Y.Local Modularity for Community Detection in Complex Networks[J].Physica A Statistical Mechanics & Its Applications，2016，443：451-459.

[5]劉繼，鄧貴仕.基于加權(quán)譜分析的用戶網(wǎng)絡(luò)社團協(xié)作推薦方法[J].大連理工大學學報，2010，50（3）：438-443.

[6]Newman M E J.Finding Community Structure in Networks Using the Eigenvectors of Matrices[J].Physical Review E，2006，74（3）：36-44.

[7]Kothapalli K，Pemmaraju S V，Sardeshmukh V.On the Analysis of a Label Propagation Algorithm for Community Detection[J].Computer Science，2012，7730（4）：255-269.

[8]Yan X，F(xiàn)anrong M，Yong Z，et al.A Node Influence Based Label Propagation Algorithm for Community Detection in Networks[J].The Scientific World Journal，2014：1-13.

[9]Newman M E J.Detecting Community Structure in Networks[J].European Physical Journal B，2004，38（2）：321-330.

[10]Donetti L，Munoz M A.Detecting Network Communities：A New Systematic and Efficient Algorithm[J].Journal of Statistical Mechanics Theory & Experiment，2004，（10）：1-12.

[11]Raghavan U N，Albert，Réka，et al.Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks[J].Physical Review E，2007，76（3）：036106.

[12]Baumes J，Goldberg M K，Krishnamoorthy M S，et al.Finding Communities By Clustering a Graph Into Overlapping Subgraphs[J].IADIS AC，2005，（5）：97-104.

[13]Malliaros，F(xiàn)ragkiskos D，Vazirgiannis，et al.Clustering and Community Detection in Directed Networks：A Survey[J].Physics Reports，2013，533（4）：95-142.

[14]Bálint Tóth，Tamás Vicsek，Gergely Palla.Overlapping Modularity at the Critical Point of k-Clique Percolation[J].2013，151（3-4）：689-706.

[15]Lancichinetti A，F(xiàn)ortunato S，Kertész J.Detecting the Overlapping and Hierarchical Ommunity Structure in Complex Networks[J].New Journal of Physics，2009，11（3）：033015.

[16]Alexander E I，Brownlee，John A W，et al.Fitness Modeling With Markov Networks[J].IEEE Transactions on Evolutionary Computation，2013，17（6）：862-879.

[17]Evans T S，Lambiotte R.Line Graphs，Link Partitions，and Overlapping Communities[J].Physical Review E：Statistical Nonlinear & Soft Matter Physics，2009，80（80）：145-148.

[18]Huang L，Wang G，Wang Y，et al.Link Clustering with Extended Link Similarity and EQ Evaluation Division[J].Plos One，2013，8（6）：e66005.

[19]Palla G，Derényi I，F(xiàn)arkas I，et al.Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[J].Nature，2005，435（7043）：814-818.

[20]Kumpula J M，Kivela M，Kaski K.A Sequential Algorithm for Fast Clique Percolation[J].Physical Review e Statistical Nonlinear & Soft Matter Physics，2008，78（2）：026109.

[21]Fa-Liang H，Shi-Chao Z，Xiao-Feng Z，et al.Discovering Network Community Based on Multi-Objective Optimization[J].Journal of Software，2013，24（9）：2062-2077.

[22]Shen H W，Cheng X Q，Chen H Q，et al.Information Bottleneck Based Community Detection in Network[J].Chinese Journal of Computers，2009，31（4）：677-686.

[23]Quan T T，Hui S C，Cao T H.A Fuzzy FCA-based Approach for Citation-based Document Retrieval[C]//IEEE Conference on Cybernetics & Intelligent Systems，2004，（1）：578-583.

[24]Kuznetsov S O.On Stability of a Formal Concept[J].Annals of Mathematics and Artificial Intelligence，2007，49（14）：101-115.

[25]Buzmakov A，Kuznetsov S O，Napoli A.Is Concept Stability a Measure for Pattern Selection[J].Procedia Computer Science，2014，31：918-927.

[26]Singh P K，Cherukuri A K，Li J.Concepts Reduction in Formal Concept Analysis with Fuzzy Setting Using Shannon Entropy[J].International Journal of Machine Learning and Cybernetics，2017，8（1）：179-189.

[27]Boffa S，Maio C D，Nola A D，et al.Ferraioli and V.Loia，Unifying Fuzzy Concept Lattice Construction Methods[C]//IEEE International Conference on Fuzzy Systems（FUZZ-IEEE），Vancouver，BC，2016：209-216.

[28]Hao F，Min G，Pei Z，et al.K-clique Community Detection in Social Networks Based on Formal Concept Analysis[J].IEEE Systems，2015：250-259.

[29]Khediri N，Karoui W.Community Detection in Social Network with Node Attributes Based on Formal Concept Analysis[C]//2017 IEEE/ACS 14th International Conference on Computer Systems and Applications（AICCSA）.IEEE，2017：1346-1353.

[30]Nicosia V，Mangioni G，Carchiolo V，et al.Extending the Definition of Modularity to Directed Graphs with Overlapping Communities[J].Journal of Statistical Mechanics Theory and Experiment，2008，（3）：3166-3168.

[31]Michelle Girvan，Mark EJ Newman.Community Structure in Social and Biological Networks[J].Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826.

（責任編輯：陳 媛）