[發明專利]基于復雜網絡社區發現的層次重疊核心藥群發現方法

無效

• 申請號: 201210122896.1
• 申請日: 2012-04-24
• 公開（公告）號: CN102682162A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 吳駿;孫道平;許峰;王志堅
• 申請（專利權）人: 河海大學
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06F17/30
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 湯志武

1.基于復雜網絡社區發現的層次重疊核心藥群發現方法，其特征是包括如下步驟：

步驟一TCMF網絡的構建方法：

a)對給定數量的方劑計算每味藥物的貢獻度和用量AC值并刪掉AC值小于一定閾值的藥物；

b)計算二元組藥物的AC值做刪減，再計算三元組藥物的AC值做刪減；

c)剩余三元組構建TCMF網絡；

d)結束；

步驟二TCMF網絡層次重疊核心藥群發現方法：

a)預處理步驟一得到的TCMF網絡；

b)對預處理后的TCMF網絡執行MAIGA算法進行藥群發現；

c)返回藥群劃分結果；

d)結束；

其中：

步驟一和步驟二所述的TCMF網絡為中醫藥方劑網絡；

步驟一-a所述的藥物在方劑中的AC值，即將藥物x的出現貢獻度p_x，計算公式為：

px=1F.size---(1)]]>

式中F.size為方劑F所包含的藥物種類數、即方劑中藥物數量；

步驟一-b所述的二元組藥物組合xy的AC值p_xy計算公式為：

pxy=2F.size---(2)]]>

步驟一-b所述的三元組藥物組合xyz的AC值p_xyz計算公式為：

pxyz=2F.size---(3)]]>

步驟一-c中所述的剩余三元組構建TCMF網絡為對AC值p_xyz大于給定閾值的三元組藥物組合構建網絡，其具體過程為：初始TCMF網絡為空、即沒有結點和邊，遍歷每個三元組藥物組合，把三元組中每一味藥物作為結點，若TCMF網絡中不存在該藥物結點，則將該結點加入網絡，然后將該三元組中的三個藥物結點每兩個組合為一條邊加入到TCMF網絡中，從而構建得到TCMF網絡；

步驟二-a中所述的預處理為對步驟一-c構建的TCMF網絡設定停詞閾值(max_ac)去除高AC值但是低相關的藥物；

步驟二-b中所述的MAIGA算法為極大團生長算法(MAx?clIque?Growing?Algorithm，簡寫MAIGA)，包括兩部分，極大團生長(MaxCliqueGrowing)算法和簇合并(ClusterMerging)算法，其具體過程如下：

MAIGA算法極大團生長部分，具體步驟為：

步驟0為起始步驟；

步驟1為給定TCMF網絡；

步驟2為計算TCMF網絡結點度存于哈希表hmNodeDegree；

步驟3為判斷hmNodeDegree是否為空，若不為空，執行步驟4，否則算法終止；

步驟4為取hmNodeDegree中度最大的結點u構建極大團C，構建過程為：尋找結點u及其鄰結點集合N(u)，若結點集N(u)∪{u}不是完全圖，則重復執行刪掉N(u)中結點x的工作直到N(u)∪{u}是完全圖，其中結點x在子圖N(u)∪{u}中的內度最??；

步驟5為判斷是否極大團C的結點數C.size＝2，若是，執行步驟6，否則執行步驟7；

步驟6為輸出C并且hmNodeDegree.remove(u)，執行步驟3；

步驟7為尋找C鄰結點集N_c，這里N_c←N(C，C)；U_c為C真子集，其中u為結點，S_c(S_c∈U_c)，U_c({S_c∈U_c|S_c.size＞1&u∈S_c})；

步驟8為判斷是否N_c為空，若空，執行步驟13，否則執行步驟9；

步驟9為任取N_c中一結點v；

步驟10為判斷結點v是否滿足d_vC+Cⁱⁿ≥σ(C.size+1)，若是執行步驟12，否則執行步驟11；

步驟11為N_c＝N_c-{v}，然后執行步驟8；

步驟12為執行算法Grow(C，v，C)，然后執行步驟11；

步驟13為求C真子集U_c，其中U_c({S_c∈U_c|S_c.size＞1&u∈S_c})；

步驟14為取任一S_c∈U_c尋找其鄰接點集中d_wS最大的結點w，執行Grow(S_c，w，C)；

步驟15為刪除結點u到C中其它結點的邊；

步驟16為更新hmNodeDegree，然后執行步驟3；

步驟17為算法的終止；

算法說明：極大團為極大完全圖，它不會包含在比它更大的完全圖中，哈希表hmNodeDegr存放<node，degree>鍵值對，Cⁱⁿ為社團C所包含邊數，N_c←N(C，C_x)為求極大團C的不包含在C_x中的鄰結點集合N_c。σ(|C|)為衡量社團生長合適度的密度函數：

σ(|C|)=|C|21-1|C|2---(4).]]>