摘 要： 在动态多模式网络中发现社区可以帮助人们了解网络的结构属性，解决数据不足和不平衡问题，并且可以协助解决市场营销和发现重要参与者的问题。一般来说，网络和它的社区结构是不均匀进化的。通过使用时态信息来分析多模网络，分析时态正则化架构和它的收敛属性。提出的算法可以解释为一个迭代的潜在语义分析过程，允许扩展到处理带有参与者属性和模内联系的网络。
关键词： 数据挖掘；社区发现；社区演化；多模网络；动态网络
当今网络拥有海量数据，要从海量数据中得到有用的信息是很困难的，因此网络分析[1]和建模[2]受到越来越多的关注。目前很多研究工作都只涉及一种模式的网络，即网络中只存在一种类型的参与者（点），参与者之间只存在同种类型的关系（联系）。但是，最近迅猛发展的Web数据挖掘涉及到了不止一种类型的参与者，这些参与者之间的关系也不再仅限于一种。这种类型的网络称为多模网络[3]。
在多模网络中，不同模中点的进化是不相同的。对于具有动态关系的异构实体，发现演化社区有很多的好处：(1)能够清晰地了解迥异模式之间的联系和长期演化模式；(2)可以形象化具有多种实体和多种关系的复杂网络；(3)有助于在多种领域中做决策；(4)在早期如果发现不良的演化样式，也可以发出事件警告。
在动态多模网络中发现社区演化还是很困难的，原因有二：(1)不同的模式之间的演化是有关联的；(2)不同模式具有独特的演化样式。本文采用谱聚类架构，提出一种发现动态多模网络中演化社区的一般方法。一个动态多模网络会包含一系列的网络快照，利用这些快照可以找出社区是如何演化的。在这个模型下，加入正则项反映时态变化[4]，可以将有联系模式的聚类结果和相邻时间戳作为一个模式下的社区更新的属性，是一个将动态多模网络分析和常规的基于属性的数据挖掘联系起来的新方法。
1 问题阐述
给出含有m种类型元素X1，X2，…，Xm的m模网络，找出每一模中的潜在社区是如何演化的[5]。在架构中，通过一系列的网络快照只关注离散时间戳，这个方法在正则项网络分析中得到广泛应用。表1所示为下文中所涉符号及其表示的内容。
图2显示平均计算时间。噪音越大，计算时间越长。静态聚类需要的时间是最短的，在线聚类的时间相对较长，时态正则化聚类的时间是最长的，特别是当噪音强度非常大时，时间变得不可接受。在这种情况下，时态平滑性已经被损害，算法需要更多的迭代找到最优解。
为了显示参数调整的效果，选择中等噪音强度的数据集，使用在线聚类和正则化聚类，时态权重wb从0.01～1 000进行调整， wa固定为1。如图3所示，时态权重过大反而得到不好的效果，即时态正则化处于首要地位。大部分时间，时态规则化有利于聚类考虑时态信息，时态权重在0.01～100的范围内体现的尤为明显。
在实际应用中，异构参与者之间的互相作用形成了多模网络。正是在这样的网络中，不同模的参与者构成社区并慢慢演化。本文提出了时态正则化多模聚类算法在动态多模网络中发现演化社区。这个算法可以理解为迭代的LSA过程，在不同模和时间戳下的属性构成社区矩阵。基于这种属性视图，提出的算法也能扩展到处理带有属性的网络、模内联系以及休眠点和活跃点。实验结果证明该算法能够根据一系列的快照找到更精确的社区结构和社区演化。
参考文献
[1] NEWMAN M.The structure and function of complex networks[J].SIAM Review，2003，45(2)：167-256.
[2] CHAKRABARTI D，FALOUTSOS C.Graph mining：laws，generators，and algorithms[J].ACM Comput.Surv.，2006，38(1)：65-78.
[3] WASSERMAN S，FAUST K.Social network analysis：methods and applications[M].Cambridge University Press，1994.
[4] BAUMES J，GOLDBERG M，WALLACE W，et al.Discovering hidden groups in communication networks[C].In 2nd NSF/NIJ Symposium on intelligence and Security Informatics，2004.
[5] LONG B，ZHANG Z M，WU X，et al.Spectral clustering for multi-type relational data[C].In ICML’06：Proceedings of the 23rd international conference on Machine learning. ACM，2006：585-592.
[6] 王林，戴冠中.基于复杂网络中社区结构的论坛热点主题发现[J].计算机工程，2008，34(11)：214-21.