动态图中变化子图识别研究.pdf

摘 要 在社会网络分析中，一般用图来表示网络中的实体与实体间的关系，以往 的工作大多都停留在对静态图的研究上，而现在许多的应用领域内，如生物信 息学、交通网络、无线传感器网络、电子通信网络等，所对应的图是随着时间 不断变化的。比如在大型的无线传感器网络中，一个查询的处理过程是由许多 传感器节点间的信息交换来完成的，而传感器节点的能量和通信距离是有限的， 这些节点在每个时刻都有可能因为种种原因而停止工作，在不同时刻，图的拓 扑结构都在发生不断的变化，这将会影响到大片网络的路由状况和最后的查询 执行时间，所以，在一个大型的无线传感器网络中，当某些节点失效后，能够 知道网络中哪些点将会受到影响是非常重要的，而这些点构成的图被称为动态 图中的变化子图。 现在对变化子图的研究还处于初始阶段，一般采用随机游走近似度作为点 之间的相似度度量，通过计算并比较不同时刻的近似度矩阵，设定一个阈值来 选出近似度变化高于阈值的点集作为变化子图。随机游走近似度计算较为复杂， 虽然能得到较精确的相似度度量值，但是计算开销也比较大，并且用户只关心 最后结果集中的点，并不会在意这些点实际的值。为此，本文中提出了用最短 路近似度的概念来取代随机游走近似度，利用最短路近似度计算不同时刻的近 似度矩阵，并以此来识别动态图中的变化子图，同时考虑到应用中的实时计算 需要，提出了一种新颖的基于最短路近似度的增量计算算法。在实验中，我们 把该算法与现有的基于随机游走近似度增量算法在结果准确率和性能上进行比 较，我们得到，最短路近似度算法可以有效地计算出变化子图，虽然其重计算 的开销较大，但是在结合增量算法后，只需在初始阶段重计算一次，此后使用 增量算法即可。并且其增量算法执行时间很短，可以很好的满足实时计算的需 要。 利用阈值在不同时刻的近似度矩阵中虽然可以得到变化子图，但是当有多 个变化同时发生时，用现有的方法无法识别出变化子图中的点是属于哪个变化 的，为了实现这个目的，我们通过多维标度分析把原问题转换到多维空间中， 然后使用基于划分的聚类算法来识别出变化子图和变化子图中受不同变化影响 而产生的部分。试验结果证明我们的方法能够有效的区分出变化子图中的不同 部分。 关键字：动态图；变化子图；近似度； Abstract Researchers always use graph structure to represent the relationship between objects in social network analyze. Most former work have been done on the static graph structure, but in many domains, such as bioinformatics, traffic network, wireless sensor network, communication network, etc, the structures are evolving over the time. For example, in a large wireless sensor network, the process of a query is formed by a lot of information exchanging between sensors. Due to the limitation of energy and the communication range, a sensor could fail to work at any moment. So the topology structure of the wireless sensor network is changing all the time, and this change will affect the routing status of other sensors which still working. It is very important to figure out which sensors have been affected more due