異質(zhì)信息網(wǎng)絡(luò)中基于有向無環(huán)圖的影響力最大化算法

吳晴晴，周麗華*，寸軒懿，杜國王，姜懿庭

（1.云南大學(xué)信息學(xué)院，昆明 650000；2.云南師范大學(xué)信息學(xué)院，昆明 650000）

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，信息逐漸進(jìn)入了網(wǎng)絡(luò)化時(shí)代，使得信息的擴(kuò)散方式與擴(kuò)散途徑不斷發(fā)生變化。影響力最大化（Influence Maximization，IM）作為信息擴(kuò)散研究中的關(guān)鍵問題，旨在尋找社交網(wǎng)絡(luò)中最具影響力的用戶，最大限度地?cái)U(kuò)大影響力。由于該問題在市場(chǎng)營銷、廣告發(fā)布、輿情預(yù)警以及社會(huì)安定等方面具有重要的應(yīng)用背景，近年來引起了學(xué)術(shù)界的廣泛研究。Kempe 等［1］首先將IM 問題建模為一個(gè)算法問題，證明其是NP-hard 問題，并提出了貪心算法。為了克服傳統(tǒng)貪心算法的低效性，近年來研究者提出了許多近似算法和啟發(fā)式方法，例如基于仿真的算法［2-3］、基于中心度的算法［4-5］、基于路徑的算法［6-7］和基于社區(qū)的算法［8-10］。盡管這些研究已經(jīng)取得了可喜的成果，但是這些算法都是針對(duì)同質(zhì)信息網(wǎng)絡(luò)設(shè)計(jì)的。同質(zhì)信息網(wǎng)絡(luò)僅考慮了一種對(duì)象類型和一種關(guān)系類型，而現(xiàn)實(shí)中的社會(huì)網(wǎng)絡(luò)包含了多種對(duì)象類型和對(duì)象之間的多種關(guān)系類型，因此，同質(zhì)信息網(wǎng)絡(luò)的建?？赡軙?huì)忽略一些對(duì)象之間通過不同類型的關(guān)系而形成的隱性關(guān)系。這些隱性關(guān)系可能有助于信息在網(wǎng)絡(luò)中更好地?cái)U(kuò)散，因此，同時(shí)考慮多種對(duì)象類型以及對(duì)象之間的多種關(guān)系可能更有助于影響力最大化的研究。

異質(zhì)信息網(wǎng)絡(luò)（Heterogeneous Information Network，HIN）包含多種對(duì)象類型和多種關(guān)系類型，能夠更加精確合理地描述真實(shí)的社會(huì)網(wǎng)絡(luò)，刻畫不同類型對(duì)象之間的微妙關(guān)系，表達(dá)更豐富的語義信息。例如圖1 是異質(zhì)信息網(wǎng)絡(luò)DBLP（DataBase systems and Logic Programming）的網(wǎng)絡(luò)模式，其包含四種節(jié)點(diǎn)類型：作者（Author，A）、論文（Paper，P）、會(huì)議（Conference，C）、術(shù)語（Term，T）；六種關(guān)系類型：撰寫∕被撰寫、發(fā)表∕被發(fā)表、包含∕被包含。

圖1 DBLP網(wǎng)絡(luò)模式示意圖Fig.1 Schematic diagram of DBLP network mode

圖2 是DBLP 異質(zhì)信息網(wǎng)絡(luò)，異質(zhì)信息網(wǎng)絡(luò)中不同類型對(duì)象之間的異質(zhì)連接負(fù)載著不同的語義信息，在信息擴(kuò)散中起不同的作用，并且相互關(guān)聯(lián)、相互影響。例如A1P1C1表示作者A1撰寫的論文P1發(fā)表在會(huì)議C1上，若C1是影響力較高的會(huì)議，作者A1可能會(huì)因?yàn)樵跁?huì)議C1上發(fā)表了論文而提升個(gè)人的影響力，同樣若作者A1是學(xué)術(shù)界的知名人物，會(huì)議C1可能會(huì)因?yàn)樽髡逜1在會(huì)議C1上發(fā)表了論文而提高會(huì)議的影響力。異質(zhì)信息網(wǎng)絡(luò)中同種類型對(duì)象之間可能通過不同的路徑產(chǎn)生不同程度的影響，例如作者A1與A3可以通過路徑A1P2A3連接，表示A1與A3合著一篇論文P2，同時(shí)也可以通過路徑A1P1T1P4A3連接，表示A1與A3發(fā)表的論文包含同一種術(shù)語T1，作者A1與A3通過蘊(yùn)含著不同語義信息的路徑產(chǎn)生不同方面的影響。因此，異質(zhì)信息網(wǎng)絡(luò)中豐富的語義信息更有助于影響力最大化的研究。然而，由于異質(zhì)信息網(wǎng)絡(luò)具有復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)和豐富的語義信息，有效地利用異質(zhì)信息和探索豐富的語義是異質(zhì)信息網(wǎng)絡(luò)分析的難點(diǎn)。

圖2 DBLP異質(zhì)信息網(wǎng)絡(luò)Fig.2 DBLP HIN

有向無環(huán)圖（Directed Acyclic Graph，DAG）是一個(gè)無回路的有向圖，具有信息量大、表達(dá)力強(qiáng)的特點(diǎn)。首先，由于DAG 結(jié)構(gòu)是有向的，與異質(zhì)信息網(wǎng)絡(luò)結(jié)構(gòu)的有向性一致，并且DAG 是一種圖結(jié)構(gòu)，表達(dá)能力優(yōu)于元路徑，因此，其可以更好地描述不同對(duì)象之間的復(fù)雜關(guān)系，保留豐富的異質(zhì)信息；其次，DAG 結(jié)構(gòu)是無環(huán)的，有利于表達(dá)影響擴(kuò)散過程中一個(gè)節(jié)點(diǎn)對(duì)另一個(gè)節(jié)點(diǎn)的線性影響，避免了環(huán)形結(jié)構(gòu)導(dǎo)致的路徑冗余，從而使得影響力度量結(jié)果小于真實(shí)值；最后，由于一個(gè)節(jié)點(diǎn)的影響范圍有限，因此將節(jié)點(diǎn)的影響限制在一個(gè)局部的DAG 中是可行的。一個(gè)小規(guī)模的DAG 易于快速處理，從而有利于實(shí)現(xiàn)在線性時(shí)間內(nèi)計(jì)算DAG 中的影響力。

本文提出了一種在異質(zhì)信息網(wǎng)絡(luò)中基于DAG 的影響力最大化算法（DAG-based Influence Maximization algorithm in heterogeneous information networks，DAGIM）。DAGIM 首先為節(jié)點(diǎn)構(gòu)建DAG 結(jié)構(gòu)，然后基于構(gòu)建的DAG 度量節(jié)點(diǎn)的影響力并且動(dòng)態(tài)地選取最具影響力的節(jié)點(diǎn)，實(shí)現(xiàn)影響力最大化。DAG 結(jié)構(gòu)不僅可以描述不同類型對(duì)象之間的復(fù)雜關(guān)系，保留豐富的異質(zhì)信息，而且有利于降低異質(zhì)信息網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性，從而更好地實(shí)現(xiàn)影響力最大化。

本文的主要貢獻(xiàn)如下：

1）提出了一種構(gòu)建DAG 的方法，為每個(gè)節(jié)點(diǎn)構(gòu)建一個(gè)DAG 結(jié)構(gòu)，該DAG 包含了節(jié)點(diǎn)對(duì)不同類型節(jié)點(diǎn)的主要影響力。

2）提出了基于DAG 結(jié)構(gòu)度量節(jié)點(diǎn)影響力的方法，分別考慮對(duì)不同類型節(jié)點(diǎn)的影響來度量節(jié)點(diǎn)的總影響力。

3）提出了DAGIM，DAGIM 根據(jù)不同的擴(kuò)散任務(wù)，采用邊際增益策略有針對(duì)性地選擇種子節(jié)點(diǎn)。

在3 個(gè)真實(shí)數(shù)據(jù)集上通過實(shí)驗(yàn)驗(yàn)證了DAGIM 的有效性和效率，探索了參數(shù)對(duì)算法性能的影響，并驗(yàn)證了影響力度量的準(zhǔn)確性，最后驗(yàn)證了邊權(quán)重對(duì)信息擴(kuò)散效果的影響。

1 相關(guān)工作

影響力最大化在2003 年首次被Kempe 等［1］建模為一個(gè)算法問題，該算法具有高精度的近似結(jié)果，但同時(shí)具有較高的時(shí)間復(fù)雜度，不能擴(kuò)展到規(guī)模較大的網(wǎng)絡(luò)上。為了克服傳統(tǒng)貪心算法的低效性，一系列啟發(fā)式算法被提出以解決這個(gè)問 題［2-12］：Leskovec 等［2］提出的CELF（Cost-Effective Lazy Forward selection）算法利用子模特性大幅提高了傳統(tǒng)貪心算法的時(shí)間效率，但是，由于該算法通過大量的蒙特卡羅仿真得到近似的目標(biāo)函數(shù)，因此不適合在大規(guī)模網(wǎng)絡(luò)中應(yīng)用；Chen 等［4］對(duì)傳統(tǒng)的貪心算法進(jìn)行改進(jìn)，提出NewGreedy 算法，進(jìn)一步減少其運(yùn)行時(shí)間；Kim 等［6］提出了一種基于影響路徑的算法，考慮了多個(gè)影響路徑并假設(shè)它們相互獨(dú)立地傳播；Shang 等［9］利用社區(qū)結(jié)構(gòu)，通過考慮了節(jié)點(diǎn)的多鄰居勢(shì)來度量節(jié)點(diǎn)在社區(qū)中的影響力；Chen 等［11］證明了利用有向無環(huán)圖（DAG）計(jì)算影響在時(shí)間上與圖的大小成線性關(guān)系，并提出了一個(gè)針對(duì)線性閾值模型的可伸縮影響最大化算法；Qiu等［13］提出了一種有效的兩階段選擇的影響力最大化算法，并提出了折扣度下降技術(shù)和延遲前向技術(shù)選擇一定數(shù)量的候選節(jié)點(diǎn)；Qiu 等［14］提出了一種基于局部影響的全局選擇算法，提出了一種候選節(jié)點(diǎn)的兩階段過濾策略，大幅降低了運(yùn)行時(shí)間，并提出了一種新的目標(biāo)函數(shù)來估計(jì)節(jié)點(diǎn)集的影響擴(kuò)散。盡管目前存在的影響力最大化算法都取得了可喜的結(jié)果，但這些算法大多數(shù)是針對(duì)同質(zhì)信息網(wǎng)絡(luò)設(shè)計(jì)的［15］，不能應(yīng)用于復(fù)雜的異質(zhì)信息網(wǎng)絡(luò)。

隨著在線社交媒體的快速發(fā)展，大量涌現(xiàn)的多功能社交媒體網(wǎng)站包含許多不同類型的對(duì)象和對(duì)象之間復(fù)雜的交互，傳統(tǒng)的同質(zhì)信息網(wǎng)絡(luò)的建模方法不再適用，因此，越來越多的研究人員開始將這些互連的多類型數(shù)據(jù)建模為異質(zhì)信息網(wǎng)絡(luò)，利用網(wǎng)絡(luò)中豐富的語義信息來設(shè)計(jì)網(wǎng)絡(luò)分析方法，并且應(yīng)用于很多數(shù)據(jù)挖掘任務(wù)［16］，目前關(guān)于異質(zhì)信息網(wǎng)絡(luò)的研究主要集中在聚類［17-18］、分類［19-20］、相似性搜索［21-22］和鏈路預(yù)測(cè)［23］等。與同質(zhì)信息網(wǎng)絡(luò)相比，異質(zhì)信息網(wǎng)絡(luò)包含了更豐富的語義信息和全面的結(jié)構(gòu)信息，為數(shù)據(jù)挖掘提供了新的機(jī)遇與挑戰(zhàn)。如何有效利用異質(zhì)信息和探索豐富語義是異質(zhì)信息網(wǎng)絡(luò)分析的主要難點(diǎn)。作為有效利用異質(zhì)信息和探索語義的工具，元路徑被廣泛應(yīng)用于異質(zhì)信息網(wǎng)絡(luò)分析。很多基于元路徑的異質(zhì)信息網(wǎng)絡(luò)數(shù)據(jù)挖掘問題已經(jīng)被廣泛研究。例如，Sun 等［17］基于元路徑選擇提出了一種聚類算法，并提出了一種有效的迭代算法PathSelClus 來學(xué)習(xí)聚類質(zhì)量和元路徑權(quán)值相互增強(qiáng)的模型。Kong 等［19］研究了異構(gòu)網(wǎng)絡(luò)中同類對(duì)象之間的集合分類問題，開發(fā)了一種基于元路徑的異構(gòu)集體分類方法，有效地將標(biāo)簽分配給通過不同元路徑相互連接的一組實(shí)例；Sun 等［21］提出了PathSim 算法，用于在異質(zhì)信息網(wǎng)絡(luò)中基于元路徑的Top-K 相似度搜索；Chen 等［24］提出了一種基于半監(jiān)督元路徑的社區(qū)檢測(cè)算法，利用譜方法分析異構(gòu)信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并利用非負(fù)矩陣分解進(jìn)行社區(qū)檢測(cè)。大量的研究成果證明元路徑能夠有效提取異質(zhì)信息網(wǎng)絡(luò)中的異質(zhì)信息，但是，基于元路徑的分析方法還存在一些缺點(diǎn)：首先這些元路徑要么需要領(lǐng)域?qū)＜业南闰?yàn)知識(shí)進(jìn)行選擇，要么需要擴(kuò)展計(jì)算來合并所有小于預(yù)先確定長度的元路徑；其次路徑只是簡單的線性序列，對(duì)復(fù)雜網(wǎng)絡(luò)的表達(dá)能力有限。Liu 等［22］提出一種信息網(wǎng)絡(luò)中基于距離感知DAG的鄰近搜索算法，不僅能降低圖的復(fù)雜性，而且能夠保留豐富的信息。

盡管異質(zhì)信息網(wǎng)絡(luò)深受廣大研究者的青睞，但是關(guān)于異質(zhì)信息網(wǎng)絡(luò)中信息擴(kuò)散的研究相對(duì)較少，并且主要集中在預(yù)測(cè)任務(wù)中。例如Molaei 等［25］提出了一種異構(gòu)深度擴(kuò)散模型，利用元路徑作為網(wǎng)絡(luò)中的主要實(shí)體，以全局端到端視角，遍歷元路徑，通過一個(gè)連續(xù)的潛在表示來學(xué)習(xí)網(wǎng)絡(luò)的功能異質(zhì)結(jié)構(gòu)，然后在生成的特征上使用深度學(xué)習(xí)架構(gòu)來預(yù)測(cè)網(wǎng)絡(luò)中的擴(kuò)散過程。Liu 等［26］提出了一個(gè)生成圖形模型，利用與網(wǎng)絡(luò)中每個(gè)用戶相關(guān)的異質(zhì)鏈接信息和文本內(nèi)容來挖掘主題級(jí)的影響力，研究了影響的傳播和聚集機(jī)制：保守傳播和非保守傳播，并且分析了直接影響和間接影響，從而在異質(zhì)網(wǎng)絡(luò)中發(fā)現(xiàn)一些有趣的影響模式，提高了用戶行為預(yù)測(cè)的準(zhǔn)確性等。Li 等［27］提出了一種新的基于符號(hào)預(yù)測(cè)的異質(zhì)信息網(wǎng)絡(luò)行為預(yù)測(cè)模型，同時(shí)捕捉了用戶的社交鏈接（包括有標(biāo)簽鏈接和無標(biāo)簽鏈接）和用戶行為，提高預(yù)測(cè)的準(zhǔn)確性。針對(duì)異質(zhì)信息網(wǎng)絡(luò)中影響力最大化問題，Li 等［28］考慮了人的個(gè)體行為來模擬影響傳播，利用人節(jié)點(diǎn)對(duì)好友的激活具有不同的影響概率，構(gòu)造基于人的影響圖，并提出基于熵的啟發(fā)式方法來識(shí)別影響中的傳播者，以使影響傳播最大化。Wang等［29］首先闡述了異質(zhì)網(wǎng)絡(luò)中影響最大化問題，并提出了一種協(xié)同排序框架來同時(shí)選擇不同類型的種子集。Deng 等［30］提出了一個(gè)衡量影響模型來捕獲具有異質(zhì)性的社會(huì)影響，分別研究了不同因素的影響，并提出了一種影響最大化貪心算法選擇種子節(jié)點(diǎn)。目前，異質(zhì)信息網(wǎng)絡(luò)中影響力最大化的研究成果相對(duì)有限，有較大的研究空間。由于異質(zhì)信息網(wǎng)絡(luò)的結(jié)構(gòu)復(fù)雜且多樣，因此在異質(zhì)信息網(wǎng)絡(luò)中研究影響力最大化存在更多的挑戰(zhàn)和更高的復(fù)雜度。

2 相關(guān)概念

定義1異質(zhì)信息網(wǎng)絡(luò)［31］。一個(gè)異質(zhì)信息網(wǎng)絡(luò)定義為一個(gè)包含兩個(gè)映射函數(shù)φ和π的有向圖G=(V，E，T，R)，其中：V={v1，v2，…，vn}是節(jié)點(diǎn)集，E={e1，e2，…，en}是節(jié)點(diǎn)之間的邊集，T={t1，t2，…，tn}是節(jié)點(diǎn)類型集，|T|>1，R={r1，r2，…，rn}是邊類型集，|R|>1。φ：V→T是節(jié)點(diǎn)到節(jié)點(diǎn)類型的映射，π：E→R是邊到邊類型的映射。

定義2邊權(quán)重［32］。假設(shè)G中存在n種類型的邊，即R={r1，r2，…，rn}，同種類型的邊具有相同的權(quán)重，即?ri∈R，ri類型邊的權(quán)重 為wi∈(0，1)。若?u，v∈V，e(u，v) ∈E且π(e(u，v))=ri，則e(u，v)的邊權(quán)重定義為w(u，v)=wi。

定義 3路徑權(quán)重［32］。假 設(shè)P(v1，vm)=表示節(jié)點(diǎn)v1到節(jié)點(diǎn)vm的一條路徑，則P(v1，vm) 的路徑權(quán)重定義 為W(P(v1，vm))=w(v1，v2)×w(v2，v3)× …×w(vm-1，vm)。

證明 邊權(quán)重wi∈(0，1)表示節(jié)點(diǎn)之間的影響概率，由定義3 可知路徑權(quán)重W(P(v1，vm))隨著路徑的增長而減小，因此，節(jié)點(diǎn)v1對(duì)節(jié)點(diǎn)vm的影響概率隨著路徑的增長而減小。

定義4出、入鄰居。給定異質(zhì)信息網(wǎng)絡(luò)G=(V，E，T，R)，若節(jié)點(diǎn)u∈V到節(jié)點(diǎn)v∈Vu存在有向邊，則節(jié)點(diǎn)v稱為節(jié)點(diǎn)u的出鄰居，用Nout(u)表示節(jié)點(diǎn)u的出鄰居集；若節(jié)點(diǎn)v∈Vu到節(jié)點(diǎn)u存在有向邊，則節(jié)點(diǎn)v稱為節(jié)點(diǎn)u的入鄰居，用Nin(u)表示節(jié)點(diǎn)u的入鄰居集。若v∈Nout(u)，那么節(jié)點(diǎn)u對(duì)節(jié)點(diǎn)v的影響概率表示為w(u，v)；若v∈Nin(u)，那么節(jié)點(diǎn)v對(duì)節(jié)點(diǎn)u的影響概率表示為w(v，u)。

問題定義 給定一個(gè)異質(zhì)信息網(wǎng)絡(luò)G=(V，E，T，R)，本文的目標(biāo)是在度量節(jié)點(diǎn)影響力時(shí)利用異質(zhì)信息網(wǎng)絡(luò)中豐富的語義信息，考慮一個(gè)節(jié)點(diǎn)對(duì)不同類型節(jié)點(diǎn)的影響，根據(jù)不同的擴(kuò)散任務(wù)，有針對(duì)性地選擇一組最具影響的節(jié)點(diǎn)S，在特定的擴(kuò)散模型下，最大化總激活節(jié)點(diǎn)數(shù)S*：

解決上述問題的關(guān)鍵是如何度量節(jié)點(diǎn)的影響，并選擇影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。

由于異質(zhì)信息網(wǎng)絡(luò)中包含多種節(jié)點(diǎn)類型，不同類型的節(jié)點(diǎn)具有不同的性質(zhì)，并且它們的影響力代表著不同的含義，在信息擴(kuò)散中起不同的作用。因此，本文在研究異質(zhì)信息網(wǎng)絡(luò)中的影響力最大化問題時(shí)，將根據(jù)不同的目標(biāo)對(duì)象選擇不同的種子節(jié)點(diǎn)，從而更好地實(shí)現(xiàn)影響力最大化。例如，在DBLP 網(wǎng)絡(luò)中，作者對(duì)論文產(chǎn)生影響的同時(shí)，通過論文的連接也會(huì)對(duì)會(huì)議、術(shù)語和作者產(chǎn)生一定影響，假設(shè)信息擴(kuò)散任務(wù)是影響更多的作者，那么本文將會(huì)選擇對(duì)作者影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)進(jìn)行信息擴(kuò)散。

3 DAGIM

DAGIM 首先為節(jié)點(diǎn)構(gòu)建DAG 結(jié)構(gòu)，然后基于構(gòu)建的DAG 度量節(jié)點(diǎn)的影響力并且動(dòng)態(tài)地選取最具影響力的節(jié)點(diǎn)，實(shí)現(xiàn)影響力最大化。

3.1 構(gòu)建DAG

為了度量節(jié)點(diǎn)的影響力，本文首先為每個(gè)節(jié)點(diǎn)u∈V構(gòu)建一個(gè)DAG。構(gòu)建方法為：將節(jié)點(diǎn)u作為DAG 的源節(jié)點(diǎn)，查找節(jié)點(diǎn)u的出鄰居，將出鄰居添加到DAG 中，然后再查找出鄰居的出鄰居，并將它們添加到DAG 中，不斷循環(huán)此過程。在此過程中，若不加任何約束條件，最終構(gòu)建的DAG 可能非常大。根據(jù)性質(zhì)1 可知，隨著路徑的增長，節(jié)點(diǎn)u對(duì)一些遠(yuǎn)距離節(jié)點(diǎn)的影響非常小，并且構(gòu)建大規(guī)模的DAG 結(jié)構(gòu)非常耗時(shí)。因此，本文在構(gòu)建DAG 的過程中將引入一個(gè)參數(shù)λ(λ∈[0，1])來約束節(jié)點(diǎn)之間的路徑權(quán)重，從而控制DAG 的大小，使得節(jié)點(diǎn)u一定影響范圍內(nèi)的鄰居節(jié)點(diǎn)添加到DAG中，保證構(gòu)建的DAG 涵蓋節(jié)點(diǎn)u對(duì)其他節(jié)點(diǎn)的主要影響，而忽略節(jié)點(diǎn)u的次要影響。圖3 所示展示了一個(gè)異質(zhì)信息網(wǎng)絡(luò)中節(jié)點(diǎn)A1的DAG 結(jié)構(gòu)。DGA 結(jié)構(gòu)清晰地描述了A1與其他節(jié)點(diǎn)之間的關(guān)系，例如A1與A3合著過論文，作者A1在會(huì)議C2上發(fā)表過論文等，A1與A5之間可以通過6 條路徑到達(dá)。DAG 結(jié)構(gòu)針對(duì)一個(gè)節(jié)點(diǎn)將異質(zhì)信息局部化，保留了與其相關(guān)的主要信息，相較于整個(gè)異質(zhì)信息網(wǎng)絡(luò)，節(jié)點(diǎn)之間的關(guān)系更加明確和清晰。

圖3 加權(quán)路徑的HIN和節(jié)點(diǎn)A1的DAG結(jié)構(gòu)Fig.3 HIN with weighting path and DAG structure of A1

在構(gòu)建Du(X，Y)的過程中，本文將節(jié)點(diǎn)u的DAG 表示為Du(X，Y)，其中X表示節(jié)點(diǎn)集，Y表示邊集。首先將源節(jié)點(diǎn)u添加到X中，然后從節(jié)點(diǎn)u開始查找它的出鄰居v∈Nout(u)，若X中不包含v且節(jié)點(diǎn)u到節(jié)點(diǎn)v的路徑權(quán)重W(P(u，v))≥λ，則將v添加到X中，添加X中的節(jié)點(diǎn)到節(jié)點(diǎn)v的有向邊到Y(jié)中，然后依次查找Nout(u)的出鄰居節(jié)點(diǎn)，不斷重復(fù)上述操作。隨著路徑長度不斷增長，路徑權(quán)重逐漸減小，當(dāng)W(P(u，v)) <λ時(shí)，循環(huán)結(jié)束。本文所提的異質(zhì)信息網(wǎng)絡(luò)中構(gòu)建DAG 的方法如算法1 所示。

算法1 構(gòu)建Du(X，Y)。

3.2 影響力度量

異質(zhì)信息網(wǎng)絡(luò)中包含多種類型的節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)可能對(duì)不同類型的節(jié)點(diǎn)產(chǎn)生不同程度的影響。因此，本文將分別考慮對(duì)不同類型節(jié)點(diǎn)的影響來度量節(jié)點(diǎn)的總影響力。由于Du(X，Y)包含了節(jié)點(diǎn)u一定影響范圍內(nèi)的鄰居節(jié)點(diǎn)，所以Du(X，Y)涵蓋了節(jié)點(diǎn)u對(duì)不同類型節(jié)點(diǎn)的大部分影響力。本節(jié)考慮如何基于Du(X，Y)度量節(jié)點(diǎn)u對(duì)這些節(jié)點(diǎn)的影響力，從而得到節(jié)點(diǎn)u的總影響力。

在Du(X，Y)中，若u是激活節(jié)點(diǎn)，利用DAG 結(jié)構(gòu)的特點(diǎn)，節(jié)點(diǎn)u可以通過蘊(yùn)含不同語義信息的路徑達(dá)到Du(X，Y)中的任意一個(gè)節(jié)點(diǎn)。由于到達(dá)不同節(jié)點(diǎn)的路徑條數(shù)、路徑長度及路徑上邊的類型均不相同，因此u對(duì)不同節(jié)點(diǎn)產(chǎn)生的影響程度不同。對(duì)于?v∈Xu，假設(shè)節(jié)點(diǎn)u到節(jié)點(diǎn)v存在l條路徑，節(jié)點(diǎn)u到節(jié)點(diǎn)v的影響概率記為IPu(v)，則IPu(v)的計(jì)算方式如式（2）所示：

算法2 描述了計(jì)算節(jié)點(diǎn)u對(duì)Du(X，Y)中節(jié)點(diǎn)的影響概率過程。

算法2 計(jì)算節(jié)點(diǎn)u對(duì)Du(X，Y)中節(jié)點(diǎn)的影響概率。

一般而言，Du(X，Y)中包含了多種類型的節(jié)點(diǎn)，而節(jié)點(diǎn)u對(duì)每種類型節(jié)點(diǎn)的影響意義不同，因此本文將分別計(jì)算對(duì)不同類型節(jié)點(diǎn)的影響力。節(jié)點(diǎn)u對(duì)t∈T類型節(jié)點(diǎn)的影響力表示為Inft(u)，如式（3）所示：

設(shè)Du(X，Y)中包含n種節(jié)點(diǎn)類型T={t1，t2，…，tn}，本文將結(jié)合對(duì)n種類型節(jié)點(diǎn)的影響來度量節(jié)點(diǎn)u的總影響力，用Inf(u)表示，如式（4）所示：

其中αi等于1 或0，若αi=1，則表示度量節(jié)點(diǎn)u的影響力時(shí)考慮了對(duì)ti類型節(jié)點(diǎn)的影響，否則就忽略了對(duì)ti類型節(jié)點(diǎn)的影響。

例在圖3（b）中，A1到C1之間存在一條路徑，即，A1對(duì)C1的影響概率為IPA1(C1)=0.5× 0.2=0.1；A1對(duì)會(huì)議的影響 為Inf會(huì)議(A1)=IPA1(C1)+IPA1(C2)=0.1+0.1=0.2；設(shè)αi=1，A1的總影響力為Inf(A1)=Inf論文(A1)+Inf會(huì)議(A1)+Inf術(shù)語(A1)+Inf作者(A1)=1.2+0.2+0.15+0.65=2.2。

3.3 DAGIM描述

DAGIM 首先構(gòu)建DAG 結(jié)構(gòu)來度量節(jié)點(diǎn)的影響力，然后采用邊際增益策略選擇種子節(jié)點(diǎn)，選擇一個(gè)影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)后，去除其他節(jié)點(diǎn)與其重疊的影響，重新計(jì)算剩余節(jié)點(diǎn)的影響力，從中再選擇一個(gè)影響力最大的節(jié)點(diǎn)作為下一個(gè)種子節(jié)點(diǎn)，重復(fù)上述操作，直到選取一定數(shù)量的種子節(jié)點(diǎn)。

算法3 DAGIM。

輸入G(V，E，T，R)，參數(shù)λ，種子節(jié)點(diǎn)數(shù)量k；

輸出 種子集S。

算法3 描述了DAGIM 的偽代碼，首先運(yùn)用算法1 構(gòu)建Du(X，Y)，然后利用算法2 計(jì)算節(jié)點(diǎn)u對(duì)Du(X，Y)中的每個(gè)節(jié)點(diǎn)的影響概率IPu(v)，利用式（3）、（4）計(jì)算節(jié)點(diǎn)u的影響力Inf(u)。為了避免影響力重復(fù)計(jì)算，算法3 采用邊際增益策略選擇k個(gè)種子節(jié)點(diǎn)。最后，這些種子節(jié)點(diǎn)通過特定的擴(kuò)散模型在網(wǎng)絡(luò)中進(jìn)行擴(kuò)散，使影響范圍達(dá)到最大。

算法1 的時(shí)間復(fù)雜度為O(nd)，算法2 的時(shí)間復(fù)雜度為O(nml)，因此，DAGIM 的時(shí)間復(fù)雜度為O(nd+nml+k)，其中n表示異質(zhì)信息網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量n=|V|；d表示節(jié)點(diǎn)的平均度；m表示DAG 中節(jié)點(diǎn)的平均數(shù)量；l表示DAG 中節(jié)點(diǎn)的平均路徑數(shù)量；k表示所選取的種子節(jié)點(diǎn)的數(shù)量k=|S|。

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)準(zhǔn)備

數(shù)據(jù)集 本文使用了3 個(gè)真實(shí)的異質(zhì)信息網(wǎng)絡(luò)數(shù)據(jù)集（DBLP 數(shù)據(jù)集、Yelp 數(shù)據(jù)集和Amazon 數(shù)據(jù)集）驗(yàn)證DAGIM的性能。DBLP 數(shù)據(jù)集包含4 種對(duì)象類型和三種關(guān)系類型，Yelp 數(shù)據(jù)集包含4 種對(duì)象類型和4 種關(guān)系類型，Amazon 數(shù)據(jù)集包含5 種對(duì)象和4 種關(guān)系類型，3 個(gè)數(shù)據(jù)集的詳細(xì)描述如表1 所示。

表1 數(shù)據(jù)集詳細(xì)信息Tab.1 Dataset detailed information

對(duì)比算法 為了驗(yàn)證所提DAGIM 的有效性，本文采用了PageRank［12］、Degree［12］、基于元路徑的信息熵（Meta-Pathbased Information Entropy，MPIE）［33］和局部有向無環(huán)圖（Local Directed Acyclic Graph，LDAG）［11］作為對(duì)比算法。PageRank 算法度量每個(gè)節(jié)點(diǎn)的重要程度，然后選擇PageRank值高的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。Degree 算法是一種基于度中心的影響力度量方法。MPIE 算法是面向異質(zhì)信息網(wǎng)絡(luò)的方法，該方法首先通過元路徑將異質(zhì)網(wǎng)絡(luò)轉(zhuǎn)化為同質(zhì)網(wǎng)絡(luò)，然后度量節(jié)點(diǎn)的直接影響力和間接影響力，最后結(jié)合兩種影響力選取種子節(jié)點(diǎn)。LDAG 算法是基于局部DAG 的影響力最大化算法。Degree 算法、PageRank 算法和LADG 算法均采用文獻(xiàn)中最佳的參數(shù)值。由于這些算法只針對(duì)一種類型的節(jié)點(diǎn)和一種類型的邊，所以在實(shí)驗(yàn)中運(yùn)行對(duì)比算法時(shí)不區(qū)分節(jié)點(diǎn)和邊的類型，但運(yùn)行DAGIM 和對(duì)比實(shí)驗(yàn)結(jié)果時(shí)，需要區(qū)分節(jié)點(diǎn)和邊的類型。

由于異質(zhì)信息網(wǎng)絡(luò)中包含多種類型的節(jié)點(diǎn)，不同類型的節(jié)點(diǎn)具有不同的性質(zhì)，并且它們的影響力代表著不同的含義，在信息擴(kuò)散中起不同的作用，因此，將不同類型節(jié)點(diǎn)的影響力進(jìn)行比較是不合理且沒有意義的。為了使實(shí)驗(yàn)結(jié)果有意義，在實(shí)驗(yàn)過程中，本文選擇了一種節(jié)點(diǎn)類型作為研究對(duì)象，即DBLP 網(wǎng)絡(luò)中的作者節(jié)點(diǎn)，Yelp 和Amazon 網(wǎng)絡(luò)中的用戶節(jié)點(diǎn)。其他類型節(jié)點(diǎn)的比較與此類似，不再贅述。

擴(kuò)散模型 本文采用線性閾值模型（Linear Threshold，LT）作為擴(kuò)散模型。對(duì)于LT 模型，每個(gè)非激活節(jié)點(diǎn)有一個(gè)[0，1]范圍的激活閾值，本文將每個(gè)節(jié)點(diǎn)的入度邊的權(quán)值歸一化，使它們的和為1，若非激活節(jié)點(diǎn)的已激活鄰居對(duì)其的影響力總和超過該閾值，則該節(jié)點(diǎn)被激活。

評(píng)價(jià)指標(biāo) 影響范圍（Influence Spread）［10］是一種廣泛使用的評(píng)價(jià)指標(biāo)，定義為擴(kuò)散結(jié)束時(shí)能夠成功激活的節(jié)點(diǎn)數(shù)，Influence Spread值越大表明算法的性能越好，因此本文使用Influence Spread 作為算法性能的評(píng)價(jià)指標(biāo)。為了消除結(jié)果的偶然性，通過執(zhí)行10 000 次蒙特卡羅（Monte Carlo，MC）仿真來估計(jì)影響擴(kuò)散值，并隨機(jī)設(shè)置每個(gè)節(jié)點(diǎn)的激活閾值。本文采用時(shí)間（Time）作為算法效率的評(píng)價(jià)指標(biāo)，其數(shù)值越小表示算法的運(yùn)行時(shí)間越短，算法的運(yùn)行效率越高。

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 有效性驗(yàn)證

對(duì)于Degree 算法、PageRank 算法、MPIE 算法和LDAG 算法，實(shí)驗(yàn)中將所有邊權(quán)重設(shè)為0.5。DAGIM 區(qū)分不同的節(jié)點(diǎn)類型和不同的邊類型，DBLP 網(wǎng)絡(luò)中不同類型的邊權(quán)重分別設(shè)為wAP=0.5，wPC=0.3，wPT=0.2，Yelp 網(wǎng)絡(luò)中不同類型的邊權(quán)重設(shè)為wUU=0.3，wUB=0.4，wBCat=0.1，wBCit=0.2，Amazon 網(wǎng)絡(luò)中，wUI=0.4，wIB=0.3，wIC=0.2，wIV=0.1。在影響力擴(kuò)散階段，本文將使用LT 模型作為擴(kuò)散模型，并將邊權(quán)值歸一化，避免了權(quán)值的不同導(dǎo)致結(jié)果的差異性。

四種算法在DBLP、Yelp 和Amazon 數(shù)據(jù)集上針對(duì)不同初始種子節(jié)點(diǎn)數(shù)目K最終激活的作者節(jié)點(diǎn)和用戶節(jié)點(diǎn)數(shù)如圖4所示。

圖4 不同算法影響范圍的對(duì)比Fig.4 Impact range comparison of different algorithms

從圖4 可以看出，在三個(gè)數(shù)據(jù)集上，DAGIM 表現(xiàn)最好，Degree 算法和PageRank 算法表現(xiàn)最差，LDAG 算法優(yōu)于這兩種算法，說明DAG 結(jié)構(gòu)有助于準(zhǔn)確地度量節(jié)點(diǎn)的影響力，區(qū)分節(jié)點(diǎn)和邊的類型能夠提升節(jié)點(diǎn)影響力度量的精度。MPIE算法在DBLP 和Yelp 這兩個(gè)數(shù)據(jù)集上表現(xiàn)不佳，主要原因可能是MPIE 算法實(shí)驗(yàn)表現(xiàn)依賴于元路徑的選取，使用多條元路徑引入了噪聲，同時(shí)影響了網(wǎng)絡(luò)結(jié)構(gòu)的完整性，導(dǎo)致節(jié)點(diǎn)影響力的度量不夠準(zhǔn)確。在Amazon 數(shù)據(jù)集中，MPIE 算法的性能和DAGIM 接近，是因?yàn)檫x取了比較合適的元路徑，對(duì)節(jié)點(diǎn)影響力的度量較為準(zhǔn)確。

4.2.2 效率對(duì)比

為了比較評(píng)價(jià)不同算法的效率，本節(jié)將種子節(jié)點(diǎn)數(shù)量K分別設(shè)為{10，20，30，40，50}，對(duì)比不同算法選出K個(gè)種子節(jié)點(diǎn)的運(yùn)行時(shí)間。表2 展示了DBLP、Yelp 以及Amazon 數(shù)據(jù)集上的運(yùn)行時(shí)間。

表2 不同算法在三個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間比較Tab.2 Running time comparison of different algorithms on three datasets

從表2 可以看出，PageRank 算法和Degree 算法具有較高的時(shí)間效率，但是從圖4 可知它們的性能相對(duì)較差。MPIE算法的時(shí)間復(fù)雜度也較高，因?yàn)樵撍惴ㄐ枰獜漠愘|(zhì)網(wǎng)絡(luò)中提取同質(zhì)子網(wǎng)，然后進(jìn)行節(jié)點(diǎn)信息熵的計(jì)算。DAGIM 和LDAG算法都是基于DAG 結(jié)構(gòu)的算法，構(gòu)建節(jié)點(diǎn)的DAG 需要花費(fèi)一定的時(shí)間，因此，這兩種算法效率相對(duì)較低；但是DAGIM的效率高于LDAG 算法，這是由于DAGIM 只是針對(duì)特定類型的節(jié)點(diǎn)構(gòu)建DAG，而不是對(duì)所有類型的節(jié)點(diǎn)都構(gòu)建。此外，從表2 中可以看出，所有算法的運(yùn)行時(shí)間隨著K值的增大而增加，但是增加幅度不大。這是因?yàn)椋篋egree 和PageRank 時(shí)間復(fù)雜度較低，屬于高效率算法，受參數(shù)K值的影響較??；MPIE 算法的運(yùn)行時(shí)間大部分消耗在了同質(zhì)網(wǎng)絡(luò)的提取以及節(jié)點(diǎn)熵值的計(jì)算，所以受參數(shù)K值的影響也較??；DAGIM 和LDAG 算法的運(yùn)行時(shí)間主要消耗在DAG 的構(gòu)建，選擇種子節(jié)點(diǎn)消耗的時(shí)間相對(duì)較少，因此，這兩種算法對(duì)參數(shù)K的變化不敏感。

4.2.3 算法參數(shù)的影響

DAGIM 中參數(shù)λ控制著DAG 的大小，隨著λ值的減小，DAG 涵蓋的鄰居節(jié)點(diǎn)越多，并且DAG 的規(guī)模越大且越復(fù)雜，這可能有助于更全面地度量節(jié)點(diǎn)的影響力。因此，為了探索DAG 結(jié)構(gòu)如何影響DAGIM 性能，本文將算法參數(shù)λ為分別設(shè)置為{0.1，0.08，0.06，0.04，0.02，0.008，0.005，0.001}進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖5 所示，從中可以看出隨著λ值的減小，在DBLP 以及Yelp 這兩個(gè)數(shù)據(jù)集上Influence Spread 的值逐漸增大，這表明復(fù)雜的DAG 結(jié)構(gòu)涵蓋了更多的異質(zhì)信息，有助于更準(zhǔn)確地度量節(jié)點(diǎn)的影響力，從而提升影響力最大化效果。在Amazon 數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果較為特殊，參數(shù)λ在取前六個(gè)值時(shí)，Influence Spread 的變化趨勢(shì)和其余兩個(gè)數(shù)據(jù)集保持一致，但在λ={0.005，0.001}時(shí)，Influence Spread 的值出現(xiàn)下降。這是由于Amazon 數(shù)據(jù)的數(shù)據(jù)分布比較緊密，隨著λ值的減小，DAG 涵蓋的節(jié)點(diǎn)增多，產(chǎn)生了噪聲，導(dǎo)致節(jié)點(diǎn)影響力的度量不夠準(zhǔn)確、Influence Spread值減小的情況發(fā)生。同時(shí)，構(gòu)建復(fù)雜的DAG 需要花費(fèi)大量的時(shí)間，并且從圖中可以看出當(dāng)λ值減小到一定程度時(shí)，Influence Spread值幾乎保持不變，這是因?yàn)殡S著路徑長度的增長，節(jié)點(diǎn)對(duì)一些遠(yuǎn)距離節(jié)點(diǎn)的影響微乎其微，不足以激活它們。因此，有必要選擇適當(dāng)?shù)摩藖硗瑫r(shí)兼顧DAGIM 的有效性和效率。

圖5 參數(shù)λ對(duì)影響范圍的影響Fig.5 Effect of parameterλ on influence spread

4.2.4 影響力度量的準(zhǔn)確性

異質(zhì)信息網(wǎng)絡(luò)中包含多種節(jié)點(diǎn)類型，一個(gè)節(jié)點(diǎn)對(duì)不同類型的節(jié)點(diǎn)產(chǎn)生不同程度的影響。為了評(píng)價(jià)通過多種類型節(jié)點(diǎn)的影響來度量節(jié)點(diǎn)影響力是否有助于更準(zhǔn)確地度量節(jié)點(diǎn)的影響力，將使用DAGIM 在三個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試。

在度量節(jié)點(diǎn)影響力時(shí)，本文采用了兩種度量方式，僅考慮對(duì)一種類型節(jié)點(diǎn)的影響和考慮對(duì)所有類型節(jié)點(diǎn)的影響，分別用INFone 和INFmult 表示。實(shí)驗(yàn)考慮DBLP 網(wǎng)絡(luò)中的作者節(jié)點(diǎn)、Yelp 和Amazon 網(wǎng)絡(luò)中的用戶節(jié)點(diǎn)作為研究對(duì)象，因此，對(duì)于僅考慮一種類型節(jié)點(diǎn)的情況，DBLP 選擇作者節(jié)點(diǎn)，Yelp 和Amazon 選擇用戶節(jié)點(diǎn)。根據(jù)影響力的度量結(jié)果，選出K（K={10，20，30，40，50}）個(gè)種子節(jié)點(diǎn)并比較它們的Influence Spread值。實(shí)驗(yàn)結(jié)果如圖6 所示，從結(jié)果中可以看出，INFmult 的Influence Spread值高于INFone，并且兩者之間的差距隨著K值增大而增大，說明考慮多種類型節(jié)點(diǎn)的影響有利于準(zhǔn)確地度量節(jié)點(diǎn)的影響力。

圖6 不同影響力度量方式的對(duì)比Fig.6 Comparison of different measures of influence

4.2.5 邊權(quán)重的影響

異質(zhì)信息網(wǎng)絡(luò)中包含多種類型的邊，而不同類型的邊在信息擴(kuò)散中起不同的作用，本節(jié)將使用DAGIM 在三個(gè)異質(zhì)信息網(wǎng)絡(luò)中探索不同類型的邊在信息擴(kuò)散任務(wù)中的重要程度。本文假設(shè)所有類型的邊權(quán)重和為1：對(duì)于DBLP 數(shù)據(jù)集，wAP+wPC+wPT=1；對(duì) 于Yelp 數(shù)據(jù)集，wUU+wUB+wBCat+wBCit=1；對(duì)于Amazon 數(shù)據(jù)集，wUI+wIB+wIC+wIV=1。本節(jié)將設(shè)置多組不同的邊權(quán)重組合進(jìn)行實(shí)驗(yàn)，選出K=50 個(gè)種子節(jié)點(diǎn)并比較它們的Influence Spread。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 邊權(quán)重對(duì)影響范圍的影響Fig.7 Effect of edge weights on influence spread

從圖7（a）可以觀察到，在DBLP 網(wǎng)絡(luò)中，當(dāng)Influence Spread 達(dá)到最大值時(shí)，邊權(quán)重wAP是三者中的最大值，這表明作者與論文之間的關(guān)系在信息擴(kuò)散中起關(guān)鍵作用。當(dāng)Influence Spread 達(dá)到最小值時(shí)，邊權(quán)重wPT是三者中的最大值，這表明論文與術(shù)語之間的關(guān)系在信息擴(kuò)散中的影響相對(duì)較小。當(dāng)wAP=0.5，wPC=0.3，wPT=0.2 時(shí)，Influence Spread值達(dá)到最大，因此本文在DBLP 數(shù)據(jù)集上驗(yàn)證算法的有效性實(shí)驗(yàn)中采用了這組參數(shù)。從圖7（b）中可以觀察到，在Yelp網(wǎng)絡(luò)中，當(dāng)Influence Spread 達(dá)到最大值時(shí)，邊權(quán)重wUB是最大值，這表明用戶與商業(yè)之間的關(guān)系在信息擴(kuò)散中起關(guān)鍵作用。當(dāng)Influence Spread值較小時(shí)，邊權(quán)重wBCat或wBCit是最大值，這表明商業(yè)與領(lǐng)域之間的關(guān)系、商業(yè)與城市之間的關(guān)系在信息擴(kuò)散中的影響相對(duì)較小。當(dāng)wUU=0.3，wUB=0.4，wBCat=0.1，wBCit=0.2 時(shí)，Influence Spread值達(dá)到最大，因此本文在數(shù)據(jù)集上驗(yàn)證算法的有效性實(shí)驗(yàn)中采用了這組參數(shù)。在Amazon 網(wǎng)絡(luò)中，當(dāng)Influence Spread 達(dá)到最大值時(shí)，邊權(quán)重wUI是最大值，這表明用戶與商品之間的關(guān)系在信息擴(kuò)散中起關(guān)鍵作用。當(dāng)Influence Spread值較小時(shí)，邊權(quán)重wIV是最大值，這表明商品與評(píng)價(jià)之間的關(guān)系在信息擴(kuò)散中的影響相對(duì)較小。當(dāng)wUI=0.4，wIB=0.3，wIC=0.2，wIV=0.1 時(shí)，Influence Spread值達(dá)到最大，因此本文在Amazon 數(shù)據(jù)集上驗(yàn)證算法的有效性實(shí)驗(yàn)中采用了這組參數(shù)。

5 結(jié)語

本文提出了一種在異質(zhì)信息網(wǎng)絡(luò)中基于DAG 的影響力最大化算法DAGIM，該算法首先為每個(gè)節(jié)點(diǎn)構(gòu)建DAG，然后利用DAG 結(jié)構(gòu)度量節(jié)點(diǎn)的影響力，根據(jù)度量結(jié)果動(dòng)態(tài)地選擇影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，從而實(shí)現(xiàn)影響力最大化。由于DAGIM 中控制DAG 結(jié)構(gòu)大小的最佳參數(shù)是通過多次實(shí)驗(yàn)得到的，在未來研究中，將考慮根據(jù)不同的網(wǎng)絡(luò)結(jié)構(gòu)自適應(yīng)地選擇最佳參數(shù)。此外，針對(duì)不同的數(shù)據(jù)集，本文根據(jù)先驗(yàn)知識(shí)給不同類型的邊賦予不同的權(quán)重，在未來研究中，可以考慮通過表征學(xué)習(xí)得到不同類型邊的權(quán)重，使得邊權(quán)重更加真實(shí)有效。