基于節(jié)點(diǎn)映射的核型企業(yè)重疊社群發(fā)現(xiàn)算法

盧志剛 胡昕晨

摘 要：針對(duì)現(xiàn)有企業(yè)社群發(fā)現(xiàn)算法多側(cè)重于同質(zhì)性市場(chǎng)環(huán)境，不能反映部分企業(yè)會(huì)參與多條供應(yīng)鏈作業(yè)的問(wèn)題，提出一種基于節(jié)點(diǎn)映射關(guān)系的核社群表示模型Map-Community，通過(guò)構(gòu)塑兩種角色節(jié)點(diǎn)及其相互間不同的映射關(guān)系，判斷企業(yè)的社群歸屬問(wèn)題?；谠摫硎灸Ｐ吞岢鲆环N具有近似線性階時(shí)空復(fù)雜度的節(jié)點(diǎn)映射算法（NMA）。首先，采取過(guò)濾操作獲得供應(yīng)鏈網(wǎng)絡(luò)拓?fù)鋱D中的雙連通核心圖;然后，引入映射度擇選出核心企業(yè)節(jié)點(diǎn);其次，依據(jù)映射判斷規(guī)則進(jìn)行局部擴(kuò)展;最后，通過(guò)回溯將局部社群結(jié)構(gòu)拓展至全局網(wǎng)絡(luò)并發(fā)現(xiàn)重疊區(qū)域。LFR網(wǎng)絡(luò)應(yīng)用實(shí)驗(yàn)中，NMA對(duì)閾值變化反映出低敏感性，且在實(shí)用性方面優(yōu)于LFM、COPRA和GCE。在企業(yè)社交網(wǎng)絡(luò)進(jìn)行仿真，利用劃分情況總結(jié)分布效應(yīng)意義。實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法對(duì)于企業(yè)重疊社群發(fā)現(xiàn)的可行性及其在發(fā)現(xiàn)質(zhì)量方面的性能優(yōu)勢(shì)。

關(guān)鍵詞：節(jié)點(diǎn)映射;雙連通核心圖;核心企業(yè);局部擴(kuò)展;企業(yè)重疊社群發(fā)現(xiàn)

中圖分類(lèi)號(hào)： TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）03-0899-08

Abstract： As most existing enterprise community discovery algorithms focus on homogenous market environment， without reflecting the participation of some enterprises in multiple supply chain operations， a core community representation model based on node mapping relationship， Map-Community， was proposed. By constructing two different role nodes and their different mapping relationships， the ownership community of a enterprise was determined. Based on this representation model， Node Mapping Algorithm （NMA） with approximately-linear time-space complexity was proposed. Firstly， filtering operation was used to obtain the biconnected core graph in the topology diagram of the supply chain network. Secondly， mapping degree was introduced to select the core enterprise nodes. Thirdly， local expansion was performed according to the mapping judgment rules. Finally， the local community structure was extended to the global network by backtracking and overlapping areas were discovered. In the LFR （Lancichinetti-Fortunato-Radicchi） network application experiment， NMA shows low sensitivity to threshold change and is superior to LFM （Local Fitness Maximization）， COPRA （Community Overlap PRopagation Algorithm） and GCE （Greedy Clique Expansion） in terms of practicality. Simulation was carried out in the enterprise social network， and the meaning of distribution effect was summarized by the community division. The experimental results verify the feasibility of this algorithm for overlapping enterprise community discovery and its performance advantages in discovery quality.

Key words： node mapping; biconnected core graph; core enterprise; local expansion; overlapping enterprise community discovery

0 引言

企業(yè)社群作為供應(yīng)鏈網(wǎng)絡(luò)拓?fù)浞妒降囊活?lèi)模塊單元，是基于某些共同屬性的節(jié)點(diǎn)互連集合。社群內(nèi)部節(jié)點(diǎn)聯(lián)系相對(duì)緊密，而社群外部聯(lián)系相對(duì)稀疏[1-3]。發(fā)現(xiàn)供應(yīng)鏈網(wǎng)絡(luò)的企業(yè)社群，為探究網(wǎng)絡(luò)拓?fù)涮匦约皟?nèi)在規(guī)律提供了中觀視角，進(jìn)而具有重要的研究意義。作為揭示真實(shí)供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)特性的先決條件，企業(yè)社群發(fā)現(xiàn)問(wèn)題是現(xiàn)階段供應(yīng)鏈網(wǎng)絡(luò)研究的重點(diǎn)關(guān)注方面。

傳統(tǒng)的企業(yè)社群發(fā)現(xiàn)算法通常唯一化節(jié)點(diǎn)歸屬問(wèn)題，旨在獲得非重疊社群結(jié)構(gòu)。這類(lèi)算法主要分為三類(lèi)：第一類(lèi)是基于啟發(fā)式的層次聚類(lèi)方法，包括考慮邊介數(shù)分裂的GN（Girvan-Newman）算法[4]和基于凝聚效應(yīng)的CNM（Clauset-Newman-Moore）算法[5]等;第二類(lèi)是基于目標(biāo)函數(shù)的模塊度優(yōu)化方法，包括極值優(yōu)化[6-7]和貪心算法[8]等;第三類(lèi)是引入正規(guī)矩陣[9]或者拉普拉斯矩陣[10]的譜聚類(lèi)方法。此外，還有基于標(biāo)簽傳播的LPA（Label Propagation Algorithm）[11-12]和基于信息論的算法[13-14]。這些算法嚴(yán)格圈定了社群邊界，對(duì)于現(xiàn)實(shí)中企業(yè)節(jié)點(diǎn)多歸屬現(xiàn)象并不能給出很好的解釋。

針對(duì)傳統(tǒng)的非重疊企業(yè)社群研究存在的問(wèn)題，一些學(xué)者將節(jié)點(diǎn)多屬性特征應(yīng)用于社群識(shí)別過(guò)程中，發(fā)現(xiàn)了交叉區(qū)域。重疊社群發(fā)現(xiàn)算法可大致分為三類(lèi)：第一類(lèi)是派系過(guò)濾方法，CPM（Clique Percolation Method）[15]基于團(tuán)滲透理論，設(shè)置網(wǎng)絡(luò)建模類(lèi)型為k團(tuán)結(jié)構(gòu)，但該算法對(duì)完全圖依賴(lài)性強(qiáng)，并不適用于稀疏網(wǎng)絡(luò)。第二類(lèi)是局部?jī)?yōu)化擴(kuò)展方法，LWP（Luo-Wang-Promislow）算法[16]利用啟發(fā)式探索完成局部子圖度量?jī)?yōu)化過(guò)程。OSLOM（Order Statistics Local Optimization Method）[17]通過(guò)局部聚類(lèi)統(tǒng)計(jì)方法，優(yōu)化社群挖掘過(guò)程。第三類(lèi)是標(biāo)簽傳播方法，COPRA（Community Overlap PRopagation Algorithm）[18]考慮了節(jié)點(diǎn)歸屬的不確定性，改進(jìn)LPA以實(shí)現(xiàn)多標(biāo)簽識(shí)別，但參數(shù)v的選取難以滿(mǎn)足真實(shí)網(wǎng)絡(luò)節(jié)點(diǎn)歸屬社群差異較大的條件。SLPA（Speaker-Listener Label Propagation Algorithm）[19]采用Speaker-Listener傳播策略完成歷史信息的全讀取，但出于對(duì)時(shí)間復(fù)雜度制約因素的考量，該算法并不適用于稠密圖。上述方法缺乏對(duì)節(jié)點(diǎn)類(lèi)型的差異化處理，并不能完全還原真實(shí)供應(yīng)鏈網(wǎng)絡(luò)的社群結(jié)構(gòu)。

針對(duì)企業(yè)社群的現(xiàn)有研究主要涉及同質(zhì)類(lèi)型的問(wèn)題，近年來(lái)以異質(zhì)性結(jié)構(gòu)為基礎(chǔ)的企業(yè)環(huán)境備受關(guān)注。企業(yè)社群逐漸成為以一個(gè)或幾個(gè)龍頭企業(yè)為核心，其他中小型企業(yè)作為核心企業(yè)的組件供應(yīng)商，存留于它地理周?chē)囊环N鏈接構(gòu)體[20]?；诤诵墓?jié)點(diǎn)擴(kuò)散的思想，LFM（Local Fitness Maximization）算法[21]以隨機(jī)種子節(jié)點(diǎn)作為初始社群，重復(fù)利用增刪節(jié)點(diǎn)引起的適應(yīng)度變化值判斷新社群組成及交叉區(qū)域。GCE（Greedy Clique Expansion）算法[22]探尋極大團(tuán)子圖，并以此作為核心進(jìn)行貪婪式擴(kuò)展。上述算法在選核方面存在隨機(jī)性，而且刪除操作還會(huì)引發(fā)擴(kuò)展偏差和覆蓋不全等問(wèn)題。

針對(duì)現(xiàn)有企業(yè)社群方法的不足，需要找到一種相對(duì)精準(zhǔn)的核型企業(yè)重疊社群發(fā)現(xiàn)算法，既能夠解決節(jié)點(diǎn)多歸屬的現(xiàn)實(shí)問(wèn)題，又能實(shí)現(xiàn)網(wǎng)絡(luò)異質(zhì)模塊的高效劃分。本文算法旨在從供應(yīng)鏈過(guò)濾網(wǎng)絡(luò)中捕捉核心企業(yè)節(jié)點(diǎn)，基于企業(yè)節(jié)點(diǎn)間的映射關(guān)系鏈不斷完善社群劃分結(jié)果。本文的主要工作有：

1）提出一種基于節(jié)點(diǎn)映射關(guān)系的核社群表示模型Map-Community，用以描述群內(nèi)企業(yè)節(jié)點(diǎn)之間的社群歸屬映射關(guān)系。

2）提出節(jié)點(diǎn)映射算法（Node Mapping Algorithm，NMA），NMA基于過(guò)濾操作可大幅簡(jiǎn)化企業(yè)社群的后續(xù)挖掘過(guò)程，通過(guò)精確定位核心企業(yè)可實(shí)現(xiàn)高效社群劃分工作。算法性能優(yōu)于COPRA[18]等具有近似線性階時(shí)間復(fù)雜度的企業(yè)重疊社群發(fā)現(xiàn)算法。

2 節(jié)點(diǎn)映射核社群發(fā)現(xiàn)算法

2.1 節(jié)點(diǎn)映射核社群表示模型

對(duì)于企業(yè)社群的挖掘過(guò)程，一些經(jīng)典的社群發(fā)現(xiàn)算法或從網(wǎng)狀圖的整體結(jié)構(gòu)入手，考慮全局信息[21]，或基于局部節(jié)點(diǎn)的作用因素，考慮區(qū)域拓展[18，22]。如COPRA算法[18]作為重疊社群發(fā)現(xiàn)的代表算法，基于局部性為每個(gè)節(jié)點(diǎn)存儲(chǔ)多標(biāo)簽及其對(duì)應(yīng)的隸屬度，但該算法不適用于節(jié)點(diǎn)關(guān)系混雜的網(wǎng)絡(luò)?？紤]到整體和局部?jī)煞N切入角度沒(méi)有完全把握核型企業(yè)社群的問(wèn)題，現(xiàn)引入企業(yè)節(jié)點(diǎn)間的映射關(guān)系，融合兩種視角挖掘社群結(jié)構(gòu)。通過(guò)不同的映射關(guān)系，將同一企業(yè)節(jié)點(diǎn)關(guān)聯(lián)范圍內(nèi)的成員劃分至一個(gè)社群。

在此意義上，社群表示模型主要由種子節(jié)點(diǎn)、聯(lián)結(jié)節(jié)點(diǎn)以及二者的映射關(guān)系組成，其中種子節(jié)點(diǎn)標(biāo)識(shí)核心企業(yè)（Core-Enterprise， CE）角色，聯(lián)結(jié)節(jié)點(diǎn)標(biāo)識(shí)配套企業(yè)（Supporting-Enterprise， SE）角色，節(jié)點(diǎn)映射關(guān)系標(biāo)識(shí)種子節(jié)點(diǎn)根據(jù)映射規(guī)則，提取與本節(jié)點(diǎn)具有適配主從關(guān)系的聯(lián)結(jié)節(jié)點(diǎn)過(guò)程，具體定義如下。

2.2 節(jié)點(diǎn)映射算法

核型企業(yè)社群發(fā)現(xiàn)的節(jié)點(diǎn)映射總體算法由過(guò)濾、種子節(jié)點(diǎn)選擇、擴(kuò)展和回溯4個(gè)階段構(gòu)成。通過(guò)對(duì)原始供應(yīng)鏈網(wǎng)絡(luò)的濾除處理，降低了后續(xù)程序的復(fù)雜性;然后以選擇算法獲取的某些種子節(jié)點(diǎn)為始端，利用映射規(guī)則找到重疊局部社群;最后基于回溯操作擴(kuò)展至全局網(wǎng)絡(luò)，完善社群結(jié)構(gòu)。

2.2.1 過(guò)濾階段

本環(huán)節(jié)需要濾除不參與重疊社群發(fā)現(xiàn)的部分非核心企業(yè)節(jié)點(diǎn)，進(jìn)而識(shí)別出包含重疊社群的供應(yīng)鏈網(wǎng)絡(luò)圖中的區(qū)域。對(duì)于核型企業(yè)重疊社群發(fā)現(xiàn)的問(wèn)題，可作如下定義。

2.2.2 種子節(jié)點(diǎn)選擇階段

在分離半島圖獲得雙連通核心圖后，需要從中提取種子節(jié)點(diǎn)。有如下相關(guān)定義。

式（3）是由萬(wàn)有引力定律推理得出，該式結(jié)果與節(jié)點(diǎn)度數(shù)成正比關(guān)系，與節(jié)點(diǎn)間距離成反比關(guān)系。由于網(wǎng)絡(luò)拓?fù)涮匦缘拇嬖?，用度?shù)反映節(jié)點(diǎn)所有信息的做法最為可靠，且能反映與其他節(jié)點(diǎn)的交流程度，因此式中候選種子節(jié)點(diǎn)u的質(zhì)量用D（u）表示。節(jié)點(diǎn)間的關(guān)聯(lián)度d（u，v）則通過(guò)其相異度來(lái)體現(xiàn)，而后者與Jaccard相似度SIM（u，v）互補(bǔ)，即d（u，v）=1-SIM（u，v）[23]。當(dāng)點(diǎn)u和v的相異度值越大（或SIM（u，v）值越?。r(shí)，前者對(duì)于后者的映射力越小，二者屬于同一社群的概率也越小。另外，由式（4）得到的F（u）值越大，說(shuō)明候選節(jié)點(diǎn)u的權(quán)威映射越大，它在眾鄰居節(jié)點(diǎn)中的顯著性越強(qiáng)，則候選節(jié)點(diǎn)u很有可能成為核心節(jié)點(diǎn)，即ku=u。

在種子節(jié)點(diǎn)選擇算法中，先根據(jù)兩個(gè)候選節(jié)點(diǎn)間的關(guān)聯(lián)性計(jì)算SIM（u，v），再利用函數(shù)映射F（u）獲得每個(gè)企業(yè)節(jié)點(diǎn)的映射度值。若當(dāng)前候選種子節(jié)點(diǎn)符合映射度值高于其他鄰居節(jié)點(diǎn)，且同屬一個(gè)社群的條件，則可輸出為種子節(jié)點(diǎn)。具體實(shí)現(xiàn)過(guò)程見(jiàn)算法1。

在雙連通核心圖中，算法1輸出的種子節(jié)點(diǎn)集合中的點(diǎn)不一定有最大的度數(shù)，但從分布情況上看，它們處于最佳位置。找到合適的種子節(jié)點(diǎn)后，下一步將基于映射規(guī)則識(shí)別鄰接社群。

2.2.3 擴(kuò)展階段

根據(jù)Map-Community模型得，任意節(jié)點(diǎn)u的直接映射點(diǎn)來(lái)自于其鄰居節(jié)點(diǎn)集N（u），間接映射點(diǎn)則從點(diǎn)v（v∈N（u））的鄰居節(jié)點(diǎn)集N（v）中獲取，以此類(lèi)推直至遍歷所有具備映射關(guān)系的節(jié)點(diǎn)。節(jié)點(diǎn)映射規(guī)則旨在從具有最大映射度值的種子節(jié)點(diǎn)切入，度量該點(diǎn)對(duì)其他聯(lián)結(jié)節(jié)點(diǎn)的映射力。該規(guī)則是實(shí)現(xiàn)遍歷過(guò)程的重要條件，同時(shí)也是供應(yīng)鏈網(wǎng)絡(luò)社群發(fā)現(xiàn)的依據(jù)。擴(kuò)展階段通過(guò)反復(fù)迭代，比較節(jié)點(diǎn)間的映射強(qiáng)度，進(jìn)而判斷構(gòu)成映射關(guān)系的節(jié)點(diǎn)是否同屬一個(gè)社群，相關(guān)定義如下。

在2.2.2節(jié)中利用選擇算法獲知了種子節(jié)點(diǎn)集，這一階段將找出構(gòu)成社群的其他節(jié)點(diǎn)要素。首先，從種子點(diǎn)集Vk中選取函數(shù)映射值最大的節(jié)點(diǎn)，記為k，此時(shí)k可以直接擴(kuò)展至其鄰居節(jié)點(diǎn)集N（k）的所有元素;然后對(duì)N（k）中每一個(gè)節(jié)點(diǎn)，與其所有鄰接點(diǎn)進(jìn)行關(guān)系影響力的分析，根據(jù)map值判斷解決映射和社群歸屬問(wèn)題;最后把符合映射規(guī)則的節(jié)點(diǎn)全部寫(xiě)入社群Ck，第一次迭代結(jié)束。后續(xù)過(guò)程初始選擇范圍應(yīng)是未劃分到任意社群的剩余節(jié)點(diǎn)，重復(fù)上述步驟。具體實(shí)現(xiàn)過(guò)程見(jiàn)算法2。

對(duì)在過(guò)濾階段得到的雙連通核心圖中的全部節(jié)點(diǎn)多次執(zhí)行迭代過(guò)程，其中初始種子節(jié)點(diǎn)擴(kuò)展適用直接映射判斷規(guī)則，后續(xù)擴(kuò)展適用間接映射判斷規(guī)則，直至獲知所有可能存在的主從信息，進(jìn)而整理得核型企業(yè)重疊社群構(gòu)體。

2.2.4 回溯階段

在雙連通核心圖中，經(jīng)過(guò)種子節(jié)點(diǎn)選擇和擴(kuò)展階段獲得了部分社群劃分，接下來(lái)需要將半島圖回溯至各個(gè)社群劃分結(jié)構(gòu)中。對(duì)于過(guò)濾發(fā)生前每個(gè)通過(guò)橋聯(lián)結(jié)的半島圖，可利用橋中與雙連通核心圖距離較近的端點(diǎn)將其添加至對(duì)應(yīng)的社群。

2.2.5 映射流程

根據(jù)上述各算法階段的描述，可得如圖5所示的節(jié)點(diǎn)映射整體算法流程。

2.3 算法復(fù)雜度

另外，NMA在計(jì)算節(jié)點(diǎn)映射關(guān)系時(shí)，需考慮映射雙方的角色及關(guān)系信息。在依據(jù)鄰接存儲(chǔ)網(wǎng)絡(luò)發(fā)現(xiàn)社群的過(guò)程中，所需節(jié)點(diǎn)和邊的內(nèi)存空間分別為O（n）和O（m）。因此NMA的空間復(fù)雜度為O（n+m）。

3 實(shí)驗(yàn)

為驗(yàn)證基于節(jié)點(diǎn)映射的核型企業(yè)重疊社群發(fā)現(xiàn)算法的有效性，首先將該算法應(yīng)用于LFR（Lancichinetti-Fortunato-Radicchi）測(cè)試網(wǎng)絡(luò)中，關(guān)聯(lián)LFM、COPRA算法等經(jīng)典的社群發(fā)現(xiàn)算法作結(jié)果及性能對(duì)比;然后將其應(yīng)用于企業(yè)仿真實(shí)驗(yàn)中，獲取供應(yīng)鏈網(wǎng)絡(luò)社群劃分結(jié)果。實(shí)驗(yàn)運(yùn)作環(huán)境：處理器 Inter Core i5-7200U CPU@2.50GHz 2.70GHz，內(nèi)存8GB，操作系統(tǒng)Windows 10，實(shí)現(xiàn)語(yǔ)言采用Java。

3.1 LFR網(wǎng)絡(luò)實(shí)驗(yàn)

3.1.1 LFR網(wǎng)絡(luò)及評(píng)價(jià)指標(biāo)

LFR網(wǎng)絡(luò)是Lancichinetti等[24]提出的用來(lái)檢驗(yàn)社群發(fā)現(xiàn)算法性能的基準(zhǔn)測(cè)試網(wǎng)絡(luò)，可通過(guò)設(shè)置不同的參數(shù)值圈定各式網(wǎng)絡(luò)拓?fù)湫螒B(tài)。其中，n標(biāo)識(shí)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù);表示平均節(jié)點(diǎn)度;kmax為網(wǎng)絡(luò)中的最大節(jié)點(diǎn)度;On和Om分別控制網(wǎng)絡(luò)中重疊節(jié)點(diǎn)的數(shù)量和歸屬社群的個(gè)數(shù);Cmin和Cmax用于限定社群規(guī)模;τ1和τ2分別表示網(wǎng)絡(luò)節(jié)點(diǎn)度和社群容量的冪律分布指數(shù);混合參數(shù)μ設(shè)定社群內(nèi)外節(jié)點(diǎn)存在鏈接關(guān)系的概率。

由于LFR基準(zhǔn)網(wǎng)絡(luò)的社群組織具有既定結(jié)構(gòu)，因此可將不同算法發(fā)現(xiàn)的社群劃分結(jié)果同此結(jié)構(gòu)進(jìn)行對(duì)比，以測(cè)評(píng)算法的實(shí)用性。過(guò)程采用規(guī)范互信息（Normalized Mutual Information， NMI）[25-26]作為相似度量指標(biāo)，定義如下：

算法生成社群與既定結(jié)構(gòu)完全一致;而當(dāng)NMI（CA，CB）=0時(shí)，說(shuō)明二者完全不一致。

3.1.2 閾值分析

判斷NMA中映射關(guān)系成立與否的關(guān)鍵在于閾值ε的圈定。 ε值越大，待映射節(jié)點(diǎn)歸屬當(dāng)前社群的可能性越小，最終劃分越容易出現(xiàn)覆蓋網(wǎng)絡(luò)不全的結(jié)果。如圖6所示，對(duì)于3個(gè)

不同的τ1值決定的LFR基準(zhǔn)網(wǎng)絡(luò)，評(píng)價(jià)指標(biāo)NMI值均保持在0.85以上，這說(shuō)明閾值ε的取值對(duì)NMI指標(biāo)沒(méi)有絕對(duì)影響，且NMA對(duì)ε的敏感性較低。令ε=0.5執(zhí)行算法得到的社群，一般默認(rèn)是較為貼合實(shí)際的。另外，當(dāng)τ1=-2時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)度的差異程度較高，即存在極少數(shù)節(jié)點(diǎn)引出的鏈接數(shù)量過(guò)飽和而多數(shù)節(jié)點(diǎn)相反的情況，此時(shí)通過(guò)NMA發(fā)現(xiàn)的社群測(cè)試值NMI較高，從而論證了NMA對(duì)于這樣一種節(jié)點(diǎn)度分布不均的無(wú)標(biāo)度網(wǎng)絡(luò)的可適性。

3.1.3 算法比較

首先選取表1所示的接近線性時(shí)間復(fù)雜度的企業(yè)重疊社群發(fā)現(xiàn)算法，后續(xù)將基于LFR測(cè)試網(wǎng)絡(luò)對(duì)各算法進(jìn)行分析。

表2所列算法應(yīng)用于不同LFR網(wǎng)絡(luò)的NMI測(cè)試值如圖7所示，其中各組子圖橫縱坐標(biāo)分別為Om和NMI指標(biāo)。從全局觀察到，NMI值隨著Om數(shù)量的遞增有逐漸降低的趨勢(shì)，這是由于Om的變化阻滯了社群挖掘進(jìn)度，進(jìn)而影響了劃分結(jié)果的質(zhì)量。

細(xì)分來(lái)看，當(dāng)固定μ值時(shí)，NMI指標(biāo)對(duì)n值從2000～10000的變化并不敏感，對(duì)應(yīng)數(shù)值基本維持不變。原因在于上述算法皆采用從種子節(jié)點(diǎn)出發(fā)進(jìn)行局部探尋的策略，該過(guò)程僅與種子所在某區(qū)域的子圖有關(guān)，避開(kāi)了網(wǎng)絡(luò)全局性的影響。當(dāng)固定n值時(shí)， μ值從0.1～0.4的變化使得社群內(nèi)外節(jié)點(diǎn)關(guān)聯(lián)水平上升，進(jìn)而導(dǎo)致社群邊界不清晰，因此4種算法的NMI值都出現(xiàn)了不同程度的滑落現(xiàn)象，其中COPRA算法的降幅最為顯著，LFM算法次之，GCE算法因其種子團(tuán)的優(yōu)勢(shì)變化并不明顯。

如圖7（a）（c）所示，當(dāng)μ取值較小時(shí)，NMA和COPRA算法的NMI取值線接近重合;如圖7（b）（d）所示，當(dāng)μ取值較大時(shí)，COPRA算法得到的NMI值初期下降程度明顯，這是因?yàn)棣淘斐闪松缛航Y(jié)構(gòu)模糊，增加了標(biāo)簽選取的難度。隨著Om的擴(kuò)大，NMA和COPRA算法的NMI差距會(huì)逐步縮減，此時(shí)不易發(fā)現(xiàn)重疊社群，前者表現(xiàn)為閾值ε的控制，后者在于非重疊節(jié)點(diǎn)標(biāo)簽的選取。

對(duì)比NMA和GCE算法，發(fā)現(xiàn)前者的劃分效果略?xún)?yōu)于后者，尤其在Om∈[2，5]時(shí)，前者的NMI線的位置明顯高于后者。GCE算法在程序結(jié)束后可能會(huì)出現(xiàn)節(jié)點(diǎn)歸屬標(biāo)簽未知的情況，NMA算法基于過(guò)濾和回溯過(guò)程能夠?qū)崿F(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)全覆蓋，很好地規(guī)避了GCE算法存在的風(fēng)險(xiǎn)。

綜上，較之LFM、COPRA和GCE算法，NMA在LFR基準(zhǔn)網(wǎng)絡(luò)中的社群發(fā)現(xiàn)性能更佳。

3.2 企業(yè)社交網(wǎng)絡(luò)仿真實(shí)驗(yàn)

根據(jù)供應(yīng)鏈運(yùn)作的特點(diǎn)，可將其內(nèi)部鏈節(jié)抽象為供應(yīng)商、制造商、分銷(xiāo)商、零售商和消費(fèi)者5種行為主體。設(shè)有覆蓋387個(gè)節(jié)點(diǎn)的6條供應(yīng)鏈，其中上述5種主體的數(shù)量分別為96，15，46，80，150。該鏈在特定時(shí)間下以交易行為標(biāo)識(shí)的無(wú)權(quán)無(wú)向網(wǎng)絡(luò)如圖8所示。

經(jīng)過(guò)NMA算法的過(guò)濾和選擇操作后，可識(shí)別出核心企業(yè)節(jié)點(diǎn)為151，153，154，155，156，157。圖9以節(jié)選原始圖為例，完成部分社群挖掘過(guò)程。由于所有的聯(lián)結(jié)邊均不具備橋的特質(zhì)，因此無(wú)需對(duì)節(jié)選圖進(jìn)行過(guò)濾。

各節(jié)點(diǎn)的函數(shù)映射值以及算法選擇的結(jié)果如表3所示，其中“Y”表示節(jié)點(diǎn)u被選中為核心企業(yè)節(jié)點(diǎn)，“N”表示未選中，標(biāo)記為“Y”的所有節(jié)點(diǎn)構(gòu)成了核心企業(yè)節(jié)點(diǎn)集合，即Vk={155，156}。

根據(jù)圖9和表3進(jìn)行迭代映射過(guò)程，第一次迭代結(jié)果如圖10（a）所示，可得點(diǎn)156的配套企業(yè)節(jié)點(diǎn)為24，73，74，80，82。第二次迭代結(jié)果如圖10（b）所示，可得點(diǎn)155的配套企業(yè)節(jié)點(diǎn)為61，63，66，67，69，74，149（閾值ε=0.5）。

如圖11所示，從映射關(guān)系規(guī)律中可推得社群劃分D={C1，C2}，兩社群C1和C2的交叉區(qū)域即為重疊企業(yè)節(jié)點(diǎn)74。

繼續(xù)應(yīng)用NMA算法拓展至全局供應(yīng)鏈網(wǎng)絡(luò)，可得圖12所示的最終社群劃分結(jié)果。

通過(guò)上述仿真實(shí)驗(yàn)，最終可得分別以企業(yè)151，153，154，155，156，157為核心的6個(gè)社群，記作C5，C4，C6，C1，C2，C3，其中社群C1和C2的重疊部分是企業(yè)74，C2和C3的重疊區(qū)域是企業(yè)94。由實(shí)驗(yàn)結(jié)果可推知以下結(jié)論：

1）社群內(nèi)的節(jié)點(diǎn)高聯(lián)結(jié)度表現(xiàn)在，核心企業(yè)決定了異構(gòu)環(huán)境的歸屬社群結(jié)構(gòu)，使得相關(guān)配套企業(yè)能夠在既定范圍內(nèi)專(zhuān)注生產(chǎn)工作，這樣一方面削弱了配套企業(yè)直面市場(chǎng)的壓力，另一方面保證了群內(nèi)競(jìng)合關(guān)系的平衡，進(jìn)而提升企業(yè)社群的整體福利享有水平。如制造商156的一級(jí)供應(yīng)商24，73，74，82和二級(jí)供應(yīng)商72，80，91等，受社群C2的圈定影響及企業(yè)156的核心映射作用而協(xié)作生產(chǎn)相關(guān)配件。

2）社群間的低聯(lián)結(jié)度表現(xiàn)于核型社群具有一定的進(jìn)入壁壘，以維持社群規(guī)模的相對(duì)穩(wěn)定，也因此增強(qiáng)了針對(duì)外部市場(chǎng)沖擊的應(yīng)變能力。如社群C1由于制造商155的主導(dǎo)作用而具備排他性，因此群外企業(yè)22和27等皆為被限制入群。

4 結(jié)語(yǔ)

針對(duì)企業(yè)主從關(guān)系提出的節(jié)點(diǎn)映射核社群模型，適用于在供應(yīng)鏈網(wǎng)絡(luò)中利用關(guān)聯(lián)鄰域信息挖掘核型企業(yè)社群的情況。NMA算法在雙連通核心圖中搜索關(guān)鍵種子節(jié)點(diǎn)，利用節(jié)點(diǎn)映射規(guī)則判斷聯(lián)結(jié)節(jié)點(diǎn)，最終回歸原始供應(yīng)鏈網(wǎng)絡(luò)圖獲得網(wǎng)絡(luò)映射社群結(jié)構(gòu)。LFR基準(zhǔn)網(wǎng)絡(luò)和企業(yè)仿真網(wǎng)絡(luò)的實(shí)驗(yàn)表明，NMA算法性能較佳，發(fā)現(xiàn)的社群質(zhì)量較好。另外該算法需要對(duì)閾值ε在合理控制范圍內(nèi)進(jìn)行設(shè)定，以保證網(wǎng)絡(luò)社群劃分的高覆蓋率。后續(xù)工作將改進(jìn)核心企業(yè)選擇策略，考慮更新時(shí)間引發(fā)的增量社群發(fā)現(xiàn)。

參考文獻(xiàn) （References）

[1] GULBAHCE N， LEHMANN S. The art of community detection [J]. Bioessays， 2008， 30（10）： 934-938.

[2] MUCHA P J， RICHARDSON T， MACON K， et al. Community structure in time dependent，multiscale， and multiplex networks [J]. Science， 2010， 328（5980）： 876-878.

[3] 隆華，李寶安.基于重疊度與模塊度增量的復(fù)雜網(wǎng)絡(luò)社區(qū)識(shí)別[J].計(jì)算機(jī)應(yīng)用，2017，37（S1）：6-8.（LONG H， LI B A. Community identificaiton of complex networks based on overlapping degree and module increment [J]. Journal of Computer Applications， 2017， 37（S1）： 6-8.）

[4] NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review E， 2004， 69（2）： 026113.

[5] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826.

GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [EB/OL]. [2018-07-10]. https：//arxiv.org/pdf/cond-mat/0112110.pdf.

[6] DUCH J， ARENAS A. Community detection in complex networks using extremal optimization [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2005， 72（2 Pt 2）： 027104.

[7] BOETTCHER S， PERCUS A G. Optimization with extremal dynamics [J]. Physical Review Letters， 2001， 86（23）： 5211-5214.

[8] NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E， 2004， 69（6）： 066133.

[9] CAPOCCI A， SERVEDIO V D P， CALDARELLI G， et al. Detecting communities in large networks [J]. Physica A： Statistical Mechanics and Its Applications， 2005， 352（2/3/4）： 669-676.

[10] DONETTI L， MUOZ M A. Detecting network communities： a new systematic and efficient algorithm [J]. Journal of Statistical Mechanics： Theory and Experiment， 2004， （10）： 10012（只有期）.

DONETTI L， MUOZ M A. Detecting network communities： a new systematic and efficient algorithm [EB/OL]. [2018-07-11]. https：//arxiv.org/pdf/cond-mat/0404652v2.pdf.

[11] RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2007， 76（3 Pt 2）： 036106.

[12] 陳羽中，施松，朱偉平，等.一種基于鄰域跟隨關(guān)系的增量社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)學(xué)報(bào)，2017，40（3）： 570-583.（CHEN Y Z， SHI S， ZHU W P， et al. An incremental community discovery algorithm based on neighborhood following relationship [J]. Chinese Journal of Computers， 2017， 40（3）： 570-583.）

[13] ROSVALL M， BERGSTROM C T. Maps of random walks on complex networks reveal community structure [J]. Proceedings of the National Academy of Sciences of the United States of America， 2008， 105（4）： 1118-1123.

[14] 鄧小龍，王柏，吳斌，等.基于信息熵的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分建模和驗(yàn)證[J].計(jì)算機(jī)研究與發(fā)展，2012，49（4）：725-734.（DENG X L， WANG B， WU B， et al. Modularity modeling and evaluation in community detecting of complex network based on information entropy [J]. Journal of Computer Research and Development， 2012， 49（4）： 725-734.）

[15] PALLA G， DERNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature， 2005， 435（7043）： 814-818.

[16] LUO F， WANG J Z， PROMISLOW E. Exploring local community structures in large networks[C]// WI '06： Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence. Washington， DC： IEEE Computer Society， 2006： 233-239.

[17] LANCICHINETTI A， RADICCHI F， RAMASCO J J， et al. Finding statistically significant communities in networks [J]. PLoS One， 2011， 6（4）： e18961.

[18] GREGORY S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics， 2010， 12（10）： 103018.

[19] XIE J R， SZYMANSKI B K. Towards linear time overlapping community detection in social networks [C]// Proceedings of the 2012 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 7302. Berlin： Springer， 2012： 25-36.

[20] 項(xiàng)后軍，裘斌斌，周宇.核心企業(yè)視角下不同集群演化過(guò)程的比較研究[J].科學(xué)學(xué)研究，2015，33（2）：225-233.（XIANG H J， QIU B B， ZHOU Y. The comparative research of the evolution of different industrial clusters with the perspective of ieading firms [J]. Studies in Science of Science， 2015， 33（2）： 225-233.）

[21] LANCICHINETTI A， FORTUNATO S， KERTSZ J. Detecting the overlapping and hierarchical community structure in complex networks [J]. New Journal of Physics， 2009， 11（3）： 033015.

[22] LEE C， REID F， McDAID A， et al. Detecting highly overlapping community structure by greedy clique expansion [EB/OL]. [2014-11-10]. https：//arxiv.org/pdf/1002.1827.pdf.

[23] ANDERSEN R， LANG K J. Communities from seed sets [C]// WWW '06： Proceedings of the 15th International Conference on World Wide Web. New York： ACM， 2006： 223-232.

[24] LANCICHINETTI A， FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2009， 80（1 Pt 2）： 016118.

[25] 陳俊宇，周剛，南煜，等.一種半監(jiān)督的局部擴(kuò)展式重疊社區(qū)發(fā)現(xiàn)方法[J].計(jì)算機(jī)研究與發(fā)展，2016，53（6）：1376-1388.（CHEN J Y， ZHOU G， NAN Y， et al. Semi-supervised local expansion method for overlapping community detection [J]. Journal of Computer Research and Development， 2016， 53（6）： 1376-1388.）

[26] DANON L， DUCH J， DIAZ-GUILERA A， et al. Comparing community structure identification [J]. Journal of Statistical Mechanics： Theory and Experiment， 2005， 2005（9）： P09008.