课程信息
参考用书
1、Networks Crowds and Markets: Reasoning about a Highly Connected World David Easley and Jon Kleinberg 2010年 Cambridge University Press
课程教师信息
课程首席教授郑晓龙研究员，在社会计算、知识图谱和大数据解析学的基础理论研究、关键技术研发和系统平台建设等方面系取得了丰富的研究成果。
概念
- 强弱关系：紧密频繁或偶然
- 结构洞
- 嵌入性：在四边形ABCD中连接AC，反映了AC之间关系的可靠性
- 桥：AB间的唯一路径 -> 捷径：去除AB连边会让他们距离增加2以上
- 社会资本：人们在社会（社会网络）结构中所处的位置给他们带来的资源
- 契结资本：强连接，表达性行动，情感
- 工具资本：弱连接，工具性
- 正关系和负关系
- 结构平衡（三者皆是敌人导致敌人的敌人仍是敌人）
- 网络影响力：依赖性，排他性，饱和性，介数
- 核心-外围结构
- 网络社区发现：节点要求，集合要求，互不重叠，层次化社区结构，如何提取隐藏的社区结构
- 激活扩散理论 ：一个概念被激活，其效应可以扩散到与其相关联的其他节点，NLP相关
- 注意力网络：近因，首因，边际递减效应
- 流行语传播网络：信息模因（Meme）
- 信息在人群中传播就像基因一样，会不断复制和演化
- 基于网络的群体情感行为演化
- 网络中的同质现象：由节点主动选择（选择相似特征【或自己所喜欢的特征？】的朋友）和被动影响（成朋友之后的影响）交错而成
- 从众行为：信息效应，直接受益效应
- 信息效应：根据有限的信息进行合理推理，和模仿顺从不同，“信息级联”
- 理性状态下的认知失衡
- 社会影响：行为，态度，信念
- 影响力对抗网络
- 大脑不擅长概率问题，擅长因果问题
Ideas
- 动态网络
- 现有社交网络（推特、微博等数据集）中缺乏负关系（对抗敌对）的挖掘与应用
- 无向图中负号偶数是平衡，有向图中负号奇数是有效调节
- 同质性，“圈层”
- 激活扩散中，概念如何更高效准确的储存和调用（进化？）
- 因果就是 贝叶斯+神经网络
- 如果用BERT对学习出句子的向量化表达，再取平均可以当作帖子的向量化表达，然后求余弦相似度，设置阈值进行连边，再把极大连通分量找出来，可以找出对哪些话题经过了大量重复的激烈讨论，我还有个不成熟的idea，这个结合上发帖时间是不是可能用来挖掘“水军”的重复发帖。
课程研讨记录
- 因果涌现
- 有符号网络 级联传播 对抗
- 图同构 图的相似性
- 研究尺度的分离 宏观系统和微观个体
- 金融耦合
- 长文本匹配
- 预测 就是 低维到高维 是高维空间的点（时间当作新维度） 那点之间的边是什么 是不是更高维的点 低维线到高维点
- 因果+推荐系统
- 金融投资组合 最小生成树
- 灾和害是两个概念
- 临界值 涌现
- 图数据库neoGJ
- 基于特定任务的复杂网络
- 语言是线性的，但是想法是非线性的
我的研讨草稿
我们小组目前在做的方向是舆情分析和社会复杂系统分析，我们平时用到复杂网络的地方就相当的多。大家上了这么多堂课，学了这么多理论概念，我正好就来给大家介绍一点这些理论的基础应用工作。就比如一个舆情事件，我们怎么分析它的发展脉络，就以之前热度很高的红十字会有关一系列事件，首先肯定是获取元数据，根据关键词抓取一些新闻报道，微博帖子，知乎回答之类，这些基本都是一些文本形式，我们可以先用nlp的技术做个切词，再用一些textrank tfidf之类的方法提取每个帖子前几的关键词，那么第一，我们就可以构建出一个关键词网络，关键词作为节点，在帖子中的共现关系做边，共现频率当权重，就有第一个关键词共现网络，我们可以根据这个网络做一个louvain算法社区划分，再分析几个社区的最大中心性的节点，比如第一个社区，最大中心性的是捐款，第二个社区呢，最大中心性的是学校，孩子之类的，就把这一系列事件分成了两大主要组别。我们还可以用帖子做节点，共享关键词做连边，我们可以根据介数中心性啊，pagerank啊，度啊最大的几个节点，也就是帖子挖掘出来，这就可以揭示这一系列相关舆情事件的主要内容。还可以对这个网络找割点，比如一个帖子“中国红会为何否认郭美美事件”是割点，那比如它左边的是郭美美，红监会之类的事件，右边是地震，捐款之类的帖子，就可以看到不同舆情子事件中的关联。如果用BERT对学习出句子的向量化表达，再取平均可以当作帖子的向量化表达，然后求余弦相似度，设置阈值进行连边，再把极大连通分量找出来，可以找出对哪些话题经过了大量重复的激烈讨论，我还有个不成熟的idea，这个结合上发帖时间是不是可能用来挖掘“水军”的重复发帖。那如果是微博的帖子，还有很多回复现象，对回复文本做情感分析，得到情感极性1，-1，0，有了这些，又可以构造出一个有符号的回复网络，边代表回复关系，符号就是情感极性，然后就可以做统计啊，研究互动关系啊，互动持续时间分布之类的。就是总之复杂网络其实是一个相当有意义的学科，学的每一个概念，可能都会发挥很重要的作用。
复杂系统研究综述
复杂系统的历史发展
复杂系统，研讨的是系统复杂行为背后体现出来的普遍原则。由于系统中大量组元之间存在着非线性互动，复杂的交互之下，整体行为，会和个体成分的行为形成明显的反差。系统通常无法被精确预测，不会呈现出易于研究的平衡态，既有着很高维的信息编码，又会持续进化、学习和适应。这些特点造成了复杂系统难以被研究。张嗣瀛也总结出了复杂系统的五个基本特征：构成元素复杂，影响因素复杂，相互作用复杂，系统行为复杂，预期结果复杂。
钱学森从系统科学的角度对复杂系统开展研究，他对复杂系统下的描述性定义是：复杂系统是由相互作用相互依赖的若干组成成分结合而成的具有特定功能的有机整体。他提出了复杂巨系统的概念，并发展为钱学森、于景元、戴汝为等提出“开放的复杂巨系统”和“定性与定量相结合的综合集成法”。复杂系统的发展历程，可以总结为四个阶段：从系统科学和系统论思想的提出，到自组织理论和非线性科学理论，形成了复杂系统建模与人工仿真系统的研究。后续发展为复杂网络理论方法和网络动力学理论，到现在，正涌现出许多行为+结构+动力学的系统科学新范式。
复杂系统的基本特征
复杂系统包括自组织性、涌现性、不确定性和开放性等重要特征：
（1）复杂系统具有自组织性的特性，构成系统的组成成分本身就可以自适应和学习，而这些组成部分之间，个体和环境之间，又可以发生复杂的交互，并在交互的过程中调整结构，优化连接，体现出更复杂的自组织和自适应性行为。
（2）在复杂系统自组织过程中，会不断产生新颖而连贯的结构、模式和性质，而后催生出偶然的、突发的、持续的、根本性的变化，这就是复杂系统的涌现性质，涌现进一步加深了系统的复杂度，体现出了从个体到整体、从组件到整个系统过程中的质变。如果只观察组件而忽略了整个系统的交互，就无法研究涌现出的新特性。
（3）复杂系统中总有许多随机因素，造就出了系统的不确定性，影响系统的状态和系统组件间的结构。
（4）复杂系统包括系统中的组件总会与外界有信息、物质和能量的交换，这些交换使得系统所处的外在环境对系统有着很大的影响，体现了系统的开放性。
复杂系统的研究
以复杂系统与不确定性为例，复杂系统由于要素过多，并不能总是被很好的纳入研究，从而造成了预期结果的巨大偏差，这就造成了复杂系统的不确定性。
很多情况下不确定性会使复杂系统变弱，但是对于进化过程，却是有益处的，以不确定的基因突变为例，造就出了生物圈这个复杂系统的多样性和完备性，利用这些进化机制，系统的变化和交互合理的情况下，反而会对整个系统有益。市场经济的蓬勃发展就是复杂系统不确定性的一个典型例子，人为设计总有考虑不周的地方，关键在于让这些不确定性得到的结果是有利或者说至少无害的，经常需要放弃控制或者合理的引导，使得系统自由的发展，复杂度自然增长。
在系统的进化过程中，个体之间除了竞争，还有合作关系，而这两种关系往往都是基于多尺度范畴的，大的尺度下，例如国家的竞争，往往孕育出了小尺度之下的合作，如国家之内的统一团结。这些大小尺度的竞争合作竞争过程可以不断延展下去，自然发展演变。基于此可以进行合理的合作竞争结构设计，借助多尺度下的进化过程，促进整个团队的良好发展。
复杂网络研究综述
复杂网络的历史发展
复杂网络的研究可以从欧拉提出的“七桥问题”开始追溯，钱学森认为复杂网络具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质。在研究复杂网络时, 我们会关注点与点之间的连边关系, 而忽视点的位置等因素。复杂网络的建模就是研究复杂系统的一种重要手段和方法，通过点和边来描绘复杂系统中的个体以及个体之间的相互联系与交互，复杂系统有进化性，复杂网络也可以模拟出点与连边之间的演化关系。复杂网络与图论和拓扑学有着密不可分的联系，可以运用图上的工具和算法，来对网络进行分析，从而得到复杂网络上的一些性质，从而映射出复杂系统层面上的一些性质。
复杂网络的基本特征
复杂网络上有一些基本的、基于图上性质的静态统计特征，分析这些特征有利于对网络的结构进行基本的了解和可视化分析：
（1）平均路径长度
复杂网络中节点之间的距离定义的是是连接两点的最短路径的边数（如何找最短路径也是一项很重要的工作）。在距离定义的基础上，网络的平均路径长度就是网络中所有节点对的平均距离，这可以反映了复杂网络的节点之间是联系紧密的，还是联系稀疏的。
（2）介数
介数包括节点上的介数与边上的介数。在上条性质的基础上，一个节点的介数指复杂网络中有多少比例的最短路径中经过该节点，相应的边介数就是复杂网络中有多少比例的最短路径中经过该条边。介数作为一个重要指标体现出了节点或者边在复杂网络中的重要程度，形象的说，描绘了节点或者边承担“中间人”角色的比例。
（3）节点的度
作为最直观的一个统计特征，节点的度就是复杂网络中与该节点相连的其他节点的总数，对网络中所有节点的度做平均，可以得到整个网络的平均度。更进一步，还可以求出所有节点度的概率分布式，进一步体现出网络的结构特性。
（4）聚集系数
对于一个节点与其相邻的所有节点，当他们连成完全图的时候，可以看作聚集程度最高的情形。相应的，节点的聚集系数就是当前连边占完全图情形连边的比例，可以反映出网络的局部特征是什么样的。
这些统计特征虽然基础，但在实际应用中却可以反应出一个真实复杂系统很多重要的特性，进一步，或许还可以研究分析这些特征之间的关联性，联合分布等，得到一些新的深层次特征，再结合实际进行进一步的研讨分析。
复杂网络还有很多经典的模型构造，这些模型理论提出来的目的是更好的研究真实世界的复杂网络和复杂系统。
（1）小世界模型
如果一个网络的规模很大，即它的节点数目很多，但是节点之间的距离却很小，那么这个复杂的网络其实就可以看作拥有小世界效应。现实世界中很多复杂系统都具有小世界效应，比如关于地球上人和人之间只需要七个以下中介人就可以联系在一起的著名研究。
–基于这个特性，通过以小概率切断随机网络中连边，并随即进行重连的手法，构造出了WS网络。在他们的基础上，Newman 和 Watts 进行了改进, 把WS网络的随机重连边改成了不切断原有连边，但以一种更小的概率直接随机增加连边，从而得到了NW模型。他们都是小世界网络模型，是一种对现实世界复杂网络的模拟。
（2）无标度网络
相对于小世界网络中节点的度分布是近似泊松分布的，大多数真实复杂网络的度分布近似服从幂律分布，这就造成了误差。类似于现实世界的二八定律，在度分布服从幂率分布的复杂网络中，大多数节点有着少量连接,少数节点有着大量连接。基于此，Barabas 和 Albert做了假设：新增加的节点会优先连接原本度就较大的节点，最后就模拟出了服从幂律分布的无标度网络。
复杂网络的研究
（1）社区划分研究
在现实社会复杂网络中，人们会处于不同的团体，团体之类连接会更加紧密和频繁。抽象到复杂网络体系，就是一个个的社区结构，这也是复杂网络中很重要且有很大研究意义的特征。研究这些社区，也有不同的标准，既可以根据连通密度进行社区区分，又可以根据连通性来划分出来类似于“派系”的结构。与图论中的划分有所区别，不同的社区之间通常可以相互重叠或嵌套，社区发现的主要目的是探究复杂网络自身隐藏的的自然划分，从而更好的现实世界复杂网络的性质。
社区划分算法的发展：
Girvan和Newman在2002年的研究工作中率先研究了网络的社区发现，他们开始把社区结构纳入网络的拓扑结构，提出了一种基于边介数运用分裂式层次聚类算法的划分方法。最初的社区划分算法都是采用类似的自顶向下或者自底向上的层次聚类算法进行刻画。作为开创性工作，相应的也遇到了如何度量划分的好坏问题。
为了进行这种度量，Newman和Girvan提出了模块度理论，该理论假设随机网络没有社区结构。把社区划分的目标设立在优化模化度，得到的社区的所有边的权重尽可能的比随机参照网络相应的边权重之和更高。基于这个提出的模块度作为目标函数，很多优化理论和算法如模拟退火、禁忌搜索等等经典算法被应用到社区发现领域。
模块度理论指明了社区划分优化的方向，也被指出存在许多问题：
基于模块度优化出的社区划分限制了社区结构只存在一种尺度，这与现实网络的社区结构存在差距。有两种主要的方法解决这种多尺度问题：通过在每个节点上加上自循环；或者在模块度的公式定义上加上一个参数，从而得到多种尺度的社区。
由于模块度的公式依赖于边权重占网络所有边的总权重的比例问题。优化模块度的算法会显著限制很多小社区的发现。解决这个问题的思路是加入在局部定义的模块度属性。
除了模块度理论，还可以根据相应矩阵的特征向量来度量节点间的相似程度，邻接矩阵的谱可以揭示网络的社区结构被Chauhan等学者指出。基于此衍生出了许多社区划分的谱方法。
由于真实世界往往存在不同群体之间存在交集的情形，对应到复杂网络，就会出现社区的重叠情况。Palla提出了用于重叠社区发现的CPM方法，主要思路是基于对社区内部的边和社区之间的边进行区分，并且允许社区之间的重叠。
评价这些社区划分算法，一方面需要对时间复杂度进行评估，另一方面可以通过与现实复杂网络已知的社区进行匹配，用匹配程度来进行度量社区划分的可信度。
（2）信息传播
由于互联网的兴起，在线网络得到了比线下网络更高的关注度，也有着更复杂的信息传播效应。典型的研究信息传播的模型是通过模拟的方式进行的，采用传染病模型中的研究方法，如SI,SIR等模型。除此之外，现在更多的是对信息级联机制进行研究。也就是假设，许多人会以一种连续的方式做出相同的决策，这与现实世界的行为相匹配。
复杂网络方法与舆情分析领域
舆情分析实际上就是对在线舆情网络的具体研究，因此复杂网络的方法可以很自然的运用到舆情分析领域。
对于一个具体的舆情事件，可以构造出多种类型的复杂网络，借助这些网络结构，可以理清这些事件的发展脉络，以单主题舆情分析为例，例如红十字会相关事件的舆情分析，首先根据关键词抓取一些新闻报道，微博帖子，知乎回答，用自然语言处理的技术做中文切词，再利用textrank和tfidf等方法提取每个帖子靠前的几个关键词。
（1）首先可以构建出一个关键词网络，以关键词作为节点，关键词在帖子中的共现关系为边，帖子之间关键词的共现频率作为权重，可以得到一个关键词共现网络，利用复杂网络中的社区划分算法在这个关键词共线网络上做一个社区划分，再分析几个社区的最大中心性的节点，比如第一个社区，最大中心性的是关键词”捐款“，第二个社区最大中心性的是关键词”学校“。可以识别出来这一系列舆情事件的两大主要组别与含义。
（2）反过来，用帖子做节点，共享关键词做连边，可以得到发帖共词网络。可以分别根据介数中心性，pagerank值，节点的度等指标选出最关键的几个节点，也就是把相应的重点帖子挖掘出来，就可以揭示这一系列相关舆情事件的主要内容。再对这个舆情网络找割点，例如找到一个帖子“中国红会为何否认郭美美事件”是网络的割点，该点左边的是郭美美，红监会等主题的帖子，右边是地震，捐款等主题的帖子，就可以反映出不同舆情子事件中的关联。
（3）利用BERT模型学习出句子的向量化表达，再取平均可以当作帖子的向量化表达，然后求帖子向量之间的余弦相似度，设置阈值进行连边，就得到了一个语义相似性网络。再把极大连通分量找出来，可以找出对哪些话题经过了大量重复的激烈讨论，笔者还有个不成熟的idea，结合上发帖时间和这些语义相近的极大连通分量，可以用来挖掘“水军”的大量重复发帖行为。
（4）部分帖子之间还存在回复现象，对回复文本做情感分析，得到情感极性值用1，-1，0表示，可以根据情感值构造出一个有符号的回复网络，边代表回复关系，符号为情感极性，就可以做情感统计分析，研究互动关系，互动持续时间分布等有重要实际意义的特征。对舆情演化的研究有重大参考价值。
复杂系统与复杂网络的拓展思考
在有关复杂系统的研究中，数据收集是最底层也是最关键的工作。一个重要的问题是，如果我们有一部分数据获取不到，获取的数据部分虚假，或者考虑的不够全面遗漏了一部分数据，现有方法如何保证结果的鲁棒性。在现实世界复杂系统问题研究中，没有办法以上帝视角去看待问题，实际上常常会面临数据的缺失和考虑不足的情形，而这些遗漏经常导致得到的结果天差地别。这些微观的细节数据是得不到全盘考虑的，可不可以在整个系统的层面考虑模型，得到一些不受细节数据影响的系统层面的结构分析成果，或者利用已有的数据做缺失数据扩充处理？
另一方面，很多应用层面的复杂系统分析只能得到实证结果，缺乏对实证结果的验证评价，利用类似于生成对抗网络的思想，在大量复杂系统（复杂网络）的结果的基础上，是不是也可以用另一套模型（复杂系统）去分析，建立源系统上的评价系统。
参考文献
[1] 钱学森, 于景元, and 戴汝为. “一个科学新领域——开放的复杂巨系统及其方法论.” 自然杂志 1 (1990): 3-10.
[2] Siegenfeld, Alexander F., and Yaneer Bar-Yam. “An introduction to complex systems science and its applications.” Complexity 2020 (2020).
[3] Watts, Duncan J., and Steven H. Strogatz. “Collective dynamics of ‘small-world’networks.” nature 393.6684 (1998): 440-442.
[4] Newman, M., and A. Barabasi. “L.; WATTS, D.” The structure and dynamics of networks.
[5] Barabási, Albert-László, Réka Albert, and Hawoong Jeong. “Mean-field theory for scale-free random networks.” Physica A: Statistical Mechanics and its Applications 272.1-2 (1999): 173-187.
[6] Boccaletti, Stefano, et al. “Complex networks: Structure and dynamics.” Physics reports 424.4-5 (2006): 175-308.
[7] Newman, Mark EJ, and Michelle Girvan. “Finding and evaluating community structure in networks.” Physical review E 69.2 (2004): 026113.
[8] Chauhan, Sanjeev, Michelle Girvan, and Edward Ott. “Spectral properties of networks with community structure.” Physical Review E 80.5 (2009): 056114.
[9] Palla, Gergely, et al. “Uncovering the overlapping community structure of complex networks in nature and society.” nature 435.7043 (2005): 814-818.
[10] 张亚茹, and 唐锡晋. “天涯杂谈 “红会贴” 热点事件分析.” 系统科学与数学 40.10 (2020): 1723-1736.
