计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2014年
6期
1057-1063
,共7页
网络影响最大化%最小种子集%简单多数阈值%计数排序%Barabasi-Albert网络
網絡影響最大化%最小種子集%簡單多數閾值%計數排序%Barabasi-Albert網絡
망락영향최대화%최소충자집%간단다수역치%계수배서%Barabasi-Albert망락
network influence maximization%minimum seed set%simple majority threshold%counting sort%Barabasi-Albert network
网络最小种子集问题与网络影响最大化问题相关,研究的是对于具有节点阈值的网络,构造网络的最小节点子集,使得如果这个子集中的节点是活的,则在给定的影响传播模型下整个网络都受到影响.为此提出了新的贪心算法,以节点的度与阈值的差为关键值对网络节点进行计数排序,然后取值最小的节点进行处理.新算法在时间复杂度上改进了基于最小堆的种子点选取算法.在简单多数阈值模型上针对经典的无标度网络得到了所构造的种子集规模上界.实验在随机生成网络和一些实际网络数据集上进行,结果表明所提方法的有效性,特别在无标度网络上生成的种子集具有比相关算法更小的规模.
網絡最小種子集問題與網絡影響最大化問題相關,研究的是對于具有節點閾值的網絡,構造網絡的最小節點子集,使得如果這箇子集中的節點是活的,則在給定的影響傳播模型下整箇網絡都受到影響.為此提齣瞭新的貪心算法,以節點的度與閾值的差為關鍵值對網絡節點進行計數排序,然後取值最小的節點進行處理.新算法在時間複雜度上改進瞭基于最小堆的種子點選取算法.在簡單多數閾值模型上針對經典的無標度網絡得到瞭所構造的種子集規模上界.實驗在隨機生成網絡和一些實際網絡數據集上進行,結果錶明所提方法的有效性,特彆在無標度網絡上生成的種子集具有比相關算法更小的規模.
망락최소충자집문제여망락영향최대화문제상관,연구적시대우구유절점역치적망락,구조망락적최소절점자집,사득여과저개자집중적절점시활적,칙재급정적영향전파모형하정개망락도수도영향.위차제출료신적탐심산법,이절점적도여역치적차위관건치대망락절점진행계수배서,연후취치최소적절점진행처리.신산법재시간복잡도상개진료기우최소퇴적충자점선취산법.재간단다수역치모형상침대경전적무표도망락득도료소구조적충자집규모상계.실험재수궤생성망락화일사실제망락수거집상진행,결과표명소제방법적유효성,특별재무표도망락상생성적충자집구유비상관산법경소적규모.
