[發(fā)明專利]一種Fedora系統(tǒng)組件復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)檢測方法

有效

• 申請?zhí)枺?/td>: 201710303329.9
• 申請日: 2017-05-03
• 公開（公告）號: CN107240028B
• 公開（公告）日: 2020-09-15
• 發(fā)明（設(shè)計）人: 程久軍;吳瀟;黃震華;張長柱;秦鵬宇;陳向榮;楊陽;廖競學(xué);邵劍雨;尚錚;米浩
• 申請（專利權(quán)）人: 同濟(jì)大學(xué)
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06F17/10
• 代理公司: 上海科律專利代理事務(wù)所(特殊普通合伙) 31290
• 代理人: 葉鳳

1.一種Fedora系統(tǒng)組件復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)檢測方法，其特征在于，根據(jù)Fedora系統(tǒng)組件中的RPM包依賴關(guān)系構(gòu)造出復(fù)雜網(wǎng)絡(luò)，在Fedora網(wǎng)絡(luò)中，一個節(jié)點代表一個軟件模塊，不同的模塊之間存在著依賴關(guān)系，如果兩模塊間存在依賴關(guān)系，則在兩節(jié)點之間創(chuàng)建一條邊，構(gòu)造出一個網(wǎng)絡(luò)；Fedora網(wǎng)絡(luò)的節(jié)點互相協(xié)作完成復(fù)雜任務(wù)，構(gòu)成了社區(qū)；

按如下參數(shù)配置生成合成網(wǎng)絡(luò)：

節(jié)點個數(shù)n；平均度最大度k_max；混合度μ；與度分布關(guān)系τ₁；與社區(qū)大小分布關(guān)系τ₂；最小社區(qū)大小c_min；最大社區(qū)大小c_max；重疊節(jié)點個數(shù)O_n；節(jié)點重疊程度O_m；

給出節(jié)點活躍度的相關(guān)定義和解析，在此基礎(chǔ)上，將節(jié)點活躍度用于重疊社區(qū)擴(kuò)展的目標(biāo)函數(shù)，進(jìn)行社區(qū)擴(kuò)展及使用最大社團(tuán)作為擴(kuò)展種子的相關(guān)解析，給出基于節(jié)點活躍度的非對稱社團(tuán)擴(kuò)展算法，實現(xiàn)重疊社區(qū)發(fā)現(xiàn)；

具體方法包括如下步驟：

步驟1，節(jié)點活躍度的定義與解析

節(jié)點活躍度的定義如下：

定義節(jié)點活躍度為一個與節(jié)點i相關(guān)聯(lián)的實值v_i∈[-1,1]，v_i是描述節(jié)點i在網(wǎng)絡(luò)演化中快速創(chuàng)建或刪除連接的內(nèi)在能力并且是可變的；當(dāng)v_i0時，節(jié)點i的邊有增加的趨勢；當(dāng)v_i0時，節(jié)點i的邊有減少的趨勢；|v_i|越大表示節(jié)點i在未來改變所在重疊社區(qū)的可能性越大；

解析過程如下：

在演化過程中，節(jié)點活躍度會影響節(jié)點邊數(shù)即影響節(jié)點度k_i的改變；設(shè)網(wǎng)絡(luò)的演化表示為快照序列其中，每個快照g_t視為一個靜態(tài)網(wǎng)絡(luò)g_t(V_t,E_t)(1≤t≤n)，V_t和E_t分別表示快照g_t的節(jié)點集合和邊集合；通過比較快照g_t-1和g_t和分析k_i的變化，得到節(jié)點活躍度v_i；節(jié)點適應(yīng)度模型的所有節(jié)點的k_i服從冪律度分布，則一個節(jié)點的k_i隨時間的演化由一個與適應(yīng)度η_i的分布有關(guān)的動態(tài)指數(shù)β(η_i)決定，即：

其中，t表示網(wǎng)絡(luò)的年齡，t_i表示節(jié)點的年齡，m是網(wǎng)絡(luò)中邊數(shù)的改變量除以節(jié)點個數(shù)的改變量；β_i(η_i)∈(0,1)是一個與適應(yīng)度的分布ρ(η_i)及節(jié)點i的適應(yīng)度η_i相關(guān)的指數(shù)；

將公式(4)中的β(η_i)改為α(v_i(t))，其中α(·)表示一個節(jié)點活躍度的函數(shù)；

在一個快照中v_i(t)＝β(η_i)，并對(4)進(jìn)行變換，得到快照g_t中節(jié)點i的活躍度為

其中，m≠0，sgn(·)是一個符號函數(shù)；在該公式中，節(jié)點i的變化速度k_i(t)通過得到，即比較兩個相鄰快照中節(jié)點i的度；節(jié)點活躍度v_i(t)為：

在公式(6)中，如果節(jié)點i滿足規(guī)定其節(jié)點活躍度v_i(t)＝0；

網(wǎng)絡(luò)的年齡必須總是大于節(jié)點的年齡，即tt_i；

公式(6)通過比較快照g_t-1和g_t推導(dǎo)出g_t中的活躍度，而無法得到g_t-1中的活躍度；當(dāng)只有一個靜態(tài)網(wǎng)絡(luò)時，無法得到各節(jié)點的活躍度；對于快照序列無法得到g₁中的節(jié)點活躍度，此時假設(shè)所有節(jié)點活躍度為同一個值；對進(jìn)行分析時，利用快照索引τ∈{1,2,…,n}作為的年齡，每個節(jié)點第一次出現(xiàn)時所在的快照索引τ_i加1作為節(jié)點的年齡，即τ_i+1；

從公式(6)看出，當(dāng)節(jié)點的邊數(shù)改變量越大，活躍度越高；

步驟2中，利用節(jié)點活躍度，組合適應(yīng)度函數(shù)與演化相似度，建立重疊社區(qū)擴(kuò)展的目標(biāo)函數(shù)，目標(biāo)函數(shù)如下

其中，參數(shù)β∈[0,1]；W_in和W_out分別是重疊社區(qū)內(nèi)部節(jié)點之間和內(nèi)外節(jié)點之間的連接數(shù)；當(dāng)前節(jié)點集合作為一個塊n是塊中的節(jié)點個數(shù)；隨機(jī)塊模型中的節(jié)點演化相似度ρ_i；

步驟3，分析了對重疊社區(qū)發(fā)現(xiàn)結(jié)果產(chǎn)生影響的種子和將其進(jìn)行非對稱性擴(kuò)展：

第一步搜索當(dāng)前快照g_t中的所有最大社團(tuán)，第二步是將這些社團(tuán)作為種子進(jìn)行擴(kuò)展；

將一個種子記為S，則與其相鄰的節(jié)點集合N表示為

其中，i是S中的一個節(jié)點，N(i)表示節(jié)點i的所有鄰居節(jié)點；在每次擴(kuò)展時，都從N中選擇一個節(jié)點放入S中，即把它從集合N移動到集合S中；在每次從N中選擇節(jié)點時，對公式(16)中的目標(biāo)函數(shù)進(jìn)行局部貪心優(yōu)化，即從N中選擇一個節(jié)點使得該節(jié)點放入S后函數(shù)f的取值最大；在每次選擇之前，集合S的函數(shù)值為f(S)；試探性地將N中的每個節(jié)點放入S，從而計算新的函數(shù)值與f(S)的差，即

f_i＝f(S∪{i})-f(S) (18)

集合N中的每個節(jié)點i都有一個f_i值，從N中選擇函數(shù)取值為正且取值最大的節(jié)點，即選擇節(jié)點j并將它真正放入S中，

在將節(jié)點j放入S之后，需要對S的鄰居節(jié)點集合N進(jìn)行更新，從而保持與S的狀態(tài)一致；重復(fù)上述過程，每次都選擇一個節(jié)點放入集合S中從而優(yōu)化目標(biāo)函數(shù)；當(dāng)無法再找到任何一個能優(yōu)化公式(19)的節(jié)點時，擴(kuò)展過程終止；此時，集合S所對應(yīng)的目標(biāo)函數(shù)值為局部最優(yōu)值，S作為一個檢測到的重疊社區(qū)；

步驟4，給出基于節(jié)點活躍度的非對稱社團(tuán)擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法：第1步：計算節(jié)點i的活躍度

當(dāng)n＝1時，節(jié)點i的活躍度為0；當(dāng)n大于1時，計算得到節(jié)點i的活躍度v_i；

第2步：把快照g_t以參數(shù)k利用bron-kerbosch算法搜索得到種子，表示為bron-kerbosch(g_i,k)；

第3步：用啟發(fā)式社團(tuán)覆蓋CCH方法過濾相似的種子，相似兩種子之間的相對覆蓋率小于閾值σ，只保留不同種子s，得到種子集合seeds；

第4步：對于每一個過濾后得到的種子s，作為初始節(jié)點集合，然后不斷地從與其相鄰的節(jié)點中尋找合適的節(jié)點放入集合，集合逐步擴(kuò)展為社區(qū)c；

第5步：根據(jù)社區(qū)c和之前擴(kuò)展得到的其他社區(qū)c_i，兩兩計算出相對覆蓋率relative-overlap(c,c_i)，如果相對覆蓋率均小于閾值σ，則把社區(qū)c放入已找到的社區(qū)集合C，并且把s從seeds中刪除；

第6步：計算社區(qū)c與種子集合seeds中剩余種子s_j之間的相對覆蓋率relative-overlap(c,s_j)，如果大于0，則把s_j也從種子集合中刪除。