[發明專利]一種社會網絡中社團成員層次結構的探測方法

在審

• 申請號: 201410698820.2
• 申請日: 2014-11-27
• 公開（公告）號: CN104484344A
• 公開（公告）日: 2015-04-01
• 發明（設計）人: 李侃;陳鳳嬌
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種社會網絡中社團成員層次結構的探測方法，其特征在于：包括以下步驟：

步驟一、輸入社會網絡的節點和邊，社團核心節點S，迭代步數T；

步驟二、根據下述公式計算每個節點i對于社團核心S的歸屬程度并按照歸屬程度降序排列所有節點：

BCsT(i)=Σt=1Tqst(i);]]>

qst(i)=Σj=1Nqst-1(j)Qij;]]>

Qij=Aijdi,i≠s0,i=s;]]>

qs0(i)=0,i≠s1,i=s;]]>

其中矩陣A_N×N是網絡鄰接矩陣，N是網絡中節點的個數，矩陣元素A_ij＝1表示節點i和j之間有邊，1＜＝i，j＜＝N，否則，A_ii＝0表示節點i和j之間沒有邊；d_i是節點i的度數，即節點i連接的邊數；

步驟三、初始層次數K＝1，根據下述公式計算前i個節點的歸屬程度不一致性f_1，i，令前i個節點在第1層的分界點g_1，i＝-1，社團結構穩定性FL_i＝0：

f_1，i＝cost(1，i)；

其中對于任意參數1＜＝p＜＝q＜＝N，

cost(p,q)=Σi=pq(wi+b-Li)2]]>

其中L_i為第i個節點的歸屬程度，參數w和b的值根據下述公式計算：

w=(q-p+1)Σi=pqiLi-Σi=pqiΣi=pqLi(q-p+1)Σi=pqi2-Σi=pqiΣi=pqi]]>

b=Σi=pqi2Σi=pqLi-Σi=pqiΣi=pqiLi(q-p+1)Σi=pqi2-Σi=pqiΣi=pqi]]>

步驟四、使層次數K增加1，根據下述公式計算前i個節點的歸屬程度不一致性f_K，i、前i個節點在第K層的分界點g_K，i以及社團結構穩定性FL_K：

f_K，i＝min{f_K-1，r+cost(r+1，i)}，r＝K-1，K，...，i-1；

gK,i=argminr{fK-1,r+cost(r+1,i)},r=K-1,K,...,i-1;]]>

FLK=Fitness(CK)=dinKdinK+doutK]]>

CK=∪k=1Klevelk]]>

C_K是層次數為K時的層次劃分，第k層的節點集合為level_k；din_K是K個層次中，處于同一層次的節點之間的邊數，dout_K是K個層次中，處于不同層次的節點之間的邊數；

步驟五、若社團結構穩定性比前一次增加，則記錄更新的層次劃分結果，重復步驟四；否則，停止計算，輸出當前的層次劃分結果。