网络动态性(Network Dynamics)

最近看相关文章的一个小总结

网络动态性研究，是观察网络的各种特征在不同时间上的变化情况，或是利用来自不同时间的数据来获得在单一时间内难以得到的信息。这里“网络”和“图 ”指的是同一个东西，即由节点和连接节点的边组成的结构。这些研究主要来自于物理学和社会学两个研究方向，物理学关注的是抽象网络的各种性质，而社会学更 关注社区发现和演化等与社交网络有关的内容。一些工作是实证性质的，即对来自某个具体网络的数据进行详细的统计和分析；另外一些是建模和算法性质的，提出 一些模型或是方法来解释或解决问题，并且在真实或是模拟的数据上进行检验。

在2005年之前，被关注的特征主要是网络的一些全局统计量，例如平均出入度和平均最短路径。通过考察这些统计量随时间变化的情况，研究者得到了一 些有意义的结论。例如真实世界的网络比较稳定，这得益于其层次性的结构，即大的网络是由很多小的趋于稳定的网络按照层次组织起来的[1]。另外一个和直观 相悖的结论是随着图节点数的增加：1）平均的度在增加而不是常数，2）节点之间的平均距离在减小，而不是缓慢增加[2]，这是不是类似于六度空间现象？

2005年之后，一些研究者开始关注网络的结构随时间变化的情况，而不只是看全局的统计量，其中关注最多的是社区的动态性质。一般的思路是先把数据 按照滑动时间窗口组织成时间上连续的多个图，然后用比较成熟的社区发现方法，例如基于edge betweenness的方法，来发现每个图中的社区，最后利用社区之间的相似性度量和时间连续性假设（即社区变化还是需要时间的，不会突然消失掉）来分 析社区的出现、增长、合并、分裂、缩小和消失等现象。其中社区发现、子图相似性的度量等等可能使用各种不同的方法，但是总体上是差不多的。这些分析得到了 比全局统计量更有趣的结论，例如有分析指出大的社区如果组成的单位经常变化，则社区的活力会长一些；小社区则恰恰相反，组成单位的变化会加速其消亡 [3]。做个直观的解释：大社区如解放军，“铁打的营盘流水的兵”，大家不是靠个人关系聚集的，而是靠严格的纪律和共同的目标，这样的社区要比靠脸熟形成 的社区，如梁山泊一百单八将，要稳定的多；小社区如宿舍好友打牌四人组，任何人员上的变动都会让这个组织迅速的消失，因为脸熟是维系这个小社区的关键力 量。另外有人提出来研究的单位可以比单独的节点或是边来得更大，先找到不同时间点上的所有子图，再根据时间上的连续性把不同时间上的相似子图（往往就是相 同的，例如01年的中国足球队和02年的中国足球队，例子是我举的）串起来形成元子图(meta group)，转而研究元子图之间的关系[4]。

社区发现，或叫做层次分割，或叫做层次聚类，是探索大规模网络内部结构的必由之路。另外一些研究就关注于如何利用动态性也就是时间信息来辅助社区发 现，或是让社区发现的算法能更好地应对高度动态的数据。来自物理学的研究者善于用物理现象来类比解决社区发现的问题。一个方法是把网络中的每个节点都想像 成相振荡器(phase oscillator，例如单摆就是一个简单的振荡器)，把节点之间的边想像为连接振荡器的物体，那么根据我们高中学过的多个不同频率的单摆在连接在一起 的时候会发生同步这一物理规律，我们可以想像网络中相近的节点震荡频率会趋于一致，而没什么关系的节点之间震荡频率会有区别，通过考察稳定后节点震荡频率 的不同，就能把网络划分成不同的社区[5]。这个方法可以看作是用一个动态的模拟来发现网络的结构。另外一个类似思路的方法是把每个节点想像成一个小球， 把节点之间的边想像成弹簧，那么这一团由弹簧连接的小球在稳定不动后就会自然地形成不同社区在一起的结构[6]。之前在用cytoscape这个网络数据 查看软件的时候，就有Spring Layout这种观看模式，和这个思路应该是一样的。这种弹簧模型还有一个好处，就是如果有一个新的节点或是边到来，不用重新计算所有的数据，只要让加入 了新节点的一团弹簧再动动，稳定之后就是新的结果。也就是说这种方法能够应对动态变化的数据，而传统的基于edge betweeness的方法则需要每次都重新计算所有数据，不能适应动态数据分析的要求。

对于在网络上的意见传播，还有一类以Opinion Changing Rate(OCR)模型为代表的模型[7]，来模拟在每个节点接受新事物能力有不同的情况下，一个意见能不能在整个网络上达成一致和这个过程需要多长的时间，这很偏向于社会学的研究。

值得一提的是数学家在很早之前就对时间相关的随机现象有了很多的研究，一般被称作时间序列分析，在这个领域内时间序列数据被看作是随机过程的一个实 现，大量随机过程的工具被用于这方面的研究。时间序列分析最初可能主要是由经济学研究驱动的，这方面了解不深。从实际的论文和方法来看，把相关数学工具用 于网络动态性研究的非常少，可能也与对数学知识要求过高有关。

话题转回语言分析，看看网络动态性研究能为语言分析提供怎样的帮助。首先语言中网络无处不在，从字、词的搭配网络，到词语之间的相关性网络，不一而 足。语言的变化虽然不及人际关系的变化快（世态炎凉人心难测），但也是在积极地演进着。例如对从小学到高三的语文课本内容的词搭配进行分析，也许可以看到 不同教育时期语文重点的变化，进而考察出这些重点和这种变化是不是清晰正确地反应了教学的需求。再例如对有准确时间标签的新闻或博客文章中的用词搭配进行 分析，也许能发现不同时期不同事件在话题上影响的变迁，或是新词汇的产生，或是旧词新意的分离或消亡（例如“小姐[年轻女性或妓女]”和“分配[分发或是 安排工作]”）。又例如对不同时代古诗中字的关系进行分析，是不是能看到诗词用语的演化规律？

[1] EA Variano, JH McCoy, H Lipson, networks dynamics and modularity, Physical Review Letters, 2004
[2] J. Leskovec, J. Kleinberg and C. Faloutsos, Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, In Proc. of KDD’05, 2005
[3] G Palla, AL Barabasi, T Vicsek, Quantifying social group evolution, Nature 446, 664 - 667 (05 Apr 2007) Letter
[4] TY Berger-Wolf, J Saia, a framework for analysis of dynamic social networks, in Proceedings of the 12th ACM SIGKDD international conference, 2006
[5] Boccaletti, S. and Ivanchenko, M. and Latora, V. and Pluchino, A. and Rapisarda, A., Detecting complex network modularity by dynamical clustering, PHYSICAL REVIEW E, vol 75, 2007
[6] Yang, B. and Liu, D.Y., Incremental Algorithm for Detecting Community Structure in Dynamic Networks, Proceedings of 2005 International Conference on Machine Learning and Cybernetics, volume 4, 2005
[7] Pluchino, A. and Boccaletti, S. and Latora, V. and Rapisarda, A., Opinion dynamics and synchronization in a network of scientific collaborations, Physica A: Statistical Mechanics and its Applications, volume 372, number 2, pp 316–325, 2006