[發(fā)明專利]一種基于拓?fù)鋭莸闹丿B復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201310392149.4
• 申請日: 2013-09-02
• 公開（公告）號(hào): CN103500168B
• 公開（公告）日: 2017-03-15
• 發(fā)明（設(shè)計(jì)）人: 王志曉;趙亞;陳昭彤
• 申請（專利權(quán)）人: 中國礦業(yè)大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06Q50/00
• 代理公司: 上海光華專利事務(wù)所31219
• 代理人: 徐秋平

技術(shù)領(lǐng)域

本發(fā)明屬于網(wǎng)絡(luò)識(shí)別技術(shù)領(lǐng)域，涉及一種網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法，特別是涉及一種基于拓?fù)鋭莸闹丿B復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法及系統(tǒng)。

背景技術(shù)

現(xiàn)實(shí)世界中的諸多系統(tǒng)都以復(fù)雜網(wǎng)絡(luò)的形式存在，如科技系統(tǒng)中的因特網(wǎng)，社會(huì)系統(tǒng)中的人際關(guān)系網(wǎng)，生態(tài)環(huán)境中的食物鏈網(wǎng)，以及電力網(wǎng)絡(luò)和交通網(wǎng)絡(luò)。社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)的一項(xiàng)重要研究內(nèi)容，對(duì)于分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，理解復(fù)雜系統(tǒng)的功能，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律、演化趨勢以及預(yù)測復(fù)雜網(wǎng)絡(luò)的行為都具有重要的意義。

目前已存在多種復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法，拓?fù)鋭莘椒ㄊ沁@些方法中的一個(gè)重要分支，該類方法具有時(shí)間復(fù)雜度低，無需領(lǐng)域或?qū)＜抑R(shí)等優(yōu)勢。淦文燕等人在發(fā)表于2009年《軟件學(xué)報(bào)》期刊的文章“一種基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法”中首次引入拓?fù)鋭菝枋鰪?fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間的作用與聯(lián)系，將每個(gè)社區(qū)視為拓?fù)鋭輬龅木植扛邉輩^(qū)，通過效益函數(shù)確定每個(gè)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的社區(qū)歸屬。該方法對(duì)重疊節(jié)點(diǎn)的確定條件比較嚴(yán)苛，從而導(dǎo)致重疊節(jié)點(diǎn)數(shù)量過于稀少，缺乏現(xiàn)實(shí)合理性。韓言妮等人在發(fā)表于2011年《Frontiers?of?Computer?Science?of?China》期刊的文章“Identifying?different?community?members?in?complex?networks?based?on?topology?potential”中提出基于拓?fù)鋭莸膹?fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)類型識(shí)別和重疊社區(qū)發(fā)現(xiàn)。該方法僅僅借助拓?fù)鋭菡页錾鐓^(qū)代表節(jié)點(diǎn)，即局部極值點(diǎn)，在以局部極值節(jié)點(diǎn)為中心往外擴(kuò)展劃分社區(qū)過程中，判斷節(jié)點(diǎn)社區(qū)歸屬的主要依據(jù)是節(jié)點(diǎn)度等有關(guān)節(jié)點(diǎn)連接關(guān)系的統(tǒng)計(jì)信息。張建沛等人在發(fā)表于2012年《電子學(xué)報(bào)》期刊的文章“基于歸屬不確定性的變規(guī)模網(wǎng)絡(luò)重疊社區(qū)識(shí)別”中提出一種出基于歸屬不確定性的變規(guī)模網(wǎng)絡(luò)重疊社區(qū)識(shí)別方法。該方法首先根據(jù)節(jié)點(diǎn)拓?fù)鋭葜档臉?gòu)成定義重疊節(jié)點(diǎn)社區(qū)歸屬不確定性側(cè)度公式，然后進(jìn)行變規(guī)模社區(qū)發(fā)現(xiàn)。在該方法中，社區(qū)的規(guī)模及節(jié)點(diǎn)社區(qū)歸屬完全依賴于預(yù)設(shè)的調(diào)節(jié)參數(shù)ξ。對(duì)于實(shí)際的復(fù)雜網(wǎng)絡(luò)，很難預(yù)先判斷每個(gè)社區(qū)的規(guī)模，因此預(yù)設(shè)一個(gè)合理的調(diào)節(jié)參數(shù)ξ十分困難。

綜上所述，現(xiàn)有基于拓?fù)鋭堇碚摰闹丿B復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法存在以下不足：（1）在節(jié)點(diǎn)拓?fù)鋭萦?jì)算過程中，假設(shè)所有復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)質(zhì)量相同，忽略節(jié)點(diǎn)間的質(zhì)量差異，缺乏現(xiàn)實(shí)合理性；（2）在社區(qū)發(fā)現(xiàn)過程中，沒有利用拓?fù)鋭輬霰旧硭尸F(xiàn)的峰谷結(jié)構(gòu)這一固有特性，而是通過效益函數(shù)等額外手段進(jìn)行判斷，增加了社區(qū)發(fā)現(xiàn)的復(fù)雜性。

發(fā)明內(nèi)容

鑒于以上所述現(xiàn)有技術(shù)的缺點(diǎn)，本發(fā)明的目的在于提供一種基于拓?fù)鋭莸闹丿B復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法及系統(tǒng)，用于解決現(xiàn)有基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法忽略網(wǎng)絡(luò)節(jié)點(diǎn)間的質(zhì)量差異及沒有利用拓?fù)鋭輬霰旧硭尸F(xiàn)的峰谷結(jié)構(gòu)這一固有特性，而是通過效益函數(shù)等額外手段進(jìn)行節(jié)點(diǎn)社區(qū)歸屬判斷等問題。

為實(shí)現(xiàn)上述目的及其他相關(guān)目的，本發(fā)明提供一種基于拓?fù)鋭莸闹丿B復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法及系統(tǒng)。

一種基于拓?fù)鋭莸闹丿B復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法，包括：根據(jù)給定的重疊復(fù)雜網(wǎng)絡(luò)，建立拓?fù)鋭輬觯?jì)算網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的拓?fù)鋭葜担桓鶕?jù)所述各節(jié)點(diǎn)的拓?fù)鋭葜邓阉鳙@得拓?fù)鋭輬鲋械乃蟹逦还?jié)點(diǎn)，從所有峰位節(jié)點(diǎn)中選取每個(gè)社區(qū)的代表節(jié)點(diǎn)；依次訪問各個(gè)代表節(jié)點(diǎn)，分別以每個(gè)代表節(jié)點(diǎn)為中心按廣度優(yōu)先向外擴(kuò)展，確定擴(kuò)展節(jié)點(diǎn)的社區(qū)歸屬；若擴(kuò)展節(jié)點(diǎn)位于拓?fù)鋭輬龅墓任唬瑒t為該社區(qū)與其他社區(qū)的重疊節(jié)點(diǎn)，擴(kuò)展停止；若擴(kuò)展節(jié)點(diǎn)位于拓?fù)鋭輬龅男逼挛唬瑒t為該社區(qū)的內(nèi)部節(jié)點(diǎn)，擴(kuò)展繼續(xù)；全部代表節(jié)點(diǎn)的擴(kuò)展過程結(jié)束后，未被訪問過的節(jié)點(diǎn)均位于拓?fù)鋭輬龅倪吘壩唬遣粚儆谌魏紊鐓^(qū)的孤立節(jié)點(diǎn)。

優(yōu)選地，所述網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)υ_i的拓?fù)鋭葜档挠?jì)算過程為：

其中，n為節(jié)點(diǎn)υ_i影響范圍內(nèi)的節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)υ_i的最大影響距離為m(υ_i)為節(jié)點(diǎn)υ_i的質(zhì)量；d_ij為節(jié)點(diǎn)υ_i與節(jié)點(diǎn)υ_j間的距離，用節(jié)點(diǎn)間的跳數(shù)進(jìn)行度量；σ為影響因子，σ∈(0,+∞)，用于控制節(jié)點(diǎn)的影響范圍；影響因子σ的選取過程為：

其中，N為所述復(fù)雜網(wǎng)絡(luò)包含的節(jié)點(diǎn)總數(shù)；分別對(duì)應(yīng)為節(jié)點(diǎn)υ₁,υ₂,...,υ_i,...,υ_N的拓?fù)鋭葜担粸闃?biāo)準(zhǔn)化因子。

優(yōu)選地，所述節(jié)點(diǎn)υ_i的質(zhì)量m(υ_i)的計(jì)算過程為：