嵌入技术的动态异构信息网络的演化聚类

陈丽敏，杨静，张健沛

(1.哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001;2.牡丹江师范学院计算机科学与技术系，黑龙江牡丹江157011)

信息网络普遍存在，如社会信息网络、DBLP书目网络，这些网络由多种类型数据构成，不同类型数据之间彼此关联，称之为异构信息网络。对异构信息网络聚类分析能更好地理解网络的隐藏结构以及每个类的数据所代表的角色［1］，而基于概率模型的异构信息网络聚类算法［2-3］只针对具体的应用领域设计函数，不具有普遍性，且收敛性也不稳定。异构网络的链接推理［4］时，往往需要最初的聚类划分更精确一些，而传统的高阶异构聚类算法［5-6］复杂度太高不适合异构信息网络。异构信息网络经常是动态的而非静态的，动态同构数据的演化聚类［7］的研究已经做了很多，而动态的异构信息网络的演化聚类分析，目前只有ENetClus［8］算法，该算法没有关注聚类质量，更侧重跟踪类的变化及分析类的推进、形成与消失。Khoa［9］使用近似 commute time嵌入聚类同构数据集，取得了很好的效果。受该思想启发，本文从相容二部图的角度提出一种基于嵌入技术的动态异构信息网络的演化聚类算法，具有较高的聚类质量，且计算速度也比较快。

1 时间平滑二部图

定义 1:给定G=＜V，E，W＞，V=X0∪X1，其中X0与X1为2个不同类型的数据集。若∀〈xi，xj〉∈E，则xi∈X0且xj∈X1，称G为二部图。

r(xi，xj)表示二部图G的结点xi与xj的关系，若结点xi与xj有关系，则结点xi与xj之间有边存在，否则无边存在。

给定t时刻的二部图Gt，∀xi，xj∈Gt。使用代价函数时间平滑Gt两结点的关系: