用复杂对抗复杂群分享实录下（内含精彩项目征集）
如果你感兴趣本篇文章，并且想自己做一件一样酷的事情， 请你举手联系铁哥（562763765）， 巡洋舰此次分享的目的是带领大家做一个极为有趣的类似项目， 学习机器学习， 自然语言处理和复杂网络的一些相关技术。 请看末尾。
上一次铁哥讲了复杂系统的几个基础概念，包括分形，相变，临界。研究复杂系统离不开复杂网络，而令你意想不到的是， 我们的流行文化居然和复杂网络息息相关。请看今天分享的主角–一篇论文。
大家都看过harry potter 或者twilight吧。你看的时候头脑中一定不会出现这些图。如果我要你画一张小说人物关系的脉络图， 而且我要你写一个程序搞， 你会怎么搞？事实上，我们可以用分析复杂网络的方法分析一部小说， 对， 就是这么神奇。
这个链接是一个更酷的关于7部星球大战的人物关系网络的可视化
http://assets.dtcj.com/visualization/star_war/index.html
接着来说这篇论文，题目是“Mining and modeling character networks”，也就是上面的图的出处。如果要机器来学习小说中人与人的关系， 核心方法就是挖掘对话中两个人物共同出现的频率我们可以做一个简单规定， 就是一个人物出现时候， 其前15个字和后15个字之内如果出现另一个人物， 那么就算这两个人同时出现。我们统计任意两个人物同时出现的频率，并把这些频率放入到一个巨大的表格里， 这时候我们会得到一个描述人物关系的矩阵。
这个矩阵的含义大家觉得是什么？提一下英文名就是adjacent matrix。在现实世界里，这个矩阵如果过大，就需要用mapreduce 来做奇异值分解。然后我们需要用一定的数学方法从矩阵把人物关系网络求出来。
要从矩阵到网络， 我们第一个要解决的问题是什么？我们首先要确立网络的中心。处于网络中心的是什么？ 是小说的核心- 主角。那么如果我们把一部小说想象成描述一个江湖。那么这些人物如同构成了一个社会网络。这个网络里最重要的人，从网络的角度看吗， 需要有哪些特征呢？首先我们可以思考是那些具有联系最多的人（和一个人直接发生的联系的个体数即复杂网络节点的度）。但是大家想一下这个方法有没有缺陷呢？ 肯定有的，如果一个看门大爷具有公司所有人的联系， 他对群体的影响力却不是很大。
此处注意我们研究一个问题要明确每个概念， 比如重要性， 什么是重要？谁对你最重要， 就是谁对你影响力最大。 重要性就是影响力。 而其影响力只能从外界和它的联系看出： 1，和他联系的有多少重量级人物 2， 和这些人互动的频率是多少？ 是不是看门老大爷的水平？ 3 ，积分， 总量是重要的。 那么单看节点的度就是不够的， 有没有别的方法？ 其他领域有无借鉴？ 可以参考pagerank算法教会我们的事。
总结一下就是要看两点， 一个是权重， 即每个连接所发生的频率， 如果看门大爷偶尔和领导说一句话， 那么它的权重几乎是0， 就可以排除掉。 另一个是这些连接本身的重要性， 如果你只有三个连接， 他们一个是习近平， 一个是李克强，一个是xx， 那就知道你的位置了。ok 这个问题很早就被google的创始人larry page 解决掉了 ， 这个算法就是大名鼎鼎的pagerank。pagerank算法是如何运算的 ， 原理并不难理解。
我们还想象网站的情形， 首先你假定你是一只猴子， 随机的进入了网站构成的巨大网络，然后我们做一个最基本的假设，那就是你可以从一个网站跳到与之相邻的网站， 这个跳跃的概率等于1除以从这个网络节点的度（因为你必须做一个选择下一步去哪里， 如果你有n个选择， 那个每个选择被选中的概率是1比n）。 你让猴子跳跃很多次，不停迭代n步之后， 你最终将得到一个你进入每一个站点的概率分布， 那个你在随机跳动里最容易进入的点， 就是网络的中心。 用数学上表示， 就是你跃迁矩阵那个对应特征值为1的特征根。
最简单的方法是从三个网站相连的示意图开始计算。我们一开始看到这个图完全不知道ABC三个方框里面的数字， 所以我们就假设各自数字为三分之一。权重是方框里的数字除以从这个方框出去的边的个数。这个得出的对应某条边的数字可以理解为从一个网站点击开另一个网站的概率。
在某个网站上的数字大， 则说明这个网站本身比较重要， 点击人数比较多，因此从这个网站出去打开其他网站的概率也较大。用这个方法可以得到在计算中心度的时候充分考虑到一个节点周围节点的重要性， 因为它衡量了整个网络对某个节点的影响而非只考虑直接相连的那些点，如果一个节点周围的点都不太有流量， 则及时与该节点相连的边数很高， 也较难有足够流量。
pagerank的算法的厉害之处在于通过不停迭代一次求出所有网站的重要性 或者从复杂网络的语言说， 就是取得了每个节点的中心度。我们之后可以按照这些中心度给所有网络节点排序。
从上面的图可以看出，相比之前用度进行的排序， 用pagerank算法进行的排序能够更加清晰的区分哈利波特中主角和配角。但对于权力的游戏，由于这本小说本身的特性，区别并不明显。
在这篇论文里， 我们还比较了其他关于中心度计算的方法。计算中心度是得到复杂网络的核心一步， 因为我们画图的时候需要把中心度最高的那个人物画在中央， 而中心度次高的画在他旁边的位置 ，这样依次向外。
我们之后需要根据已知复杂网络的知识， 来判断所生成的网络属于何种类型。文中用到了机器学习的分类器来判定这个问题。此处我们给出了几种标准的复杂网络， 然后判断从小说生成的人物网络最符合哪一类标准网络。
第一类网络是preferential attachment**（PA）。**说的是具体生成网络过程中，我们一条一条边的往上加。假设一开始我们有n个节点， 然后我们要再增加第n+1个节点， 这时候我们自然要再从其他节点抽出m条边与之相连，这个抽取的概率与前述节点的度成正比。
你要计算新增加的节点是否需要与某个之前节点相连，你就要看一下之前节点是否有很多条边， 边数越多， 这个连接的概率越大。这就是瑞东刚说的马太效应，富者越富，贫者越贫。这种网络是由它的生成过程定义的。在生成过程中充分考虑到已有的节点和边数（度）对网络构建的影响。
第二种已知网络类型是The Binomial Random Graph G(n, p), or Erd ̋os -R ́enyi (ER) 这是给定整个网络的平均度数， 然后在任意两个节点之间按照这个度数决定的概率随机抽取， 决定是否把这两个点连接在一起。 这种方法生成的随机网络叫做Binomial Random Graph，又叫ER graph。
第三种方法， Chung-Lu model。(CL) 这种网络模型充分考虑了我们之前生成的小说人物网络的结构 ， 所谓在已知给定两个节点间连线的概率，正比于这两个节点的度的乘积。也就是说， 这个模型最大的利用了我们之前已知小说网络的信息。
第四种模型是CFG model, we select a graph uniformly from the set of graphs which exactly match the target degree distribution. 即按照文章中的节点分布生成符合条件的随机网络，假设网络中只要3个节点，我们要考察的小说中有三个角色，哈利，罗恩和赫敏。其度分布为100 80 75，我们需要生成一个具有相同节点的度分布的网络。
我们之后的任务是判定我们所生成的小说人物的网络拓扑结构， 最符合刚刚说的哪一类网络？如果你想到机器学习里的分类器 ， 那就对了。但是SVM是要提取数据特征的额。此处如何提取数据的特征呢？
看懂这张图， 就弄明白了我们提取整个网络特征的方法。因为你要判断一个复杂网络属于哪一类给定的复杂网络类型。这里复杂网络的一个很重大的特征是motif。你可以从一个大的网络里，给定节点个数， 抽取所有小的子网络。比如上图， 你从大的网络里抽取所有三个节点的图出来， 然后三个节点间只有可能有四种连线方法，(假定节点是相同的)，我们可以统计所有三节点图里四种连线方法所占的比例。用同样的方法我们可以处理4节点图， 5节点图，得到一个巨大的关于连线方法的统计分布。
当然这里可用到的分类器有support vector machine， random forest， 和boosted decision tree。因为我们也不知道这些特征哪些比较重要， 哪些不太重要， 用随机森林是一个很好的对各个特征影响进行综合的方法。
最后三种分类方法得到了一个比较一致的答案， 那就是我刚讲到的第三种复杂网络模型（Chung-LU）最好的描述了小说人物的网络。
可以看到三种方法取得一致意见，而且是压倒性的。得分越高，分类器认为这些横轴的模型更像待 检验的模型，即通过文本分析生成的网络。纵坐标 可以理解为 不同模型分类效果的得分。分值越高匹配度越高。得分越高，分类器认为这些横轴的模型更像待 检验的模型，即通过文本分析生成的网络。这里提到这个数字是similar aggreate results for 800 character。
这里是取了 800个 电影剧本， 纵轴的数字代表横轴的模型被分到同一类的次数。具体是 five fold cross validation，就是抽20%的验证。此处的训练是用100个随机生成的上述四类中每一类复杂网络， 给分类器进行训练。拿剩下的80%训练。通过训练之后， 再把从小说提取的人物网络经过分类器试验。
这篇文章其实已经涉及了一些自然语言处理的知识， 比如一开始的人物名字频率的分析计算， 如何猜测每个代词指代的人物等， 我们接下来进入自然语言处理部分。
自然语言处理是数据科学的一个分之，既然是科学，就应该遵守科学所需遵守的规矩。科学永远是来源于好奇的，我个人是哈利波特的死忠粉，看完数后会有很多问题。比如谁是书中的第二主角，是罗恩还是赫敏。要回答这个问题，我们需要数据。
**好的科学，就是提出问题，找出如何观察计量数据，之后将数据展示出来。**另外一点就是要keep your mind wide open,保持不确定的状态，接受新鲜的事物。
回到刚才的问题，最简单的方法是统计 罗恩 和 赫敏这两个名字在书中出现的次数。这个问题牵扯到自然语言处理中会遇到的某些核心困难。比如一个词语在不同的语境下有着不同的含义。传统的自然语言处理 是基于规则的。有学语言学的朋友， 应该知道乔姆斯基范式。一个句子可以分为主语开始，接一个动词，再接一个宾语。将英文的句子按照词性以及这样的规则，展开成一颗树的过程，就是传统的分词算法。下图是提到的分词树。
近年来，随着计算性能的提升，另一种不利用语言特性的基于概率的自然语言处理开始表现出比rule base的方法更好的效果。基于概率的方法，被广泛的应用到机器翻译，搜索引擎优化中。这里推荐感兴趣的同学去看吴军的《数学之美》，其中有很多精彩的介绍。
总结：本次分享的意义， 在于告诉大家我们可以用机器学习和复杂系统的方法去研究一些我们现实生活中的现象， 比如我们在看看的影视作品。有一些公司甚至可以利用这点开发商业产品， 比如一些制造电影电视剧的公司， 可以根据整个人物关系网络和观众喜好度的关系制定策略开发影视产品，也可以做社交网络的研究，例如去看人人网是怎么衰落的，前期后期有什么不同。
感谢 Salome 同学提供的记录。
巡洋舰项目征集：此次巡洋舰希望带领大家完成一个与此篇论文一致的项目。 我们将让大家挑选一部喜闻乐见的小说，有中英文对照的， 然后大家可以亲手用论文中的技术制作你心爱小说的人物网络，用机器学习的思想理清那错综复杂的关系！ 同学将被分为A组和B组， 分别对小说的中文版和英文版加以分析， 最终对两个版本汇总出的人物网络加以比较。
本项目要求加入者具有一定编程基础，名额极为有限，感兴趣的请直接联系铁哥（微信562763765）。
更多阅读