电? 子? 科? 技? 大? 学?

    UNIVERSITY?OF?ELECTRONIC?SCIENCE?AND?TECHNOLOGY?OF?CHINA?

    ·

    ·

    博士学位论文?

    DOCTORAL DISSERTATION

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    ·

    论文题目? 复杂网络数据模式挖掘与演化分析研究?

    学 科 专 业 ? ? 计算机应用技术?

    学? ? ? ? ?号? ? ? ? ? ? ? ? ? 201311060130

    作 者 姓 名 ? ? 吴涛? ?

    指 导 教 师 ? 陈雷霆? ?教授?

    万方数据?

    分类号? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 密级? ? ? ? ? ?

    ·

    UDC注 1

    · ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

    学? ?位? ?论? ?文?

    复杂网络数据模式挖掘与演化分析研究?

    (题名和副题名)?

    ·

    ·

    ·

    吴涛

    (作者姓名)?

    ·

    ·

    ·

    ·

    指导教师? ? ? ? ? 陈雷霆? ? ? ? ? 教? ?授?

    · ? 电子科技大学? ? ? ? 成? ?都?

    (姓名、职称、单位名称)?

    申请学位级别? ? ? 博士? ? ? ? ? ?学科专业? ? ? ?计算机应用技术? ? ? ? ? ?

    提交论文日期? ? 2017.3.20? ?论文答辩日期? ? ? ? 2017.5.26? ? ? ? ?

    学位授予单位和日期? 电子科技大学? 2017 年6 月22 日? ? ? ?

    答辩委员会主席? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

    评阅人? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

    ·

    ·

    ·

    注 1：注明《国际十进分类法 UDC》的类号。?

    ·

    万方数据?

    ·

    PATTERN MINING AND EVOLUTION ANALYSIS

    OF COMPLEX NETWORKED DATA

    A?Doctor?Dissertation?Submitted?to?

    University?of?Electronic?Science?and?Technology?of?China?

    ·

    ·

    ·

    ·

    ·

    ·

    Major:? ? ? ? ? ? ? Computer Applied Technology

    Author:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Wu Tao

    Advisor:? ? ? ? ? ? ? ? ? ? Prof. Chen Leiting

    School?:? ? ? School of Computer Science Engineering ?

    ·

    万方数据?

    独创? 性? 声? 明?

    本人声明所呈交的学位论文是本人在导师指导下进行的研究工作

    及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方

    外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为

    获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与

    我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的

    说明并表示谢意。?

    ·

    签名：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?日期：? ? ? ? ? ?年? ? ? ? ?月? ? ? ? ?日?

    ·

    ·

    论文使用授权?

    本学位论文作者完全了解电子科技大学有关保留、使用学位论文

    的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁

    盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文

    的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或

    扫描等复制手段保存、汇编学位论文。?

    (保密的学位论文在解密后应遵守此规定)?

    签名：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?导师签名：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

    日期：? ? ? ? ?年? ? ? 月? ? ?日?

    万方数据摘要

    I?

    摘?要?

    大数据时代，数据通过“量化一切”形成数据世界。由于数据是世界的客观

    反映，所以数据的分析挖掘工作可以指导人们认识世界、改造世界。随着信息技

    术的发展普及，社会和企业都产生了海量的数据资源，需要被分析利用。同时，网络化是现实世界的普遍特征和内在规律，自然元素、物种人群等各种对象元素

    相互影响、相互依赖形成网络系统。由于数据产生的客观性和普遍性，数据世界

    中的数据资源基本上都是刻画网络化现实世界特征规律的网络化数据。另外，由

    于数据产生的弱约束性以及强覆盖性，收集的数据资源在客观、准确刻画现实世

    界的同时，具有多源多态、复杂异构特征。所以，当前数据处理的主要对象为海

    量的复杂异构网络数据。新型的复杂异构网络数据对传统数据处理技术产生了巨

    大的挑战。为了分析挖掘新型的复杂异构网络数据，本文探索研究基于数据特征

    的、面向现实需求的新型数据处理理论和模型。复杂异构网络数据主要包括网络

    结构数据、网络行为数据以及网络内容数据，本文从不用角度、不同需求、不同

    方法对复杂网络数据进行模式挖掘和演化分析研究，凝练复杂网络数据处理的研

    究范式和计算框架，探索复杂网络数据蕴含的科学问题、问题相关数据的特征规

    律以及问题的求解方案，构建复杂网络数据处理的技术体系。具体研究内容和创

    新点包括：?

    1.基于标记传播的网络结构模式整体检测分析算法?

    针对复杂异构的网络拓扑，以社团结构为主体、同时考虑网络节点的不同角

    色进行多尺度、多层次网络结构模式的挖掘研究，提出一个基于标记传播过程的

    网络结构模式发现算法 LINSIA。LINSIA 通过允许节点同时拥有不同的网络标记

    从而能够识别枢纽节点和重叠社团，通过构建多层次网络结构树并进行最优层次

    分割从而发现网络的多层次、多尺度结构模式，通过标记选择和标记更新策略的

    创新提出与网络异构程度相适应的标记传播过程，从而发现离群节点、避免极大

    社团。实验结果表明 LINSIA算法性能良好，其关于网络结构模式挖掘的综合性解

    决方案对网络结构数据的分析研究工作具有重要的理论意义。?

    2.面向最优网络分裂的节点中心性度量方法?

    本文面向最优网络分裂问题，从微观角度探索网络的结构和功能特征，提出

    基于邻居节点度信息熵和本地结构聚类密度的 ECI 节点中心性。实验结果表明，ECI 中心性在网络分裂过程中性能明显优于传统的 CI 中心性。同时，基于局部结

    构信息的 ECI 中心性取得了媲美全局性方法的分裂效果。本文通过分析 ECI 中心

    万方数据摘要

    II?

    性的性能表现和网络结构特征之间的关联关系，对 ECI 中心性的适用范围进行讨

    论，为最优网络分裂问题中的节点中心性选择提供指导。另外，通过借鉴物质传

    播和热传导物理过程，本文在迭代更新框架中定义非线性混合更新机制，从而提

    出 PIRank节点中心性。该中心性整合物质传播和热传导过程对网络重要节点的不

    同偏好，能够发现具有不同特征的网络重要节点。实验结果表明，PIRank 节点中

    心性对最优网络分裂问题性能表现良好。?

    3.基于节点位置漂移模型的动态网络演化预测算法?

    针对动态演化网络，提出一种结合节点位置漂移模型和链路预测方法的网络

    演化预测算法。此工作首先提出以网络平均最短距离为指导的相似性度量 WSD。

    然后，基于动态演化网络的聚集特性和时效特性定义邻居节点对中心节点的时空

    影响力，并以引力场的视角比较邻居节点的时空影响力强度和本地网络的固有结

    构强度，从而提出更新中心节点网络位置的时空漂移模型。算法基于此漂移模型

    推理动态网络未来的结构状态，并基于未来的网络结构状态预测未来的网络链路。

    实验结果表明，本文提出的相似性度量 WSD与其它经典方法相比性能更优，结合

    位置漂移模型能够准确预测网络演化。?

    4.基于个体转发行为建模的在线社交网络信息传播演化预测方法?

    针对信息传播过程，提出基于微观个体转发行为估计的多尺度信息传播预测

    方法 MScaleDP。MScaleDP 适用于不同规模的信息传播过程、不依赖于任何全局

    信息。MScaleDP将信息传播过程分解为微观个体转发行为集合以及承载转发行为

    的网络拓扑结构。对于微观个体转发行为，MScaleDP从多个维度构建转发特征，并以二分类模型进行建模。 MScaleDP考虑信息级联传播与标记传播方法 LPA的内

    在一致性，以微观个体转发模型替代 LPA的标记更新机制，并通过对 LPA传播过

    程进行限制提出了AULPA级联传播预测算法。 实验结果表明结合个体转发行为估

    计模型和 AULPA级联传播预测算法，MScaleDP 能够全面、准确的预测信息传播，性能优于传统方法。本文还对影响信息传播的主要驱动机制进行了挖掘分析，发

    现时效特征和内容特征是信息传播的主要影响因素。?

    综上，本文围绕复杂网络数据的模式挖掘和演化分析展开了研究，针对四个

    方面的问题提出了解决方案，并进行了大量的实验验证。实验结果表明，本文发

    现的特征规律以及提出的模型算法准确有效、性能优良。本文工作成果不仅具有

    重要的理论意义，也具有广泛的实际应用价值。?

    ·

    关键词：网络数据，链路预测，节点中心性，信息传播，结构模式，演化分析?

    万方数据ABSTRACT?

    III?

    ABSTRACT?

    In?big?data?era,? the?digital?world? is? formed?by?“quantifying?everything”.? In?virtue?

    of?the?data?reflects?the?world?objectively?and?comprehensively,?the?world?can?be?we?can?

    explored? and? exploited? through? data? analysis.?As? network? is? the? substantial? character?

    and? inherent? principle? of? actual? world,? in? which? natural? elements,? species? and? other?

    human? factors? form? networked? systems? through? interacting? and? influencing,? the? data?

    resources? reflecting? the?actual?world?are?basically? the?networked?data.?Actual?world? is?

    complicated? and? miscellaneous,? and? the? process? of? data? collection? is? always?

    unconstrained? and? ubiquitous.? Accordingly,? the? networked? data? is? complex? and?

    heterogeneous.?With? the? development? and? popularization? of? information? technology,?

    enterprises? and? society? have? produced? a? large? amount? of? complex? networked? data,?

    which?need?to?be?analyzed?and?utilized?urgently.?The?characteristic?properties?of?the?new?

    fashioned? complex? networked? data? have? brought? great? challenge? to? traditional? data?

    processing?technology.?In?order?to?analyze?and?mining?the?complex?networked?data,?this?

    project?explores?new?data?processing?models?and?theories?according?to?its?characteristic?

    properties? and? practical? requirements.? Complex? networked? data? mainly? includes?

    network? structure? data,? network? behavior? data? and? network? content? data.? In? order? to?

    utilize? these?data,? the?project?develops?algorithms?and?solutions?for?pattern?recognition?

    and? evolution? analysis? from? various? perspectives,? construct? research? paradigm? and?

    research? framework,? extracting? potential? characteristics? and? underlying? principles? and?

    improving? the? technological? system.? Specifically,? the? main? contributions? and?

    innovations?of?this?dissertation?are?listed?as?follows:?

    1.?Comprehensive?network?structure?pattern?mining?

    To? solve? the? problem? of? structure? pattern? mining,? label? propagation? based?

    integrated?network? structure? investigation? algorithm? (LINSIA)? is?proposed,?which?can?

    identify? community? strucrure,? hub? nodes? and? outliers? of? complex? heterogenous?

    networks.? LINSIA? algorithm? can? recognize? overlapping? communities? and? hubs? by?

    allowing?nodes?possessing?multiple? lables,?can? recognize?hierarchical?communities?by?

    constructing? bottom-up? super-network? structure,? and? can? find? outliers? and? avoiding?

    great? community? structure? by? proposing? novel? lablel? selection? and? label? updating?

    mechanisms.?Moreover,?LINSIA? can? give? out? a? soft-partitioning? community? structure?

    万方数据ABSTRACT?

    IV?

    and? depict? the? degree? of? overlapping? nodes? belonging? to? each? relevant? community.?

    Extensive?experiments?demonstrate? that?LINSIA?algorithm?outperforms?state-of-the-art?

    methods,?and?has?profound?practical?and?theoretical?value.? ?

    2.?Node?centrality?for?optimal?network?targeted?attack.?

    To? solve? the? problem? of? node? centrality? ranking,? proposes? a? centrality? ECI? by?

    considering? loop? density? and? degree? diversity? of? local? network? topology.? And? the?

    proposed?ECI? centrality?would?degenerate? into?CI? centrality?with? the? reduction?of? the?

    loop? density? and? the? degree? diversity? level.?By? comparing?ECI?with?CI? and? classical?

    centrality?measures?in?both?synthetic?and?real?networks,?the?experimental?results?suggest?

    that?ECI?can? largely? improve? the?performance?of?CI? for?network?disruption.?Based?on?

    the? results,?we?analyze? the?correlation?between? the? improvement?and? the?properties?of?

    the? networks.? We? find? that? the? performance? of? ECI? is? positively? correlated? with?

    assortative?coefficient?and?community?modularity?and?negatively?correlated?with?degree?

    inequality? of? networks,? which? can? be? used? as? guidance? for? practical? applications.?

    Moreover,? we? propose? a? power? iteration? ranking? (PIRank)? algorithm? by? integrating?

    mass?diffusion?and?heat?conduction? into?eigenvector?centrality.?Because? these?physical?

    processes? treat? influential? nodes? differently,? combining? them? increases? our? ability? to?

    identify?different?types?of?influential?nodes.?To?test?our?PIRank?algorithm,?we?apply?it?to?

    the?selection?of?attack?targets?in?the?network?disruption?problem?and?to?the?identification?

    of? influential? spreaders? in? the? influence? maximization? problem.? From? extensive?

    experimental? results? on? real-world? networks?we? find? that? the? strength? of? the? network?

    disruption?of?a?PIRank-guided?targeted?attack?can?be?increased.?

    3.?Network?evolution?prediction?based?on?link?prediction?and?position?drift? ?

    In?order? to?solve? the?problem?of?network?evolution?prediction,? this?project?adopts?

    linkprediction? paradigm.? To? estimate? the? likelihood? of? the? existence? of? links? more?

    accurate,? an? effective? and? robust? similarity? index? is? presented? by? exploiting? network?

    structure? adaptively.?Moreover,? most? of? the? existing? link? prediction? methods? do? not?

    make?a?clear?distinction?between?future? links?and?missing? links.?In?order? to?predict? the?

    future? links,? the? networks? are? regarded? as? dynamic? systems? in? this? project,? and? a?

    similarity? updating? method,? spatial–temporal? position? drift? model,? is? developed? to?

    simulate?the?evolutionary?dynamics?of?node?similarity.?Then?the?updated?similarities?are?

    used? as? input? information? for? the? future? links’? likelihood? estimation.? Extensive?

    experiments?on?real-world?networks?suggest?that?the?proposed?similarity?index?performs?

    万方数据ABSTRACT?

    V?

    better? than?baseline?methods? and? the?position?drift?model?performs?well? for? evolution?

    prediction?in?real-world?evolving?networks.?

    4.?Information?diffusion?prediction?based?on?individual?spreading?estimation.?

    To?address?the?problem?that?information?diffusion?prediction,?this?project?develops?

    a? novel? prediction? method,? multiscale? diffusion? prediction? (MScaleDP).? MScaleDP?

    aggregates?microscopic? spreading?modules? of? individual? nodes? using? a? unidirectional?

    label? propagation? algorithm? for?macroscopic? diffusion? prediction,? in? which? the? label?

    selection? mechanism? corresponds? to? the? microscopic? spreading? decision-making.?

    Through?microscopic? spreading? behavior?modeling,? the? underlying? influential? factors?

    and?the?principal?driving?mechanisms?of?diffusion?process?are?identified.?Moreover,?we?

    find? that? the?accuracy?of? spreading?behavior?estimation?does?not?always? increase?with?

    the?growth?of?the?feature?number.?We?also?find?that?the?accuracy?of?spreading?behavior?

    estimation?is?not?strongly?correlated?with?the?estimation?model?when?sufficient?features?

    are?considered.?The?proposed?method?is?successfully?tested?on?microblogging?network,?

    and?represents?a?valuable?tool?for?gaining?insights?on?information?diffusion?process..?

    In?summary,?this?dissertation?takes?efforts?on?pattern?mining?and?evolution?analysis?

    of? complex? networked? data.? A? series? of? experiments? show? that? the? identified?

    characteristics? and? the? proposed? solutions? in? this? project? are? accuracy,? effective? and?

    effiecient.? Therefore? they? not? only? have? important? theoretical? value,? but? also? have?

    extensive?application?potential.?

    ·

    Keywords: Networked?data,?Link?prediction,?Node?centrality,?Information?diffusion,? ?

    Structural?pattern,?Evolution?analysis.?

    ·

    万方数据目录

    VI?

    目?录?

    第一章 绪论? .....................................................................................................................1

    1.1? 论文的研究背景? ...............................................................................................?2

    1.2? 论文的研究目标与意义? ...................................................................................?3

    1.3? 网络数据分析挖掘的研究进展? .......................................................................?5

    1.3.1? 社团结构检测? ........................................................................................?5

    1.3.2? 网络节点中心性度量? ............................................................................?7

    1.3.3? 链路预测与网络演化? ............................................................................?9

    1.3.4? 信息传播演化分析与建模? ...................................................................? 11

    1.4? 面临的问题和挑战? .........................................................................................?12

    1.5? 论文主要内容与章节安排? .............................................................................?14?

    1.5.1? 主要研究内容与创新点? ......................................................................?14

    1.5.2? 论文章节安排? ......................................................................................?15

    第二章 网络结构检测分析研究? ...................................................................................17

    2.1? 基本标记传播算法? .........................................................................................?17

    2.2? 基于标记传播的网络结构检测算法? .............................................................?18

    2.2.1? 标记传播与节点角色? ..........................................................................?18

    2.2.2?LINSIA社团检测算法? .........................................................................?20

    2.2.3?LINSIA算法时间复杂度? .....................................................................?23

    2.3? 实验与结果分析? .............................................................................................?25

    2.3.1? 实验设计? ..............................................................................................?25?

    2.3.2? 初始标记影响力与自适应调控因子的影响? ......................................?26

    2.3.3? 基于人工网络的算法性能评估? ..........................................................?26

    2.3.4? 基于真实网络的算法性能评估? ..........................................................?27

    2.3.5? 算法运行时间比较? ..............................................................................?33

    2.4? 本章小结? .........................................................................................................?34

    第三章 面向最优网络分裂的节点中心性度量研究? ...................................................35

    3.1? 网络最优分裂问题定义? .................................................................................?35

    3.2? 基于群体影响力的节点中心性研究? .............................................................?36

    3.2.1?CI中心性分析? ......................................................................................?36

    3.2.2?ECI中心性度量? ....................................................................................?36

    万方数据目录

    VII?

    3.2.3?ECI中心性时间复杂度? ........................................................................?39

    3.2.4? 实验与结果分析? ..................................................................................?39

    3.3 基于幂迭代的节点中心性度量研究? ..............................................................?46

    3.3.1 物质传播与热传导过程? .......................................................................?47

    3.3.2 物质传播与热传导过程特性分析? .......................................................?49

    3.3.3 混合更新机制? .......................................................................................?51

    3.3.4?PIRank中心性度量? ..............................................................................?52

    3.3.5? 实验与结果分析? ..................................................................................?53

    3.4? 本章小结? .........................................................................................................?59

    第四章 基于链路预测的动态网络演化预测研究? .......................................................60

    4.1 问题定义? ..........................................................................................................?60

    4.2 演化预测模型? ..................................................................................................?61

    4.2.1? 结构依赖的相似性度量? ......................................................................?61

    4.2.2? 节点位置时空漂移模型? ......................................................................?62

    4.3 实验与结果分析? ..............................................................................................?65

    4.3.1? 实验数据? ..............................................................................................?65

    4.3.2? 相似性度量 WSD的有效性?...............................................................?66

    4.3.3? 相似性度量 WSD的鲁棒性?...............................................................?68

    4.3.4? 时空位置漂移模型的有效性? ..............................................................?70

    4.4 本章小结? ..........................................................................................................?72

    第五章 在线社交网络信息传播过程演化预测研究? ...................................................73

    5.1? 问题定义? .........................................................................................................?73

    5.2? 演化预测模型? .................................................................................................?74

    5.2.1? 本地影响力量化? ..................................................................................?75

    5.2.2? 微观转发行为建模? ..............................................................................?76

    5.2.3? 基于标记传播的全局传播预测? ..........................................................?77

    5.3? 实验与结果分析? .............................................................................................?80

    5.3.1? 实验设计? ..............................................................................................?80

    5.3.2? 转发估计模型选择与特征分析? ..........................................................?81

    5.3.3? 微观转发行为估计与驱动机制分析? ..................................................?82

    5.3.4? 宏观信息传播预测? ..............................................................................?86

    5.4? 本章小结? .........................................................................................................?87

    第六章 总结与展望? .......................................................................................................88

    万方数据目录

    VIII?

    6.1? 本文研究工作总结? .........................................................................................?88

    6.2? 下一步研究思路? .............................................................................................?90

    致谢? .................................................................................................................................92

    参考文献? .........................................................................................................................93

    攻读博士学位期间取得的成果? ...................................................................................104

    万方数据图目录

    IX?

    图目录?

    图 1-1?网络数据分析计算框架? ..............................................................................?4?

    图 1-2?论文组织架构图? ........................................................................................?15?

    图 2-1?紧密相连瓦网络结构的标记传播过程? ....................................................?18?

    图 2-2?包含多个紧密相连结构的网络的节点标记迭代更新过程? ....................?18?

    图 2-3?标记迭代更新过程说明示例? ....................................................................?20?

    图 2-4?极大极小社团划分说明示例? ....................................................................?21?

    图 2-5?社团检测与多层次网络构建? ....................................................................?24?

    图 2-6?网络结构划分与节点检测? ........................................................................?24?

    图 2-7?参数取值对 LINSIA算法性能的影响? .....................................................?27?

    图 2-8?基于 LINSIA算法的美国高校足球比赛网络结果分析? .........................?29?

    图 2-9?基于 LINSIA算法的美国政治博客网络结构分析? .................................?32?

    图 2-10? 基于 LINSIA 算法的海豚种群网络结构分析? .......................................?32?

    图 2-11?基于 LINSIA 算法的EAGLE示意网络结构分析? ................................?32?

    图 2-12? 算法运行时间综合比较? ..........................................................................?33?

    图 3-1?CI中心性和 ECI中心性说明?...................................................................?37?

    图 3-2?ER 和 SF网络中基于 ECI的网络分裂的性能表现? ................................?42?

    图 3-3?LFR 社团网络中基于ECI的网络分裂的性能表现? ................................?43?

    图 3-4?真实网络中基于 ECI的网络分裂的性能表现?.......................................?44?

    图 3-5?ECI优化程度与网络结构主要特征的关联关系?.....................................?46?

    图 3-6?标准物质传播与热传导过程选择重要节点的偏好性? ............................?48?

    图 3-7?基于Karate网络的标准物质传播和热传导过程特性测试? ...................?50?

    图 3-8?基于Email 网络的参数取值对性能的影响分析?....................................?51?

    图 3-9?基于Email 网络的混合更新机制的混合参数取值合理性分析?............?55?

    图 3-10? 基于最大连通子图的PIRank与 Eigen中心性性能比较.....................?56?

    图 3-11? 基于连通子图数目的PIRank与 Eigen中心性性能比较? .....................?56?

    图 3-12? 混合参数取值与 PIRank效果的关联分析? ............................................?57?

    图 3-13? 基于最大连通子图的PIRank中心性性能评价? ....................................?58?

    图 3-14? 基于连通子图数目的PIRank中心性性能评价? ....................................?58?

    图 4-1?网络节点本地空间交互示例? ....................................................................?63?

    万方数据图目录

    X?

    图 4-2?网络节点关联链路的时序解析? ................................................................?65?

    图 4-3?邻居节点时空影响力与本地网络结构强度比较? ....................................?65?

    图 4-4?真实实验网络中不同比例训练集条件下相似性度量性能比较? ............?68?

    图 4-5?真实实验网络中不同网络平均距离条件下相似性度量性能比较? ........?69?

    图 4-6?节点位置漂移不同迭代次数对链路预测结果的影响? ............................?70?

    图 4-7?基于位置漂移模型的动态网络演化预测(Precision)? .........................?71?

    图 5-1?多尺度信息传播预测方法MScaleDP......................................................?74?

    图 5-2?同步信息级联过程说明示例? ....................................................................?78?

    图 5-3?异步信息级联过程说明示例? ....................................................................?79?

    图 5-4?候选特征对微观个体转发行为估计的有效性分析? ................................?82?

    图 5-5?消息转发候选特征之间的相关性分析? ....................................................?83?

    图 5-6?不同比例已知传播数据条件下节点状态预测? ........................................?85?

    图 5-7?不同比例已知传播数据条件下传播规模预测? ........................................?85?

    图 5-8?基于激活节点序列准确性的信息传播过程预测? ....................................?85?

    ·

    万方数据表目录

    XI?

    表目录?

    表 2-1? 人工实验网络生成模型参数取值? ............................................................?28?

    表 2-2? 人工实验网络社团检测结果? ....................................................................?28?

    表 2-3?真实实验网络结构特征? ............................................................................?29?

    表 2-4?真实实验网络中互斥社团的检测结果? ....................................................?30?

    表 2-5?真实实验网络中层次社团的检测结果? ....................................................?30?

    表 2-6?真实实验网络中重叠社团检测结果? ........................................................?30?

    表 2-7?真实实验网络中层次重叠社团检测结果? ................................................?30?

    表 3-1?实验网络的结构特征? ................................................................................?41?

    表 3-2?人工实验网络中 ECI对网络分裂的优化程度?.......................................?45?

    表 3-3?真实实验网络中 ECI对网络分裂的优化程度?.......................................?46?

    表 3-4?ECI优化程度与网络结构特征的相关性?.................................................?46?

    表 3-5?实验网络的结构特征? ................................................................................?54?

    表 4-1? 实验网络的结构特征? ................................................................................?67?

    表 4-2?基于AUC评价指标的链路预测相似性度量性能比较?.........................?67?

    表 4-3?基于Precision 评价指标的链路预测相似性度量性能比较? ...................?67?

    表 4-4?基于位置漂移模型的动态网络演化预测(AUC)?...............................?70?

    表 5-1?微观个体状态行为本地影响因素? ............................................................?76?

    表 5-2?候选模型性能评价? ....................................................................................?81?

    表 5-3?微观转发行为性能评价? ............................................................................?83?

    表 5-4?基于特征权重的信息传播驱动机制分析? ................................................?84?

    表 5-5?基于特征权重的信息传播驱动机制分析(不考虑消息生存时间)? ....?84?

    ·

    ·

    万方数据第一章 绪论

    1?

    第一章?绪论?

    随着信息技术的迅猛发展，网络数据(Networked? Data，ND)在社会经济生

    活的各个领域呈现出爆发式的增长。网络数据是指蕴含关联关系的、具有网络化

    组织结构的数据，也是数据资源的一种主要存在形式。网络数据将网络化的现实

    世界、人类社会映射到数据空间，从而通过对数据空间中数据资源的分析研究可

    以指导、促进现实世界的发展进步。当前，海量的网络数据要求人们开展相关的

    科学技术研究，认识和利用数据资源。网络数据的研究在社会安全、商业智能、智慧城市、科学研究等诸多领域都具有广阔的应用前景。复杂网络数据的研究与

    应用涉及多个学科的高度交叉，近年来引起了国内外工业界和学术界的极大关注，已经成为多个领域的前沿研究热点。?

    网络数据的分析利用虽然得到了多个领域的重视，但是已有工作往往是基于

    各自学科、各自领域展开的。例如，基于医学视角研究传染病网络数据，基于生

    物学视角研究蛋白质交互网络数据，基于社会学视角研究社会关系网络数据。为

    了高质量、高效率的分析数据，网络数据的挖掘利用需要共性的数据处理理论和

    工具的支持。研究科学有效的网络数据处理理论和分析挖掘算法对于网络数据的

    广泛利用、对于社会经济各个领域的快速发展具有重大价值和深远意义。?

    网络数据具有海量、稀疏和复杂性特征，其复杂性体现在网络结构的复杂性、网络存在动态演化性、节点和链路类型的多样性、动力学过程的复杂性以及以上

    各种复杂性的相互影响。传统的数据分析技术已经日益无法满足复杂网络数据的

    处理需求。近年来兴起的网络科学让人们有机会从新的视角认识和理解复杂网络

    数据。虽然网络科学与数据科学各有侧重，但它们具有从复杂数据资源中提取有

    意义的信息并最终形成一个紧凑的量化表示[1]

    的共同目标。因此，本文提出结合网

    络科学与数据科学的理论方法进行复杂网络数据模式挖掘与演化分析的研究。?

    本文作者在攻读博士学位期间参加了教育部广东省产学研合作项目《健康大

    数 据 智 能 分 析与 服务 平 台 关 键 技术 研究 及 应 用 示 范》(项 目 编 号：

    2015B010131002) ，此项目的研究重点和研究目标在于复杂异构数据分析挖掘的关

    键技术，通过分析挖掘复杂异构数据，为上层智能应用提供理论支持和原型算法。

    本文的工作主要围绕复杂异构数据中的复杂网络数据展开，论文选题立足于上述

    项目的需求，从网络科学和数据科学的角度对复杂网络数据的组织结构、节点重

    要性、结构演化、信息传播等关键基础问题进行研究，提出新颖的模型算法，解

    决相关难点和挑战。?

    万方数据电子科技大学博士学位论文

    2?

    1.1?论文的研究背景?

    近年来，随着互联网、物联网、云计算等信息技术的迅速发展，快速增长的数

    据成为了许多行业共同面对的挑战和机遇，使得“大数据”成为时代关注的焦点，数据成为了继自然资源、人力资源之后的新型资源。数据资源作为国家、企业的

    核心战略资产和财富，开发利用数据资源可以推动经济发展、增强竞争力、优化

    治理效率。因此，数据空间已逐渐成为国家和企业竞争的一个重要领域，数据技

    术与数据产业会像工业革命一样撑起一个时代[2]。?

    数据不仅可以描述物理世界，还可以刻画人类社会。当前，与数据的经济价值

    相比，数据的科学价值似乎还没有引起人们足够的重视[2]。在数据世界演化成熟并

    被深入认识之前，实践和技术的发展正在倒逼数据科学理论的发展。数据科学将

    遵循从海量数据现象中发现科学规律，构建数据计算理论和计算模型，进而反过

    来指导数据资源开发利用的发展规律。具体的，当前数据分析技术还不成熟，数

    据科学的发展还处于认识数据、利用数据的初级阶段。面对海量异构、复杂演化

    的数据，传统的数据分析方法对数据规范性要求较高、分析效率较低、成本和能

    耗较大，从而只能让我们利用很少一部分数据，剩余大部分数据都没有产生价值。

    如果数据是矿山的话，我们现在缺少“有效开采矿产的技术装备” 。因此，面对数

    据资源开发利用的巨大社会需求，我们要问“数据处理的理论模型在哪里？数据

    处理的技术方法在哪里？” 。所以，数据科学需要充分的理论模型和技术方法研究

    以应对数据资源开发利用的挑战。?

    在大数据时代，传统数据分析技术遇到挑战，数据分析领域的主要工作，包

    括语义分析、知识发现、信息检索等，都变得十分困难。除了数据类型、数据结

    构的多样性外，其背后的一个重要原因是数据对象不是独立的，数据中蕴含复杂

    的关联关系、呈现网络化组织模式。另外，当今世界包括电力网络、交通网络、在线社交网络等网路系统随处可见，这些网络系统直接产生大量网络化数据。从

    而，网络数据无处不在，网络数据是大数据的一个普遍存在形式。因此，要有效

    求解大数据时代的数据分析问题，一个重要方面就是要对普遍存在的复杂网络数

    据进行深入认识和挖掘。?

    由于数据的共性、数据的整体特征往往隐含在数据背后的网络中，开发利用

    数据资源就是要分析处理网络数据。然而，当前的数据处理技术从数据中提取到

    的一般是频繁模式或数据模型，人们无法基于这些模式和模型认知网络数据背后

    的复杂机理，即当前数据分析技术仅能发现数据表层的统计规律，对于数据内在

    规律的发现和认知仍然缺乏行之有效的手段。所以，人们需要基于网络数据的特

    征、以新的视角寻求认知利用复杂网络数据的新型模型方法。?

    万方数据第一章 绪论

    3?

    1.2?论文的研究目标与意义?

    近年来， 网络科学的快速兴起和迅速发展为复杂网络数据的分析研究提供了新

    的思路。因为要理解复杂网络数据就要对背后的网络进行分析挖掘。所以，本文

    提出基于网络科学理论对复杂网络数据进行探索研究。同时，国务院于 2015 年 8

    月颁发的《促进大数据发展行动纲要》[3]

    中明确指出： “融合数理科学、计算机科

    学、社会科学及其他应用学科，以研究相关性和复杂网络为主，探讨建立数据科

    学的学科体系” 。Barabási教授也认为[2]

    ·“数据科学需要网络科学来理解信息之间

    的相互关联，因此网络科学成为数据科学的关键方法论引擎之一” 。?

    从数据科学的角度分析，网络数据是多种数据资源中的一种重要类型。由于

    网络数据的内在关联、交互影响的特性，传统数据处理技术无法满足它的分析处

    理需求，故需要提出新的理论模型和技术方法。然而，网络科学的研究方法主要

    是基于高度抽象的复杂网络对实际系统进行理论模拟和分析，从而无法直接采用

    网络科学的技术方法进行网络数据的分析挖掘。所以，为了进行网络数据的分析

    处理，需要对传统数据处理技术和网络科学理论进行融合，发展适用于网络数据

    处理的计算理论和计算框架。由于网络数据来源的复杂性、应用目标的多样性，网络数据分析处理的计算框架需要考虑数据来源、数据质量、应用目标等问题，明确计算任务的性质、任务的目标以及应用领域等情况，从而提高网络数据的挖

    掘效率，促进相关问题的抽象定义以及关键技术的优化发展。?

    本文提出的网络数据分析处理的总体计算框架如图 1-1所示， 主要包括数据收

    集整合、数据预处理、数据总体特征感知、数据分析挖掘、数据计算学习以及数

    据实际应用六个层次。其中，数据收集整合的目标是尽可能完整、准确的将不同

    规模的、不同类型的、不同结构的目标系统通过采样、转换等方式表征为复杂网

    络数据；数据预处理的目标是对于获得的网络数据进行清洗，按照网络模型进行

    抽取、转换，分割为标准的网络结构、网络行为、网络内容属性数据集；数据总

    体特征感知是对获得的网络数据进行概括的分析认知，包括统计特性、网络骨干

    结构[4,5]

    、网络结构概述[6]

    等，支撑网络数据的分析挖掘和计算学习；数据的分析

    挖掘是对于目标网络进行多角度分析以发现网络的结构模式、网络的演化规律、网络行为模式等，同时探索研究网络数据可能蕴含哪些科学问题、这些问题能否

    求解以及如何求解；网络数据的计算学习研究数据处理过程中的共性计算基础，包括压缩、划分、距离、检索以及大规模高效计算等问题，其主要目标是提高网

    络数据分析挖掘算法的速度和效率；网络数据处理的实际应用部分研究如何将基

    础模型算法与现实应用场景相结合，如何基于网络数据分析处理的技术解决现实

    应用问题。?

    万方数据电子科技大学博士学位论文

    4?

    ·

    图 1-1 网络数据分析计算框架?

    面对广泛存在的网络数据， 本文的研究目标是基于网络科学理论和传统数据处

    理技术研究网络数据的内在规律，提出进行网络数据模式挖掘和演化分析的模型

    算法。具体的，在网络结构模式挖掘方面，网络结构在宏观上具有连接密度、平

    均聚类系数、平均最短路径、幂律度分布、小世界特性等的统计特性；在中观上，网络结构可以被看做多个社团结构的耦合，其中社团结构往往与网络功能紧密相

    关；在微观上，网络元素在节点度、链路权重、重要性等方面存在明显的异质性。

    基于真实网络数据的实证分析发现，社团往往是由功能相近或者性质相似的个体

    构成，社团结构能够反映单个节点对象在自发、无序关联行为背后的局部弱规则

    性和全局有序性[7]

    ，对网络研究具有重要意义。因此，研究者提出了社团检测问题

    [7-8]。由于通常无法获得完整的网络结构数据，研究者探索基于已知的网络结构信

    息预测网络链路的可能性，从而提出了链路预测问题[9]。由于复杂网络的异构性，网络中各个节点以及各个链路之间在重要性上存在巨大差异。为了识别重要的网

    络节点和链路，研究者提出了网络节点排序[10-11]

    和网络链路分类问题[4]。在动态网

    络演化分析方面，大多数现实网络的结构和行为往往都具有动态性，其随着时间

    的增长而变化。当前对网络的分析研究或者基于某一时刻的镜像数据进行分析，万方数据第一章 绪论

    5?

    或者将多个观察数据叠加集成进行分析。这都忽视了数据中的时序信息以及不同

    时间点网络的变化情况，从而无法有效发现、理解动态网络数据的模式机理。为

    了建模动态演化网络，人们提出“采用链路预测方法、通过分析链路预测的准确

    性从而对各种可能的网络演化机制进行显著性判别”的研究思路，进而发现网络

    演化的驱动机制、进行演化建模[12]。另外，为了理解广泛存在的信息传播现象，研究者提出了信息传播的建模预测问题[13-14]。通过分析影响信息传播的潜在因素

    以及信息传播规律，预测信息传播过程将来的传播范围、传播规模以及参与个体。 ?

    由于网络数据的复杂性和普遍性，本文针对网络数据的研究具有重要的科学

    理论意义及工程应用价值。具体的，社团结构是许多现实网络所普遍具有的一种

    结构特征，社团结构检测具有广阔的应用前景和重要的应用价值[15-18]。在社交网

    络中，社团检测可以帮助识别具有相似背景和价值观的人群，可以让研究者快速

    了解人群的组织结构。在科学家合作网络中，社团检测可以快速了解研究人员之

    间的合作关系和主要科研团体。在语义网络中，社团检测可以进行主题发现。另

    外，社团结构还与传播等动力学过程紧密相关[19-20]。研究网络节点重要性问题，可以发现意见领袖、犯罪团伙头目、关键功能节点，可以优化网络鲁棒性、进行

    最优网络分裂、优化商业营销策略[10,21]。链路预测可以用来预测恐怖组织中恐怖

    分子之间隐含的互动关系，可以用于社交网络、电子商务中的个性化推荐，可以

    在生物研究中通过估计蛋白质之间的交互关系指导科学实验。另外，研究链路预

    测问题还有助于对非完备或含噪声网络进行恢复重构[22]。信息传播的建模预测可

    以更有效、更准确的进行网络态势建模、谣言管控、用户体验优化，还可以对网

    络行为进行引导规约，维护良好网络环境。?

    1.3?网络数据分析挖掘的研究进展?

    为了更好的理解复杂网络数据模式挖掘与演化分析的研究价值和研究意义，本节介绍复杂网络数据分析处理相关问题的发展历程、研究现状以及各个问题的

    基本研究思路和主要方法。?

    1.3.1?社团结构检测?

    关于社团检测问题，M.?Girvan和 M.?E.?J.?Newman认为聚合式层次聚类方法导

    致网络中的边缘节点被独立的划分为社团，从而无法获得满意的网络社团结构。

    为了克服以上缺点，他们在 2002 年提出基于分裂式层次聚类的社团检测方法[15]。

    这种方法将整个网络视为一个初始社团，然后以介数中心性对链路进行重要性排

    序并连续删除重要链路。在每次删除链路之后，剩余链路的介数中心性需要进行

    万方数据电子科技大学博士学位论文

    6?

    重新计算。迭代执行链路删除操作，直到没有剩余链路为止。从而，根据链路删

    除过程中产生的网络结构层次树进行社团划分。基于相同框架，F.? Radicchi? 等人

    提出以聚类系数来取代介数中心性进行链路重要性排序和删除的社团检测方法[8]。 ?

    M.?E.?J.?Newman和 M.?Girvan认为[23]

    ，无论是聚合式方法，还是分裂式方法，它们迭代添加链路或者删除链路的过程最终会生成一个网络结构层次树。为了进

    行社团划分，必须在构建的结构层次树上选择一层进行切割，而进行层次树切割

    的位置直接与最终社团的质量相关。该问题的本质在于缺乏一种度量社团质量的

    手段。为解决此问题，他们在 2004 年提出了“社团模块度(Modularity)”概念[23]。

    对于某一个网络的不同社团划分，模块度越高，该划分越能体现网络的社团结构。

    从而，模块度可以作为不同社团检测算法性能比较评价的一个度量指标，极大地

    促进社团检测问题的发展。另外，模块度概念的提出使得网络社团检测问题可以

    被建模为一个以模块度最大化为目标的优化问题，其从网络的所有可能的社团划

    分中寻找一个模块度最大的划分。另外，基于模块度最优化的社团检测思路，许

    多结合贪婪策略、模拟退火、极值优化等算法的社团检测方法被提出[24-27]。?

    基于以上先驱性工作，后续越来越多的、基于包括标记传播、随机行走、统计

    推理等各种技术的社团检测算法被提出。具体的，文献[28-30]提出基于标记传播

    的社团检测算法 LPA(Label? propagation? algorithm)，其中每个节点可以基于周围

    邻居节点的社团标记进行标记更新。随着标记的更新传播，紧密相连的节点群落

    很快会形成一致的社团标记。在网络节点标记不再发生变化时，网络中具有相同

    社团标记的节点即被划分为一个社团。LPA 算法具有近似线性的时间复杂度，适

    用于大规模网络。文献[31]提出基于随机行走的社团检测算法 Infomap。Infomap

    算法基于信息论和压缩编码理论对随机行走过程在各个网络节点上的到达频率进

    行编码。为了发现网络中的社团，Infomap算法提出对编码过程进行二级划分，社

    团对象也可以被唯一编码，并且允许不同社团的内部节点采用相同编码。从而，通过求解网络的二级最小描述长度问题，获得网络的社团结构。文献[32]提出基于

    随机行走的社团检测算法 Walktrap。Walktrap 算法在网络上执行随机行走，然后计

    算节点之间在t步范围内能够相互到达的概率，以此概率为基础定义节点距离以及

    社团距离。基于以上距离，采用聚合式层次聚类框架进行社团检测。另外，文献

    [33-34]中，M.?E.?J.?Newman提出了基于模块度矩阵特征向量划分的社团检测算法

    LE和基于概率混合模型和期望最大化算法的社团检测方法。?

    除互斥社团检测问题外，还存在重叠、层次社团检测问题。文献[35]首先指出

    了现实网络中存在社团重叠现象，并提出了一种基于完全子图渗流(Clique?

    Percolation,? CP)的重叠社团发现方法。基于此方法，文献[36]提供了一个用于重

    万方数据第一章 绪论

    7?

    叠社团检测的开源计算工具 CFinder。另外，基于标记传播方法，文献[37]提出了

    进行重叠社团检测的 SLPA算法。在 SLPA算法中，每个节点都会保存其历史标记

    序列，SLPA 随机选择一个节点作为 listener，此 listener 的每个邻居节点 speaker

    根据各自的标记序列按比例选择一个标记并将此标记发送给 listener，listener 将返

    回的标记中数量最多的标记添加到自己的标记序列中。以上过程迭代执行指定次

    数后，对每一个节点的标记序列进行统计，按一定门限值删除低概率标记，剩下

    的标记即为该节点的社团标记(通常有多个)。文献[38]提出了进行社团检测的

    Louvain 算法。Louvain 算法迭代性的将网络节点与模块度增益最大的邻居节点进

    行融合， 直到网络中任何节点的移动都不能再改善总的模块度为止。 然后， Louvain

    算法将得到的社团视为新的节点重新构造网络，并再次执行迭代融合操作。如此

    循环，Louvain算法可以发现网络不同层次的社团结构。?

    另外，按照聚合式层次聚类思路，沈华伟等人[39]

    提出了基于最大完全子图的层

    次重叠社团检测算法 EAGLE。 基于统计推理方法， Brian?Karrer和 M.?E.?J.?Newman

    提出了随机块社团检测算法(Stochastic?block?models,?SBM)[40]

    ，I.?Psorakis 等人提

    出了基于非负矩阵分解(Nonnegative?Matrix?Factorization,?NMF)的社团检测算法

    [41]。基于标记传播，S.?Gregory提出了重叠社团检测算法 COPRA[42]。另外，Yong-?

    Yeol?Ahn等人[43]

    观察到在重叠社团中，节点常常属于多个社团，但链路一般都只

    属于一个社团，从而提出社团可以定义为一组紧密相连的链路而不是节点，进而

    基于链路之间的相似度构建结构层次树进行重叠社团检测。?

    总体而言，社团检测问题的研究在最初的问题定义阶段以研究可行性为主，并基于无标注网络数据进行实验分析，提出了模块度概念进行社团检测算法的比

    较评价。随着研究的不断深入，人们发现模块度指标存在一些不足，从而针对模

    块度提出了许多改进优化工作，追求方法的完善性。另一方面，更多的有标注网

    络数据和人工网络数据被用来进行社团检测算法的比较评价。进而，基于各种理

    论方法追求更高准确率的、面向不同结构的社团检测算法被提出。近期，许多工

    作开始关注社团检测是否具有现实意义以及如何设计普适的、可精确计算的社团

    检测算法等相关问题[44-45]。?

    1.3.2?节点中心性度量?

    网络节点中心性问题是网络结构分析中的几个关键问题之一， 对理解和调控网

    络功能具有重要意义。虽然网络节点中心性的概念提出比较早，包括度中心性、介数中心性等，但是在网络科学发展初期没有得到足够的重视。在重要网络节点

    对网络功能的影响方面，最初 David?Kempe? 和 Jon?Kleinberg?等人[46]

    在 2003 年研

    万方数据电子科技大学博士学位论文

    8?

    究了社会网络中的影响力最大化问题，思考在社会网络中如何选择节点作为产品

    或者发明的传播源，通过尽可能引发大规模级联传播的方式实现市场营销影响力

    最大化。文献[47]基于独立级联模型(Independent? cascade，IC)和线性门限值模型

    (Linear?threshold， LT) 对以上工作中基于贪婪策略的影响力最大化问题进行研究，提出了基于渗流理论的求解方法，极大地优化了影响力最大化问题的求解效率。

    另外，A.?L.?Barabasi等人[48]

    在 2000年研究了网络对错误和攻击的鲁棒性问题。许

    多复杂网络系统对错误展示出了很高的鲁棒性，他们发现能够容忍错误的网络往

    往是万维网、社会网络等无标度网络。但是，这些网络对于网络攻击行为是极度

    敏感的。所以，研究网络攻击过程中的目标节点选择问题对网络鲁棒性优化、网

    络攻击具有重要意义。在 2002 年，文献[49]发现网络的异质性极大地促进了疾病

    在网络中的传播，使得疾病很难被根除。在不同模型网络上采用不同免疫方法的

    实验结果显示，在全局水平进行随机均匀免疫的效果无法令人满意，只有进行目

    标免疫才能够达到控制疾病爆发的目的。实验还表明选择一小部分节点进行免疫

    就可以控制疾病的全局化大范围传播。文献[50]研究传染性疾病传播控制问题，考

    虑应该如何选择网络节点进行免疫从而最优的控制疾病在网络上的传播。实验表

    明基于局部网络结构就足以发现网络中需要进行免疫的重要节点。?

    基于以上先驱性工作，后续基于不同视角、面向不同功能、采用不同技术的多

    种网络重要节点发现算法被提出。具体的，基于“节点邻居越多影响力越大”的

    思想提出了仅仅基于本地结构特征的中心性度量，例如只考虑邻居节点个数的度

    中心性(Degree? centrality)和考虑一跳邻居节点和两跳邻居节点的本地中心性

    (Local?centrality)[51]；基于“节点影响力与节点在网络中的位置紧密相关”的思

    想提出了接近中心性 (Closeness?centrality) [52]

    ， 介数中心性 (Betweenness?centrality)

    [53]

    ，k-shell 中心性(k-shell?based?centralities)

    [54,55]

    等；基于网络的谱特征，提出了特

    征向量中心性(Eigenvector?centrality)[56]

    、LeaderRank中心性[57]

    、PageRank 中心

    性[58]

    等方法。 k-shell 中心性依次删除网络中度为i的节点和与其相连的边。 随着i的

    增大，网络中的节点和边被一层一层的剥去，k-shell 方法认为越靠内层的节点其

    重要性越高。k-shell 方法的优点是计算速度快，适用于大规模网络，缺点是对节

    点的重要性刻画不够精细。文献[59]认为节点度、k-shell 和特征向量中心性虽然能

    够鉴别网络中的重要节点，但是无法准确估计网络中大部分非重要节点的传播能

    力，从而提出了预期强度(Expected?force，EF)方法。另外，文献[60]发现传统的

    中心性度量方法都过度的强调基于传播源所能够形成的传播路径的数量，但是没

    有关注这些传播路径的多样性，从而提出基于信息熵对本地拓扑结构的多样性进

    行度量，并结合节点度构建新的节点中心性度量方法。文献[61]认为节点的全局传

    万方数据第一章 绪论

    9?

    播影响力不仅仅与节点自身的中心性相关，而且与其邻居节点的中心性相关，从

    而提出了基于迭代资源分配的方法，通过多次迭代之后的均衡状态进行节点影响

    力度量。?

    总体而言，Degree 中心性等局部性方法高效但精度较低，Closeness 中心性、Betweenness 中心性等全局性方法有效但复杂度较高， 类 k-shell 中心性方法对节点

    重要性的区分度不够。已有的节点中心性度量方法基本上都是面向不同应用的，当前还没有一种普适的、确定性的度量方法。同时，已有的度量对于同一网络产

    生的重要节点集合也往往存在不一致性。基于真实网络数据的分析研究表明，节

    点的重要性与具体的网络功能密切相关[62]。所以，面对不同应用、不同结构特性

    的网络，进行重要节点发现需要选择适合的节点中心性。如何设计普适的、考虑

    网络功能的节点中心性度量以及在不同的分析任务中如何选择合理的节点中心性

    都将是未来一段时间内的研究热点。?

    1.3.3?链路预测与网络演化?

    分析利用动态演化网络的关键在于认识理解网络基础元素的演化规律。 对于网

    络演化的研究，传统的网络科学方法主要是基于理论模型，分析理论演化模型生

    成的网络是否具有与真实网络类似的拓扑性质。但是，由于可以用来对模型网络

    和真实网络进行比较的拓扑性质太多，各个指标表现可能不一致，所以无法准确

    评价网络演化模型的性能。近年来，部分研究者提出基于链路预测框架研究网络

    演化问题。链路预测根据已知网络结构信息、基于指定的估计机制计算链路产生

    的可能性。通过比较不同链路预测方法的准确性可以直观的对各链路预测方法蕴

    含的网络演化机制进行显著性判别，从而发现网络演化的主要驱动因素、建模预

    测网络演化[12]。?

    Jon? Kleinberg 等人在文献[9]中首先研究了基于已知网络结构数据预测未知网

    络链路的可行性问题，并发现网络演化过程能够基于网络结构本身实现预测。基

    于此工作，大量基于已知网络结构的链路预测方法被提出，其主要包括基于相似

    性的方法、基于最大似然估计法和基于机器学习的方法[63]。基于相似性的方法假

    设结构上越相似的节点它们之间存在链路的可能性越高，并且两个节点的相似度

    可以通过链路传递。基于相似性的链路预测方法可以进一步细分为基于近邻的方

    法和基于距离的方法。基于近邻的方法认为：如果两个节点有更多的共同邻居，则它们之间更可能产生一条链路，相关的相似性度量有共同近邻度量(Common?

    Neighbor,?CN) 、Adamic-Adar 方法(Adamic-Adar,?AA)

    [64]

    、资源分配方法(Resource?

    allocation,?RA)

    [65]

    、Leicht–Holme–Newman度量(LHN)[66]

    等。基于距离的链路预

    万方数据电子科技大学博士学位论文

    10?

    测方法假设链路存在的概率是由节点间的距离或者最短路径决定的，相关的相似

    性度量有局部路径方法(Local? Path,? LP)

    [67]

    、全局路径方法 Katz 度量[68]

    、Leicht–Holme–Newman-II度量(LHN-?II)[66]

    等。基于最大似然估计法的方法主要

    包括层次结构模型(HSM)方法[69]

    和随机块模型(SBM)方法[40]。基于机器学习

    的方法主要是监督学习方法[70]

    和非负矩阵分解方法(NMF)[71]。另外，还有平均

    通勤时间(Average?Commute?Time,?ACT)方法[72]

    、余弦相似性方法[73]

    、有重启的随

    机游走方法? (Random?Walk?with?Restart,?RWR)

    [74]

    、 SimRank方法[75]

    以及基于信息论

    [76]

    、监督随机行走[77]

    、博弈论[78]

    等技术的解决方案。由于结构相似性方法的简单

    实用特性，基于相似性的链路预测方法成为链路预测问题研究的主要方向。?

    网络演化是真实网络中的一种普遍现象。对于网络演化问题的研究，除了小世

    界网络模型、无标度网络模型等经典理论模型外，现在的工作主要是从真实动态

    网络数据分析的角度展开的。文献[79]基于真实的动态校园社会网络数据分析了不

    同的学校组织架构下校园社会网络的变化情况，发现网络演化是网络自身拓扑和

    网络外在环境共同作用的结果。文献[80]研究了流行性(Popularity)与相似性

    (Similarity)两种网络演化机制。结果表明流行性只是吸引新生链路的原因之一，另

    一个影响因素是相似性。作者权衡两种因素提出一个演化模型，其能够准确的刻

    画大规模网络的演化并预测新的链路。文献[12]认为网络演化是由多个演化机制共

    同驱动的，研究者提出综合多个演化机制的混合模型以模拟真实的网络演化。?

    为了理解动态演化网络中链路的产生机理， 近年来人们开展了大量的实证分析

    研究。文献[81]分析了微博网络中链路的形成过程，认为 90%的新生链路是在节点

    两跳范围内创建的，网络演化存在聚集(Clustering)效应。文献[82]基于 Twitter数据

    分析了信息网络中的有向三元闭包(Triadic?Closure)结构， 其结果表明有向三元闭包

    在大规模信息网络中明显存在，且其产生强度与节点的流行性有关，是链路形成

    的重要影响因素。虽然网络结构影响网络中的信息传播过程，但是网路结构也被

    信息传播过程所改变，文献[83]对微博数据的实证分析工作表明节点更愿意与信息

    传播路径上的节点相连。所以，基于信息传播路径的捷径(Shortcuts)机制也是影响

    网络演化的重要因素。?

    综上所述，链路预测除了结构相似性之外，还与流行性、相似性、聚类特征、网络行为、时间序列、空间距离等因素相关。另外，为了更好的预测网络链路、建模网络演化，网络演化算法还需要考虑节点以及链路的内容属性等因素。所以，网络演化是由多个因素共同作用而形成的复杂动态过程。对于网络演化的研究，除了探索新的影响因素外，如何选择、融合多个潜在影响因素以及如何鉴别影响

    网络动态演化的关键因素都是网络演化建模预测领域的重要问题。?

    万方数据第一章 绪论

    11?

    1.3.4?信息传播演化分析与建模?

    从新闻报道到社会谣言、从流行时尚到思想文化、从经济危机到恐怖主义，这

    些现象的背后都是传播动力学过程。深入研究网络信息的传播规律，理解用户对

    信息的转发机制，可以优化营销策略、规约网络行为、改善网络服务。当前关于

    信息传播过程的研究主要分为两方面，即理论传播模型在模型网络上的传播特性

    分析以及真实社会信息网络上传播过程的分析建模。理论传播模型方面的研究主

    要集中在疾病传播模型。由于网络异质性对疾病传播有重要影响，文献[84]提出边

    权划分方法对传播门限值和最终传播范围进行估计。 文献[85]基于SIR 传播模型对

    基于平均场方法、淬火平均场、动态消息传播方法的传播门限值不一致性问题进

    行了系统的分析，为门限值估计方法的选择提供了指导。另外，疾病传播在有向

    网络、多层网络等不同类型网络上的传播特性也被广泛研究[86-87]。?

    在文献[88]中，研究人员进行了社会行为传播实验。结果表明行为传播与一般

    的信息传播和疾病传播有所不同。与信息和疾病在小世界网络中传播较快不同，行为在高聚类网络中比小世界网络中传播得更快更广。所以，传播过程可以为分

    为两类，一类是简单的接触型的传播，另一类是多次强化型的传播。文献[89]基于

    以上研究成果，提出一个强调社会强化作用的传播模型。在规则网络和随机网络

    上的实验结果表明此模型能够很好的解释以上工作中的行为传播和信息传播过

    程，也表明不仅仅是行为传播，信息传播过程也需要强化确认，从而对以上工作

    的结论形成了补充。?

    在信息传播建模方面，文献[90]基于 Twitter数据分析消息标签的传播情况。结

    果发现不同主题的标签其传播模式差异很大，原因不仅仅与强化次数有关，也与

    标签本身的主题语义有关。文献[91]基于 Twiteer 数据预测消息将来的流行程度，其从结构、内容、语义、用户等多个方面构建特征，基于泛化线性模型以及朴素

    贝叶斯模型将流行度预测问题建模为一个机器学习问题。文献[92]认为宏观的信息

    传播预测可以通过对微观个体转发的建模来实现，结合多个维度的特征构建了一

    个基于机器学习方法的微观个体转发模型，并通过异步独立传播模型

    (Asynchronous? Independent?Cascades,?AsIC)将个体转发预测结果进行整合。与以上

    工作不同的是，文献[14]提出直接基于宏观全局性信息传播数据进行传播预测。?

    总体而言，信息传播与行为传播比较接近，与疾病传播差别较大。信息的传播

    强度会随着时间的增长而逐渐衰减，信息传播与传播者的兴趣和信息内容相关，信息传播过程中会受到传播个体状态的影响，会受到社会强化作用的影响。所以，信息传播受到多方面因素的共同作用，具有高度的复杂性，建模预测信息传播过

    程是一项挑战性的工作。?

    万方数据电子科技大学博士学位论文

    12?

    1.4?面临的问题和挑战?

    网络数据具有高度的复杂异构性， 对网络数据的分析挖掘不仅要处理网络结构

    数据，还要处理网络行为数据以及网络内容数据，不仅要处理静态网络数据，还

    要处理动态网络数据。面对复杂网络数据，传统的数据处理技术已经难以满足其

    分析需求。虽然本文提出从网络科学的视角进行研究，但是网络科学技术方法比

    较理论化，无法直接用于现实数据的分析挖掘任务。所以，进行可靠稳定、高效

    准确的网络数据挖掘处理仍然面临着诸多挑战。?

    研究分析表明， 社团、 枢纽节点以及离群节点等都是网络结构的重要特征[15,93]。

    其中，社团结构是联系微观网络行为与宏观网络特性的重要桥梁，社团结构让人

    们有机会研究基于单个节点或者网络整体无法探知的结构、功能特征。枢纽节点

    往往与多个节点相连，与网络功能紧密相关。例如：在疾病传播网络中，疾病常

    常基于枢纽节点跨越不同群组，对枢纽节点进行免疫能够有效控制传染性疾病扩

    散。离群节点与网络节点的一般行为或特征不一致，离群节点检测可用于发现异

    常，对离群点的预处理可以提高其它网络分析任务的效果。关于网络结构检测分

    析，早期研究工作主要关注互斥社团检测问题，提出了包括划分类方法[15,23]

    、聚

    合类方法[7,26]

    、矩阵相关方法[94-95]

    、基于模型的方法[30,33,40]

    等多种检测算法。但是，除了互斥社团，真实网络中社团结构之间还常常蕴含层次、重叠等复杂逻辑关系。

    虽然近期对社团层次性和重叠性已经有了初步的研究工作[38,96-98]

    ， 但是这些工作主

    要是对社团的层次特性和重叠特性分别展开研究。另外，除了社团结构，网络结

    构检测还需要考虑枢纽节点、离群节点等微观结构特征。因此，网络数据的分析

    挖掘需要考虑数据的内在复杂性，分析网络不同尺度的结构特征，研究网络结构

    的整体组织模式以及网络节点在网络组织中的角色作用，进行网络结构的整体检

    测分析是当前网络数据挖掘研究领域的一项重要挑战。?

    对于网络的微观结构特征， 由于网络结构的异构性， 网络中存在少数重要节点。

    它们相比网络其他节点，能够在更大程度上影响网络结构与功能。网络重要节点

    一般数量非常少，但其影响却可以快速地波及到网络中大部分节点。由于网络重

    要节点的影响巨大，基于不同的思想的多种发现网络重要节点的中心性度量被提

    出[51-57]。近年来的研究发现，中心性度量的有效性与具体应用问题直接相关[99-100]。

    文献[101]研究如何在网络中选择最佳节点作为传播源以最大化影响力。文献[21]

    研究度中心性、介数中心性、特征向量中心性等多种不同的中心性度量在网络鲁

    棒性问题中的表现。文献[102]研究基于节点中心性的节点免疫策略从而使疾病传

    播控制最优化。文献[10]提出群体影响力中心性(Collective? influence，CI)，并将

    其应用于影响力最大化、网络鲁棒性以及节点免疫控制等问题进行性能评价。综

    万方数据第一章 绪论

    13?

    上，由于不同问题场景对于网络重要节点的定义不同，完全通用的、能够适用于

    任何网络、任何问题的中心性度量可能是不存在的。所以，网络重要节点发现问

    题更合理的目标是针对某一个特定问题进行节点中心性研究。?

    网络结构数据除了静态特征，还具有动态演化性。网络结构动态演化过程的建

    模预测是网络数据挖掘领域的一个重要问题。动态网络的建模预测可以用于病毒

    传播网络的控制、动态金融网络的调控和生态网络保护等。对于动态网络的演化

    预测，理论上已经存在多种网络演化模型[17]

    ，包括全局耦合网络模型、星型网络

    模型、ER 随机网络模型、小世界网络模型以及无标度网络模型等。然而，这些模

    型都是从理论上对网络的近似模拟，而真实网络系统根据其现实应用背景不同往

    往具有不同特性。所以，虽然这些理论模型对于网络演化机制的认识理解十分重

    要，但是对于实际动态网络的建模预测不够精细具体。?

    关于网络演化， 到目前为止已经进行了许多揭示动态网络演化机制的实证分析

    工作[83,103,104,105]。文献[104]通过分析四个带有时序信息的在线社交网络发现，网络

    中大多数新生链路跨越的距离非常短，经常形成三角闭合结构。此外，文献[105]

    的研究结果表明，动态演化网络各个状态的自相关函数是连续的，这揭示了网络

    当前时刻的状态与上一时间点网络状态的相关性。从群体演化角度，研究人员发

    现许多新的群体成员是当前群体成员的近邻节点或者二跳近邻节点，并且这些近

    邻节点加入结构紧密的群体的可能性比加入结构松散的群体的可能性更大[106-107]。

    换而言之，网络近邻节点更倾向于与紧密关联的节点相连。因此，网络结构信息、网络节点交互的时序信息都会影响网络的动态演化。所以，网络演化受到结构信

    息、时间标记、动力学过程等多方面因素的影响，如何综合多方面的影响因素构

    建高效、准确的网络演化预测模型是一个重要挑战。

    除了网络结构的动态性， 网络节点通常根据邻居节点的决策行为对接收到的消

    息进行响应，从而形成网络信息的动态传播过程。信息传播过程抽象的描述了各

    种传播现象，包括创新发明的普及、社会运动的兴起以及新闻、舆论的传播等。

    相应的，信息传播过程的演化预测有着广泛的应用领域，包括加速创新传播、进

    行病毒式营销、实现谣言管控等。与网络结构演化建模问题类似，当前网络科学

    领域对传播过程的研究主要基于 SI、SIS、SIR等理论模型[17]

    ，探索它们在随机网

    络、小世界网络、无标度网络等不同模型网络上的性质规律。然而，理论网络模

    型与理论传播模型都是为了探索网络的一般规律，现实网络和现实信息传播过程

    具有与理论网络模型和传播模型不同的特征。所以，尽管信息传播现象在网络中

    无处不在，但是对信息传播的建模预测至今仍然没有很好的解决方案。?

    近年来， 大量可用的在线社交网络数据使得关于信息传播的研究有了长足的进

    万方数据电子科技大学博士学位论文

    14?

    步。研究人员开展了许多在线社交网络信息传播的分析工作[14,108-114]。其中，许多

    工作[14,108,111-112,114]

    都基于已知的消息传播结构图预测消息的最终传播规模。然而，由于信息采集的限制，包括传播结构图等传播过程的全局信息往往是不可用的。

    同时，对于新发起的信息传播过程，有意义的全局传播信息也非常少。除了消息

    传播的最终规模，其它的传播信息，包括转发节点、转发时间等，也是现实应用

    关注的焦点。另外，现实应用要求提出的信息传播预测方法要能够适用于包括博

    客、电子邮件、在线社交等多种类型的信息传播应用。在许多情况下，消息转发、传播是多个显式和隐含因素共同作用的结果，这使得准确建模信息传播过程十分

    困难。所以，如何将时间、内容、结构、兴趣等要素进行整合从而建模信息传播

    过程，如何基于网络数据挖掘实际信息传播过程的影响要素以及相关属性信息以

    及如何在复杂网络环境中调控信息传播过程都是网络数据处理面临的挑战。?

    1.5?论文主要内容与章节安排?

    1.5.1?主要研究内容与创新点?

    本文从三个方面对复杂网络数据的内在模式和演化规律进行分析研究， 主要包

    括网络结构的静态检测分析、网络结构的动态演化预测以及网络上信息传播过程

    的建模预测。在静态检测分析方面，分别进行了网络结构特征的整体检测分析研

    究和微观网络特殊节点的检测发现研究；在网络结构的动态演化预测方面，基于

    链路预测的研究框架，结合结构信息和时序信息，提出网络演化预测模型；在信

    息传播预测方面，主要关注在线社交网络上消息传播过程的建模，提出了结合转

    发行为估计模型和级联传播算法的预测模型。?

    本文主要创新点和贡献具体如下：?

    (1)通过对基本标记传播算法传播特性的分析，重新定义了标记更新机制。

    根据现实网络结构的异构性特征，提出了可自适应调控的标记传播算法。提出的

    基于标记传播的网络结构整体检测分析方法，不依赖于任何先验参数，能够通过

    对迭代结果的分析实现多个结构特征的检测发现。通过层次化超网的构建，整体

    检测分析方法可以发现网络的多层次多尺度组织结构。?

    (2)对网络结构中的重要节点检测问题，从不同的角度、不同思路提出了两

    种节点中心性度量，并在最优网络分裂问题中进行了性能测试。?

    (3)提出了基于网络稀疏性的自适应链路预测相似性度量，同时结合影响网

    络演化的潜在因素构建了节点位置时空漂移模型。基于位置漂移模型，利用现有

    的网络结构信息推理网络节点将来的结构相似度，然后基于推理的结果进行链路

    万方数据第一章 绪论

    15?

    预测，从而实现动态网络的结构预测。?

    (4)提出了结合转发行为估计和级联传播建模相结合的在线社交网络信息传

    播预测方法，并基于二分类模型对个体转发行为进行建模，基于标记传播算法提

    出级联传播模型。通过基于新浪微博数据的学习发现，影响微博传播的主要因素

    是微博的存在时间以及微博的内容长度，整体上影响信息传播的驱动机制是消息

    的时效性和其内容语义。?

    1.5.2?论文章节安排?

    本文各章节之间的关系如图 1-2 所示，具体的章节安排如下：?

    第一章阐述本课题的研究背景，给出网络数据分析挖掘的总体研究框架，介

    绍本课题的研究目标和研究意义，回顾总结相关问题的国内外研究进展，分析面

    临的问题和挑战。?

    第二章，研究网络静态结构的模式挖掘问题，以社团结构为主体、同时考虑

    网络节点的不同角色，提出了基于标记传播过程的多尺度、多层次网络结构整体

    检测算法 LINSIA，并进行实验验证。?

    ·

    图 1-2 论文组织架构图?

    万方数据电子科技大学博士学位论文

    16?

    第三章，对网络节点角色进行进一步研究，面向网络重要节点检测问题，基

    于不同角度提出了两个节点中心性度量，并基于多种网络在最优网络分裂任务中

    进行性能测试。?

    第四章，研究动态网络结构的演化预测问题，提出结构稀疏自适应的节点相

    似性度量，并提出建模网络节点相对位置动态变化的漂移模型。本文结合节点位

    置漂移模型和提出的相似性度量进行网络未来链路的预测，并进行性能测试。?

    第五章，研究网络信息传播的建模预测问题，基于分类模型和标记传播过程

    分别对个体转发行为和级联传播过程进行建模，结合以上模型实现在线社交网络

    中信息传播额预测，并对影响信息传播的潜在因素进行分析，对提出的预测方法

    进行实验评估。?

    第六章，对全文工作进行总结，提出未来的研究规划和研究思路。?

    ·

    万方数据第二章 网络结构检测分析研究

    17?

    第二章?网络结构检测分析研究?

    理解网络的结构和功能并分析两者之间的关系是网络数据处理的一个核心目

    标。由于网络功能承载于网络结构之上，所以研究网络结构对于理解、调控网络

    功能具有重要意义。社团是网络结构的主要特征之一，在真实网络中社团还存在

    多层次性和相互重叠性。同时，网络的异构性导致网络中存在一些特殊节点，包

    括对网络功能具有与其数量不成比例的影响力的枢纽节点以及与网络主体弱相关

    的离群节点等。本章对网络结构数据进行分析，研究网络不同层次、不同尺度、不同类型的结构特征，提出基于标记传播方法的网络结构整体检测分析算法

    LINSIA?(Label?based?integrated?network?structure?investigation?algorithm)。?

    2.1?基本标记传播算法?

    为了进行网络结构的整体检测分析，本文提出基于标记传播方法[30]

    的解决方

    案。其基本思想是：基于节点标记的迭代更新，全部节点标记最终稳定在一个与

    网络结构紧密相关的均衡状态。此均衡状态是节点综合网络局部结构和全局结构

    之后的选择。其中，具有相同标记的节点对应一个社团，同时属于多个社团的节

    点是枢纽节点，不属于任何社团或者无法形成社团的孤立节点即为离群点。从而，基于此均衡状态解析网络结构。通过对标记传播过程进行调节控制，使得算法最

    终能够识别多层次、多尺度的社团结构以及不同的节点角色。?

    基本标记传播算法[30]

    为每个节点初始分配一个唯一标记。在更新过程中，每个

    节点统计邻居节点标记，以邻居节点中数量最多的标记更新自己标记。若出现多

    个数量相等的标记，则随机选择一个。由于每个节点标记趋同于多数邻居节点，所以紧密相连的节点的标记会很快趋于一致，如图 2-1 所示。从而，随着标记的迭

    代更新，不同标记的数量会逐渐减少，少数节点标记会主导局部结构区域，最终

    以相同的节点标记表征节点之间结构上的紧密相关性。?

    对于标记更新过程，基本的标记传播算法可以是同步标记更新，也可以是异步

    标记更新。在同步更新过程中，每个节点基于邻居节点上一轮的标记进行标记选

    择， 即 1 2

    ( ) ( ( 1), ( 1),..., ( 1))

    n x x x x

    C t f C t C t C t ? ? ? ? ， 其中 ( ) x

    C t 为节点x在时刻t的标记。

    在异步更新过程中，每个节点基于邻居节点当前标记进行标记选择，即

    1 1 1

    ( ) ( ( ), ..., ( ), ( 1), ..., ( 1))

    k k k n x x x x x

    C t f C t C t C t C t

    · ?

    · ? ? ，其中 1 1 , ...,k

    x x ? 为此轮已经完成标

    记更新的邻居节点， 1, ...,k n x x ? 为此轮还没有进行标记更新的邻居节点。在基本标

    记传播算法中，对于每一轮迭代更新，节点的更新顺序随机确定。?

    万方数据电子科技大学博士学位论文

    18?

    ·

    图 2-1? 紧密相连结构的标记传播过程(从左到右，节点标记依次更新。由于链路的

    高密度性，全部节点最终获得相同的标记。)?

    ·

    图 2-2? 包含多个紧密相连结构的网络的节点标记迭代更新过程(节点标记迭代更新

    过程的收敛性由网络的子结构决定，而不是网络整体。)?

    在标记更新过程中，随着每个节点的标记趋同于多数邻居节点，网络标记的总

    个数不断减少，如图2-1 所示。同时，网络紧密相连的子结构中的节点标记很难影

    响此结构以外其它节点标记的选择。根据文献[30]，基本标记传播算法的迭代次数

    与网络节点数无关， 在迭代 5 次之后， 95%的网络节点的标记达到稳定状态。 另外，文献[28]也确认了此收敛性质，同时证明，紧密相连子结构内部节点的标记影响外

    部其它节点标记的概率很小，节点标记迭代更新的收敛性主要由网络中各个紧密

    相连的子结构决定， 而不是网络整体， 如图 2-2 所示。 根据各个子结构的特征不同，收敛速度有所差异。所以，基本标记传播算法是收敛的。另外，文献[28]表明基于

    异步迭代更新的基本标记传播算法收敛性明显优于同步迭代更新。?

    2.2?基于标记传播的网络结构检测算法?

    2.2.1?标记传播与节点角色?

    为了便于后续算法介绍，先给出本节所提算法的相关基础定义。节点影响力代

    表了节点在网络中的重要性，标记影响力表示在标记迭代更新过程中标记的流行

    万方数据第二章 网络结构检测分析研究

    19?

    度。本文通过一个自适应变量? 调节节点度对节点影响力与标记影响力的影响，基于扩展邻居核心度(Extended? neighborhood? coreness,? ENCoreness)

    [115]

    刻画节点的

    全局重要性，基于节点度刻画节点的本地影响力。本文定义节点i的标记集合为

    i

    Lset ，定义候选标记集合为 i

    LC ， i

    LC 等于节点i的邻居节点标记集合的并集。本

    文统计邻居节点集合中各个标记的占比计算标记影响力。?

    定义 2-1：节点影响力 对于节点i，其节点影响力定义如下?

    ,( )

    ( )

    ( ) ( )

    ( )

    i j

    j N i

    ENCoreness j

    NI i ENCoreness i w

    degree j

    ·

    ·

    · ? ? ? ? ? ? ? ? ? ? ?(2-1)?

    其中 ( ) ENCoreness i 是节点i的 ENCoreness中心度， ( ) degree i 是i的节点度， , i j

    w 是

    链路 ij

    e 的权重， ( ) N i 是节点 i 的邻居节点集合，? 是一个自适应变量，,( )

    ( )

    i j

    ENCoreness j

    w

    degree j

    · ? 表示邻居节点 j在其所有邻居节点中对节点i的影响比例。?

    定义 2-2：标记影响力 令 i

    LIset 为集合 i

    LC 中各个标记的影响力，计算如下?

    ( )

    ( )

    { | , }

    ( )

    j

    p

    j p p

    i i i ij i m

    j N i j

    m Lset

    LI NI j

    LIset LI LI w p LC

    degree j LI

    ·

    ·

    ·

    · ? ? ? ? ? ? ? ? ? ? ?(2-2)?

    其中 j

    Lset 是节点 j的标记集合， i

    LC 为节点i的候选标记集合， p

    j

    LI 是节点 j的标

    记 p的影响力，如果节点 j没有标记 p，则 p

    j

    LI 等于 0。 ( )

    ( )

    NI j

    degree j

    · 表示邻居节点 j

    在其所有邻居节点中对节点i的影响比例，j

    p

    j

    m

    j

    m Lset

    LI

    LI

    ·

    · 表示标记 p在节点 j的全部标

    记中的影响力占比。?

    定义 2-3：节点标记 根据公式(2-2) ，在非重叠网络中，选择集合 i

    LIset 中影

    响力最大的标记作为节点i的标记， 从而发现互斥社团。 在存在重叠社团的网络中，选择集合 i

    LIset 中影响力处于最大量级的标记作为节点i的最终标记，定义如下：?

    3 3 3

    { | log(max( )) 1 log( ) log(max( )) , } p p

    i i i i i i

    Lset p LIset LI LIset LI LIset ? ? ? ? ? (2-3)?

    定义 2-4：枢纽节点 根据标记迭代更新结果，本文定义具有多个标记的节点为

    枢纽节点，计算如下：?

    { | ( ) 1, } i

    Hubs i len Lset i V ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(2-4)?

    其中 i

    Lset 为节点i的标记集合， ( ) i

    len Lset 为标记数量，V 为网络节点集合。?

    定义 2-5： 离群节点? 离群点往往是节点度很小且与网络主体结构关联很弱的节

    万方数据电子科技大学博士学位论文

    20?

    点。在基于标记传播的网络结构分析中，离群点应该具有节点度小、与社团连接

    少、具有独立标记、不是枢纽节点等特征，故定义离群点如下：?

    { | ( ) 1 ( ) 2 ( , ) 1, } i i i

    Outliers i len Lset degree i label Inset i V ? ? ? ? ? ? ? ?(2-5)?

    其中 i

    Lset 为节点i的标记集合， i

    label 为节点i的标记， i

    Inset 为节点i及其邻居的初

    始标记集合。如果 i

    label 与初始标记集合 i

    Inset 中的任何一个相同，则函数

    ( , ) i i

    label Inset ? 等于 1，否则等于 0。?

    定义 2-6：隶属强度 在重叠社团中，枢纽节点可以以不同隶属强度同时属于多

    个社团。为了刻画枢纽节点对各个社团的隶属程度，定义社团隶属强度如下：?

    { | , }

    i

    q

    q q i

    i i i i m

    i

    m Lset

    LI

    PIntensitySet PI PI q Lset

    LI

    ·

    · ? ?

    · ? ? ? ? ? ?(2-6)?

    其中 q

    i

    PI 为节点i对于标记为q的社团的隶属强度， q

    i

    LI 为节点i的标记q的影响力，i

    Lset 为节点i的标记集合。?

    2.2.2?LINSIA网络结构检测算法?

    由于节点标记趋同于大多数邻居节点的标记， 从而网络中的密集区域随着标记

    的迭代更新很快形成一致标记。这些密集区域中具有一致标记的节点组继续扩展

    以试图捕获更多节点以扩充当前节点组。当节点组扩展到另一个节点组的边界时，两个节点组形成竞争，如图 2-3(a)所示，其中左右两个节点组在红色节点处形

    成竞争。当迭代更新过程最终收敛时，网络中的各个密集区域的节点组之间达到

    均衡状态，从而实现网络结构的划分。然而，由于网络结构的异构性[17]

    ，可能不

    存在对称结构，而是核心边缘结构，从而网络核心区域的节点的在形成一致节点

    标记后，会继续向边缘节点扩展，如图2-3(b)所示。?

    ·

    图 2-3? 标记迭代更新过程说明示例。(a)多个均衡密集区域之间形成相互竞争；(b)

    不均衡网络上的标记传播?

    万方数据第二章 网络结构检测分析研究

    21?

    ·

    图2-4? 极大极小社团划分说明示例。(a)极大社团划分；(b)极小社团划分

    为了使所提算法适用于各种异构网络， 本文提出基于网络异构性调节节点影响

    力和标记影响力，通过抑制网络核心节点以及高度节点对应的影响力的方式调控

    标记更新过程，从而实现与网络结构相适应的标记选择和结构检测。具体的，在

    公式 2-1 和公式2-2 节点影响力和标记影响力定义中，用参数? 均衡社团内部的凝

    聚性和社团之间的竞争性。如果参数? 取值很小，则 ENCoreness中心性高的网络

    核心节点和大度节点的节点影响力和标记影响力都会大大高于边缘节点。在标记

    选择过程中，这样的影响力差距使得密集区域中具有一致标记的节点组不断向网

    络边缘扩展，同时与边缘节点和核节点相连的网络节点趋于选择核节点标记。如

    此迭代更新，可能导致全部网络节点最终选择与核节点相同的标记，从而形成极

    大社团划分。如果? 取值很大，核心节点和大度节点的影响力会受到抑制，严重

    时会导致全部网络节点影响力和标记影响力大小相当，最终网络节点各自取不同

    的标记，从而形成很多极小社团划分。例如：如果不进行调控或者参数? 取值很

    小，在图 2-4(a)中，节点 , , , a b c d 的标记影响力远远大于 , , q r s等边缘节点的标

    记影响力，从而节点 p同时与多个边缘节点和一个核心节点相连时，根据标记影

    响力，此节点以很大概率选择核心节点的标记作为自身节点标记，而忽视局部网

    络结构。如此迭代更新，最终导致全部网络节点具有相同节点标记。相反的，如

    果参数? 取值很大，则最终基于标记传播的网络结构划分很形成许多结构碎片，如图 2-4(b)所示。所以，刻画网络异构性的参数? 是必要的。?

    本文基于网络的异构性确定参数? 的取值，对基于 k-shell 中心性[54]

    排序的节

    点序列，以节点影响力累积和等于总影响力二分之一时的节点数占比度量网络异

    构性度量r。如果网络完全均衡，异构性度量 0.5 r ? ，并定义 0.1 r ? 时为极不均衡

    状态，从而r的中值为0.3，最终参数? 的取值定义如下。在任意网络中，结构自

    适应调控因子? 计算如下：?

    万方数据电子科技大学博士学位论文

    22?

    '

    13

    1.0 (0.3 )

    N

    N

    · ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(2-7)?

    其中N 表示网络节点总数， '

    N 表示对应于影响力累积和的节点数。?

    由于节点的标记更新相对于边缘节点更多的受核节点标记的影响，核节点标

    记的准确更新对于全部节点标记的准确性至关重要。否则，核节点不准确的标记

    信息会扩散到全网，从而影响其它节点标记的准确性。另外，为了防止边缘节点

    以及离群点标记被淹没，影响力较低的边缘节点和离群点标记应该优先更新。例

    如，在图 2-4(b)，如果节点 p早于 , , q r s等邻居节点更新节点标记，则以很大概

    率选择核心节点c的标记作为自身节点标记。 否则， , , q r s等邻居节点选择节点 p的

    标记作为自己的标记，节点 p在 , , q r s等邻居节点之后更新节点标记时，邻居标记

    的影响力之和很可能大于核心节点c的标记的影响力，从而形成独立结构划分。综

    上，本文提出基于节点影响力升序进行标记更新。?

    基于以上思想，改进之后的 LPA 算法伪码如算法 1 所示。其中，本文在步骤

    2 和步骤 3 中提出基于固定顺序进行节点标记更新，同时计算节点标记的影响力，基于此影响力进行标记选择，从而避免了基本 LPA 算法中随机节点选择和多个候

    选标记随机选择所导致的算法不稳定(instability)问题。另外，? 本文的标记影响

    力为连续值，同时在步骤 3 中采用异步标记更新方式，强化了 LPA算法的收敛性。

    在步骤 2 和步骤 3 中，结构自适应调控因子? 通过影响节点影响力和标记影响力

    取值调控标记更新过程。最终，步骤 4 根据节点最终标记解析网络结构。?

    由于真实网络中低层次的多个社团往往嵌入到高层次的一个社团中， 从而形成

    嵌套层次社团结构。为了检测网络中的多尺度、层次性社团结构，本文对算法 1

    进行扩展，构建一个加权的、从底向上的多层超级网络。首先，LINSIA 在原始网

    络中基于算法 1 检测重叠社团，并基于社团检测结果以超级节点取代社团结构，从而构建一个加权超级网络。其次，在构建的超级网络之上，基于算法 1 进行互

    斥社团检测。将超级网络的互斥社团映射到原始网络更新网络社团，获得更大尺

    度的社团划分。然后，基于新的社团结构构建更高层次的超级网络，继而进行社

    团检测。循环迭代以上两步，直到社团结构不再发生变化。其中，在超级网络构

    建过程中，节点之间的链路权重计算如下：?

    , ( ) ( )

    i j

    mn m n

    ij

    m com n com ij

    a len C len C w

    N ? ?

    ·

    · ? ? ? ? ? ? ? ? ? ? ? ?(2-8)?

    其中 i

    com 为超级节点i 对应的社团， mn a 指示节点m 和n 之间是否存在链路，( ) m len C 表示节点m参与的社团的个数， ij

    N 表示在社团 i

    com 和 j

    com 之间存在链路

    的节点个数。?

    万方数据第二章 网络结构检测分析研究

    23?

    Algorithm 1 Imporoved?LPA?algorithm?

    Input: Network? ? ( , ) G V E ? ,1 2 ? { , ,..., } n V v v v ? .

    Output: Community?division? ? CS ,?

    i

    PIntensitySet , Hubs and? Outliers .

    Step 1:?Initialization:?assign?a?unique?label?to?each?node?in?the?network.?

    Step 2:?Calculate?node?influence? ( ) NI i ? for?each?node?according?to?e.q.?(2-1)?and?rank?nodes?

    ascendingly?into? NList .?

    Step 3:?Iteration?of?label?propagation:?

    (a) Set? 1 t ? ;?

    (b) For? each? node?

    i

    v ,?

    i

    v NList ? ,? calculate? the? influence?

    i

    LIset ? of? its? candidate?

    labels?according?to?e.q.?(2-2).?

    (c) Updating? node? label?

    i

    Lset ? of? node?

    i

    v ? by?

    1 1

    ( ( ),..., ( ),i

    v v

    f C t C t

    · 1

    ( ),i

    v

    C t

    ·

    ·

    1

    ( 1),i

    v

    C t

    ·

    · ? ..., ( 1))

    n v

    C t ? ? according? to? e.q.? (2-3),? where? 1 v ,2 v ,… 1 i

    v ? ? are?

    neighbors? of? node?

    i

    v ? that? have? already? been? updated? in? the? curren? iteration,? and?

    1 i

    v ? ,… n v ? are?neighbors?that?are?not?yet?updated?in?the?curren?iteration?.?

    (d) If?labels?do?not?change?anymore,?then?stop.?Else,?set? t+1 t ? ? and?go?to?Step?(b).?

    Step 4:? Get? community? division? ? CS ? in? which? all? nodes? sharing? the? same? label? form? a?

    community,?and?calculate? Hubs ,? Outliers ? and?

    i

    PIntensitySet .?

    基于构建的多层次超级网络以及各层互斥社团划分，LINSIA算法可以实现多

    层次、多尺度社团检测。LINSIA算法中高层次的一个大规模社团可能包含低层次

    的多个小规模社团，从而能够揭示社团之间的层次嵌套关系。LINSIA算法允许节

    点同时拥有多个标记，从而能够发现重叠社团结构。最后，基于模块度[7]

    以及扩展

    模块度[39]

    概念，通过模块度最大化方法在多层次社团结构中选择最佳社团划分，并基于公式(2-4)、公式(2-5)检测枢纽节点和离群点。具体的 LINSIA算法伪

    码如算法 2 所示。其中，步骤 2 基于算法 1 获得初始社团划分；步骤 3 构建超级

    网络，基于算法 1 获得超级网络的社团划分并获得原始网络更大尺度的社团划分

    结果。通过循环构建超级网络和社团检测，步骤 2 获得网络的多层次、多尺度重

    叠社团结构；步骤 4 基于社团模块度化从各层社团划分中选择模块度最大的划分

    作为最优社团划分；步骤 5 基于节点标记计算网络的其它结构特征。LINSIA构建

    多层次超级网络以及检测网络结构的过程如图 2-5，图 2-6 所示。?

    2.2.3?LINSIA算法时间复杂度?

    LINSIA 算法的时间复杂度等于在不同层次进行社团检测以及计算社团隶属强

    度、检测枢纽节点以及离群点的复杂度之和。在每一层次，社团检测的复杂度为

    万方数据电子科技大学博士学位论文

    24?

    ·

    图2-5? 社团检测与多层次网络构建?

    ·

    图 2-6? 网络结构划分与节点检测。(a)层次重叠社团结构；(b)网络结构检测结果?

    万方数据第二章 网络结构检测分析研究

    25?

    ( ) ( log( )) ( ) O n O n n O t m ? ? ? ? ，其中n和m是网络节点数和边数。 ( ) O n 是计算节点

    影响力的复杂度， ( log( )) O n n ? 是节点排序的复杂度， ( ) O t m ? 是标记更新的复杂度，t为标记更新的迭代次数。 如果层次化超级网络包含h层， 则总的时间复杂度为在h

    层中各个层次上的复杂度之和。另外，枢纽节点和离群点检测的复杂度为 ( ) O n 。

    实验分析表明在迭代更新以及层次化超网构建过程中t和h都是一个小整数，并且

    随着超级网络层次的增加其超级节点和边的数目会急剧减小，所以较高层次社团

    检测的复杂度很小，所以 LINSIA复杂度为 ( ) ( log( )) ( ) O n O n n O t m ? ? ? ? 。?

    Algorithm 2?LINSIA?algorithm?

    Input: Network? ? ( , ) G V E ? .

    Output: Hierarchical community?division?

    1 2 ? { , ,...} Dic CS CS ? ,?the?best?community?division?

    ·

    best

    CS ??

    1 2 ?{ , ,...} C C ,?

    i

    PIntensitySet , Hubs and? Outliers .

    Step 1:? 0 t? ,?initialize?label.?

    Step 2:? 1 t t ? ? ,?get?community?division? ?

    t

    CS ? and? ?

    t

    Dic CS ? ? using?Algorithm?1.?

    Step 3:?Find?community?division?set?

    1 2 ? { , ,...} Dic CS CS ? .?

    (a) Build?weighted?super-network?

    t

    SN ? based?on? ?

    t

    CS ;? ?

    (b) Get?disjoint?community?division? ?

    t

    CCS ? using?Algorithm?1;?

    (c) 1 t t ? ? ,?project? ?

    t

    CCS ? to?primitive?network?then?get? ?

    t

    CS ,? ?

    t

    Dic CS ? .?

    (d) Iterate?(a)?(b)?(c)?until?no?new?community?division?being?generated.?

    Step 4:?Select?division?from?

    1 2 ? { , ,...} Dic CS CS ? ? with?the?greatest?modularity?as? ?

    best

    CS .?

    Step 5:?Calculate?

    i

    PIntensitySet , Hubs and? Outliers based?on? ?

    best

    CS .?

    2.3?实验与结果分析?

    2.3.1?实验设计?

    本节将首先对所提算法中的初始标记影响力和自适应调控因子进行测评分析。

    然后，分别基于人工网络和真实网络数据集对提出的 LINSIA算法进行性能测评，并与多个相关算法进行性能比较，具体的基准算法简介如下。?

    LPA和NIBLPA算法[30,116]

    ：传统的基于标记传播方法的互斥社团检测算法。?

    NF 算法[26]

    ：基于模块度增益最大化策略进行社团融合构建结构层次树，最终

    基于层次树分割实现社团检测。?

    Louvian算法[38]

    ：基于模块度增益最大化的层次社团检测算法。?

    OCSBM 算法[117]

    ：基于产生式统计学习模型的重叠社团检测算法。?

    EAGL?E算法[39]

    ：基于最大团聚合框架的层次重叠社团检测算法。?

    万方数据电子科技大学博士学位论文

    26?

    为了评价 LINSIA算法的性能，本文具体将 LINSIA与 LPA和 NIBLPA算法进

    行比较以测试 LINSIA 对互斥社团的检测能力，将 LINSIA 与 NF 和 Louvain 算法

    进行比较以测试它对层次化社团结构的检测能力， 将 LINSIA与 OCSBM 算法进行

    比较以测试 LINSIA 对重叠社团结构的检测能力，将 LINSIA 与 EAGLE 算法进行

    比较以测试它对层次重叠社团结构的检测能力。为了比较各个算法对于社团检测

    的准确性，对于已知真实社团划分的网络，本文分别采用 NMI(Normalized?mutual?

    information)

    [118]

    以及 ENMI 指标[119]

    评价对互斥社团和重叠社团的检测结果。对于

    未知真实社团划分的网络，本文分别采用模块度 Q[7]

    以及扩展模块度EQ?[39]

    评价对

    互斥社团和重叠社团的检测结果。对于枢纽节点和离群节点的检测评估，本文采

    用可视化分析的方式进行检测结果的合理性评价。?

    2.3.2?初始标记影响力与自适应调控因子的影响?

    为了评价算法性能， 本节分析标记更新过程中初始标记影响力和自适应调控因

    子对 LINSIA算法性能的影响。在标记更新过程中，全部节点标记拥有相同的初始

    影响力。由于标记影响力的计算公式(2-2)以及标记的选择公式(2-3)都是以标

    记影响力的占比为基础的，所以标记的初始影响力对标记传播结果应该没有影响。

    为了进行验证，在基于 LFR 网络模型[120]

    产生的具有不同社团个数的人工网络上，将标记影响力取不同初始值并进行社团检测实验。根据图 2-7(a)中的实验结果

    可知，无论标记影响力初始值如何变化，LINSIA 算法产生的社团划分基本稳定。

    所以，LINSIA算法对初始标记影响力是不敏感的。?

    另外，本文分析了调控因子? 对 LINSIA算法性能的影响，不同? 取值条件下

    社团个数的变化情况如图 2-7(b)所示。从结果可知，公式(2-7)对? 的取值估

    计较为合理。基于此估计值，LINSIA能够准确的检测网络中包含的社团个数。?

    2.3.3?基于人工网络的算法性能评估?

    本文基于 LFR 网络模型[120]

    生成人工网络以测试 LINSIA算法的性能。LFR 网

    络产生模型可以通过多个参数调控人工网络的结构特征，包括节点数n、平均节点

    度k、混合比率? (节点将其? 比率的相关链路与其他社团中的节点相连)、重叠

    节点数 n O ，重叠节点的重叠强度 m O 以及层次社团结构中高层混合比率 '

    · 。为了进

    行性能评估， 本文共生成了 7 个不同结构的网络， 具体如表 2-1 所示。 其中， LRF_1

    和 LRF_2为非层次非重叠网络，LRF_3和 LRF_4为包含层次结构的网络，LRF_5

    和 LRF_6 为包含重叠社团结构的网络，LRF_7 为同时包含层次社团结构和重叠社

    团结构的网络。?

    万方数据第二章 网络结构检测分析研究

    27?

    ·

    ·

    (a)?

    ·

    (b)?

    图 2-7? 参数取值对LINSIA 算法性能的影响。(a)初始标记影响力；(b)拓扑自适应

    调控因子?

    基于以上人工网络，执行 LINSIA 算法的社团检测结果如表 2-2 所示。根据表

    2-2可以发现LPA和NIBLPA算法较为准确的检测出了网络 LRF_1和 LRF_2中的

    社团结构。同时，NF 和 Louvain 算法对 LRF_3 和 LRF_4 的社团检测结果也能够

    较好的匹配真实社团结构。在包含重叠结构的 LRF_5 和 LRF_6 网络中，OCSBM

    在给定社团数量的条件下较为完美的发现了网络的重叠社团结构。另外，尽管

    EAGLE 算法能够发现层次重叠社团结构，但实验结果显示其在 LRF_5、? LRF_6

    和 LRF_7网络中性能较差。与以上算法相对应的是，LINSIA算法在各个人工网络

    的社团检测任务中都能够准确的发现社团结构，且无需任何先验知识。?

    2.3.4?基于真实网络的算法性能评估?

    在此小节中， 本文将基于多个具有不同结构特征的真实网络对 LINSIA算法进

    万方数据电子科技大学博士学位论文

    28?

    行性能评价。为了展示 LINSIA算法的综合性能，本小节将分别从互斥社团检测、层次社团检测、重叠社团检测、层次重叠社团检测以及枢纽节点和离群点检测五

    个方面进行实验评估，真实网络数据集如表 2-3 所示。?

    (1)互斥社团检测?

    为了评价本文提出的 LINSIA算法对互斥社团的检测性能， 本文在真实网络中

    分别执行 LINSIA、LPA 以及 NIBLPA 算法，并比较它们的检测结果。根据表 2-4

    所示结果，相对于 LPA 和 NIBLPA算法，LINSIA 算法在互斥社团检测问题中总体

    上取得了更好的准确性。由于 LPA 是一个参数化的算法，其在同一网络上多次运

    行结果不一致，这一不足限制了 LPA算法在现实问题中的应用。LINSIA算法性能

    较优的原因是相对于 LPA 和 NIBLPA 算法，本文提出的 LINSIA 算法对标记影响

    力定义、标记选择策略以及标记传播过程都进行了优化。另外，为了展示 LINSIA

    算法对网络结构分析的有效性， 本文详细介绍 LINSIA对美国高校足球比赛网络[13]

    ·

    的社团检测结果。美国高校足球比赛网络共包括属于 12 个不同的联盟的 115支队

    伍以及 8 支独立队伍。LINSIA 算法对此网络的社团检测结果如图 2-8 所示。根据

    图 2-8 可知，LINSIA 算法共检测到了11 个社团，网络中的大多数节点都准确分配?

    表 2-1? 人工实验网络生成模型参数取值?

    ·

    表2-2? 人工实验网络社团检测结果?

    ·

    万方数据第二章 网络结构检测分析研究

    29?

    表 2-3? 真实实验网络?

    ·

    到了相应的社团中，最终的标准化互信息 NMI 取值为 0.7411。相应的，LPA 和

    NIBLPA算法对这些社团结构的检测准确性相对较低， 它们检测结果的最终标准化

    互信息 NMI取值分别为0.6832 和 0.7027。?

    (2)层次社团检测?

    为了评价 LINSIA 算法在层次社团检测中的性能，本文将其与 NF 和 Louvain

    算法进行比较，结果如表2-5 所示。由于是层次社团检测，其结果包括网络在多个

    层次上的不同社团划分。为了评价这些社团划分的准确性，对于真实社团结构已

    知的网络本文比较社团个数以及标准化互信息 NMI，对于真实社团结构未知的网

    络本文比较各个层次的社团模块度的平均值。根据表 2-5 可知，LINSIA 在层次社?

    ·

    图2-8? 基于 LINSIA 算法的美国高校足球比赛网络结果分析?

    万方数据电子科技大学博士学位论文

    30?

    表 2-4? 真实实验网络中互斥社团的检测结果?

    ·

    表 2-5? 真实实验网络中层次社团检测结果?

    ·

    表 2-6? 真实实验网络中重叠社团检测结果?

    ·

    表2-7? 真实实验网络中层次重叠社团检测结果?

    ·

    团检测问题中总体取得了相对NF和Louvain算法更好的准确性和更高的社团模块

    度。相对于 NF 和 Louvain 算法，LINSIA 算法虽然每个节点都基于邻居节点进行

    标记更新，但通过迭代传播节点的候选标记一定程度上反映了网络的全局结构信

    息，而 NF和 Louvain 没有相关机制获取网络全局结构信息。?

    (3)重叠社团检测?

    为了评价 LINSIA 算法对于重叠社团的检测性能，本文将 LINSIA 与 OCSBM

    算法进行比较，结果如表 2-6 所示。由于网络中真实的重叠社团信息未知，本文

    采用扩展模块度对得到的重叠社团质量进行评价。在给定社团数量的条件下，?

    OCSBM 在已知社团结构信息的网络中能够获得极高质量的社团划分。但是，OCSBM 的不足在于其需要网络中社团数量作为先验信息，不适用于真实社团数

    量未知的网络。相对于OCSBM，LINSIA具有更广泛的适用性。为了展示LINSIA

    万方数据第二章 网络结构检测分析研究

    31?

    算法对重叠社团检测的有效性， 本文详细介绍 LINSIA对美国政治博客网络[95]

    的分

    析结果，此网络根据在 2004 年美国总统大选期间有关美国政治的博客链接整理而

    成，各个博客根据它们是自由派或保守派被分为两类。LINSIA算法对此网络的检

    测结果如图 2-9 所示。根据图 2-9 可知，LINSIA 将全部博客大体上分为两部分，这与自由派和保守派两种政治立场相一致。另外，LINSIA算法能够检测出兼顾自

    由派和保守派的博客以及对自由派和保守派都不支持的博客，即重叠社团之间的

    枢纽节点和离群节点，如图 2-9 中的红色节点和绿色节点所示。?

    (4)层次重叠社团检测?

    为了评价 LINSIA 算法对于层次重叠社团的检测性能，本文将 LINSIA 与

    EAGLE 算法进行比较，结果如表 2-7 所示。由于网络中真实的社团重叠信息未

    知，本文计算各层社团划分的扩展模块度的平均值进行性能评价。另外，对于已

    知真实社团个数的网络，本文比较社团个数进行性能评价。根据表 2-7 可知，LINSIA算法相对于EAGLE算法具有明显的性能优势。另外，EAGLE基于最大团

    (Maximum?clique)进行社团检测，由于真实网络具有稀疏性，所以 EAGLE发现

    的最大团常常只包含几个节点，导致最终检测到的社团划分具有数量大规模小的

    特点。为了详细展示LINSIA算法的网络结构分析能力，本文将LINSIA应用于包

    含 62 只海豚的新西兰海豚种群网络，结果如图 2-10 所示。其中，图 2-10(a)展

    示了网络层次结构中较高层中的重叠社团结构，图 2-10(b)较低层中的重叠社团

    结构。对比图 2-10(a)和 2-10(b)，可以发现重叠社团结构之间的层次嵌套关

    系。根据文献[96]中的海豚种群网络的真实结构信息，可以发现 LINSIA基本能够

    检测到网络中的真实社团结构。另外，为了对比LINSIA算法和EAGLE算法的性

    能，本文将 LINSIA 应用到文献[39]中用于展示 EAGLE 性能的示意网络，最终的

    层次重叠社团结构如图 2-11 所示。对比图 2-11(a)和 2-11(b)，可以发现重叠

    社团在两个不同层次上嵌套关系以及社团之间存在的枢纽节点(红色节点)。根?

    据网络拓扑结构，可以得出LINSIA算法能够有效解析EAGLE示意网络的结论。?

    (5)离群点检测及社团隶属强度?

    LINSIA 除了检测社团结构外，还能够发现网络中的枢纽点和离群点。在图 2-9、2-10、2-11 中，LINSIA 发现的枢纽点如红色节点所示。对于枢纽节点，LINSIA

    还可以基于标记影响力度量这些节点对每个相关社团的隶属强度。 例如： 在图2-10

    (a)中，重叠节点 1，7，19 同时属于标记为 57 和 51 的两个社团，它们的隶属

    强度分别为[(57,0.746),? (51,?0.253)]，[(57,?0.501),? (51,?0.499)]，? [(57,? 0.5708),? (51,?

    0.429)]。对于重叠节点 1，其隶属强度表明其以 0.746 的强度隶属于标记为57 的社

    团，同时以 0.253 的强度隶属于标记为 51 的社团。?

    万方数据电子科技大学博士学位论文

    32?

    ·

    图 2-9? 基于 LINSIA 算法的美国政治博客网络结构分析?

    ·

    图 2-10?基于 LINSIA 算法的海豚种群网络结构分析。(a) EQ=0.3314,?C=2的重叠社

    团结构；(b) EQ=0.3301,?C=3的重叠社团结构?

    ·

    图 2-11? 基于 LINSIA 算法的EAGLE 示意网络结构分析。(a) EQ=0.3314,?C=2的重

    叠社团结构；(b) EQ=0.3301,?C=3的重叠社团结构?

    万方数据第二章 网络结构检测分析研究

    33?

    图 2-9、 图 2-10 的网络结构检测结果表明 LINSIA可以有效合理的发现网络中

    的离群点(绿色节点)。LINSIA能够检测离群点的主要原因是本文提出的标记更新?

    策略使得边缘节点有机会与核节点在标记传播更新过程中竞争。例如：在图 2-10

    (a)中，作为边缘节点的节点 60 首先进行标记更新，其选择节点32 的标记作为

    自己的新标记。然后节点 32 在综合比较了邻居节点的标记影响力之后成为重叠节

    点，从而使得节点60 得以保持其本地标记信息，而没有被来自网络核心区域的标

    记所淹没，最终使得节点 60 成为离群点。?

    综合以上分析，可以发现 LINSIA 算法相对于传统社团检测算法具有很多优

    点，包括适用于多种网络，能够发现多层次、多尺度的社团结构。同时，LINSIA

    算法具有鉴别网络中特殊节点的能力。有别于传统的面向单一结构特征的网络结

    构分析方法，LINSIA 算法对网络结构进行综合分析，再基于分析结果进行分类输

    出，从而能够综合地、有效地揭示网络的结构模式，这对于网络结构检测分析问

    题的发展具有重要意义。?

    ·

    图 2-12?算法运行时间综合比较。(a)、(b)、(c)、(d)分别为面向互斥社团、层次社团、重叠社团和层次重叠社团检测任务LINSIA 算法与相应基准算法的比较结果?

    2.3.5?算法运行时间比较?

    通过上节的实验分析，可以发现 LINSIA具有良好的网络结构分析检测能力。

    但是，实际应用不仅要求算法有效，同时也要求其效率较高、能够适用于较大规

    模的网络。为了评价 LINSIA算法的效率，按照不同的网络结构检测分析任务，本

    万方数据电子科技大学博士学位论文

    34?

    文将 LINSIA 算法与其它算法在真实网络上的运行时间进行对比，结果如图 2-12

    所示。实验结果表明 LINSIA算法慢于 LPA、NF、EAGLE算法，快于 Louvian和

    OCSBM 算法，与 NIBLPA算法速度相当。虽然 LINSIA算法在速度上没有明显优

    势，但综合 LINSIA 算法全面的网络结构分析能力，其与 NIBLPA算法接近的收敛

    速度也是比较合理的。?

    2.4?本章小结?

    网络结构检测分析是网络数据挖掘的一个重要问题，它对于理解网络结构、调

    控网络功能、制定进一步的网络数据挖掘方案都具有重要意义。关于网络结构的

    检测分析，虽然已经开展了较为广泛的研究，但是大部分已有的研究工作是基于

    网络的某一结构特征进行算法设计的，这与网络数据挖掘的实际应用需求不符。

    关于网络结构的整体检测分析问题，至今相关研究仍然较少。本文基于标记传播

    方法给出了网络结构整体检测分析的解决方案，实验结果表明本节提出的 LINSIA

    算法性能良好。当前研究与彻底解决网络结构的分析挖掘问题仍然相距甚远，需

    要进一步探索更准确、更高效的解决方案。?

    ·

    万方数据第三章 面向最优网络分裂的节点中心性研究

    35?

    第三章?面向最优网络分裂的节点中心性研究?

    由于网络功能与网络结构密切相关，网络结构只有保持完整连通的条件下才

    可能维持网络功能。同时，由于网络结构的异构性，网络中存在能够对网络结构

    和网络功能产生巨大影响的重要节点。检测和影响这些重要节点是进行网络结构

    优化以及网络功能调控的重要途径。特别地，由于网络系统的功能紧密依赖于网

    络结构的完整性，所以可以通过移除网络重要节点以分裂网络结构的方式破坏网

    络功能。现实生活中很多问题都要求破坏网络功能，例如：发现和破坏分子关联

    网络中的重要节点从而消灭细菌，免疫居民中的部分重要个体分裂传播网络从而

    实现疾病控制，消灭恐怖组织网络中的关键人物从而打击恐怖势力。鉴于节点重

    要性问题广泛的应用意义和重要价值，本文对节点中心性度量展开研究。?

    本章内容由四部分构成：首先，3.1 节介绍网络分裂问题的现实背景以及问题

    定义；其次，3.2 节阐述本文提出的基于本地网络结构的节点中心性ECI以及实验

    分析；再次，3.3 节阐述本文提出的结合物质传播和热传导过程的节点中心性

    PIRank以及实验分析；最后，3.4 节对本章内容进行小结。?

    3.1?网络最优分裂问题定义?

    在实际生活中， 功能被破坏或者失去活力的网络有时比功能良好的网络更有意

    义。同时，在网络化系统中，网络结构是网络功能的基础，网络功能依赖于网络

    结构的完整性。因此，网络结构的最大连通子图对于网络功能十分重要。由于真

    实网络的异构性，网络中常常存在一小部分节点，它们可能对网络结构完整性以

    及网络功能正常性有着十分不对称的影响力。可以通过发现和移除这一小部分节

    点可以进行网络攻击、将网络分裂成许多互不相连的结构碎片，减小网络最大连

    通子图的规模，从而达到摧毁网络功能的目的。特别的，网络最优分裂问题就是

    研究如何设计节点的中心性度量，并基于节点中心性度量发现网络关键节点，从

    而使得关键节点被移除后网络结构尽可能彻底的分裂，网络最大连通子图尽可能

    的小。由于网络最优分裂问题应用范围广泛，本文将面向网络结构最优分裂问题，在已有方法基础上研究节点重要性排序方法。?

    给定网络 ( , ) G V E ? ，其中 | | N V ? 个节点由 | | M E ? 条边相连。定义 q G 为基于 ......