摘 要： 不同时刻的动态网络往往具有不同权重，针对加权动态网络的频繁模式挖掘，提出一种挖掘算法WGDM，它适用于加权动态社会网络、生物网络等方面的频繁模式挖掘。WGDM算法利用支持度的反单调性裁剪搜索空间，从而减少冗余候选子图，提高算法效率。通过实验测试了WGDM算法的性能，并根据中国实际股票市场网络，利用WGDM算法挖掘股票市场网络中有趣的频繁模式。
关键词： 加权动态网络；加权图集；频繁子图；图挖掘
近年来，针对社会网络、生物网络等的挖掘研究越来越多(如社区识别、社区关系发现等)[1]，尤其是针对犯罪团伙和恐怖分子活动网络的研究，引起了世界各国的重视[2]。实际中，网络往往随时间而变动，即网络是动态网络[3]。挖掘动态网络中的频繁模式，即可以发现变化网络中具有相对“稳定性”的频繁模式，这些模式在动态网络中往往也是比较有趣和重要的，这对研究动态网络很有意义。由于图具有结构关系，可用来表示事物之间复杂的相互作用关系，是基本的数据结构，因此网络可用图来表示，即一个网络可抽象成一个图，对网络的挖掘研究也就转化为对图的挖掘研究。
在实际中，一个动态网络在某个时刻表现出来的整体重要性可能并不一样，这就需要考虑各个时刻网络的不同权重，即考虑加权的动态网络。而挖掘加权动态网络的频繁模式，即是挖掘加权图集的频繁子图。
对图加权主要包括顶点、边和整个图的加权。当前，已经提出一些关于加权图集的频繁子图挖掘算法[4-7]，如参考文献[4]、[6]提出的是基于顶点加权的频繁子图挖掘，而参考文献[5]、[7]则是基于边加权的频繁子图挖掘。
网络在某个时刻的重要性可以对整个图赋予不同权重来表示，无需考虑网络内部顶点和边的权重，有时也很难知道顶点和边的权重，针对这种整个图加权的挖掘，关于顶点或边加权的挖掘算法均不适用于这种挖掘。为此本文提出一种适用于整个图加权的频繁模式挖掘算法(简称WGDM)。
sup(P)=w1+w3=1+3=4
结合GASTON算法[9]的策略方法，下面给出挖掘加权图集中频繁子图的算法步骤：
算法2 挖掘频繁路径(Path)
输入：加权图集D，图编码，内嵌列表，最小支持度min_sup，路径P。
输出：频繁路径(Path)。
(1)事先由算法1计算加权图集中所有顶点和边的支持度，删除小于min_sup的顶点和边。
(2)由算法1计算出路径P的支持度，如果其支持度support(P)<min_sup，则停止扩展，剪掉其所有超图；否则从内嵌列表选取可扩展的边l，构造新图g←l+P。
(3)如果新图g还是路径，则转至步骤(2)。
(4)如果新图g是树则转至算法3。
(5)如果新图g是具有循环的图则转至算法4。
算法3 挖掘频繁树(Tree)
输入：加权图集D，图编码，内嵌列表，最小支持度min_sup，树T。
输出：频繁树。
(1)由算法1计算出树T的支持度，如果其支持度support(G)<min_sup，则停止扩展，剪掉其所有超图；否则从内嵌列表选取可扩展的边l，构造新图g←l+T。
(2)如果新图g还是树，则转至步骤(1)。
(3)如果新图g是具有循环的图则转至算法4。
算法4 挖掘频繁循环图(Cyclic Graph)
输入：加权图集D，图编码，内嵌列表，最小支持度min_sup，图G。
输出：频繁图。
(1)由算法1计算出图G的支持度，如果其支持度support(G)<min_sup，则停止扩展，剪掉其所有超图。
(2)否则从内嵌列表选取可扩展的边l，构造新图g←l+G，转至步骤(1)。
(3)输出所有频繁图。
从算法2~算法4，先找出频繁路径，如果该路径扩展成树，则转至找频繁树；如果扩展成图，则转至寻找频繁循环图。在寻找频繁树时，如果树扩展成循环图则转至寻找频繁循环图；最后找出频繁循环图。其实，路径和树都是无循环的特殊的图，所以最后输出的加权频繁子图也包括路径和树。
3 实验
3.1 算法性能测试
本文测试使用的数据集是有关分子生物活性信息的真实数据集NCI-H23，这个数据集可以从以下网址获 得：http：//www.cs.ucsb.edu/~xyan/dataset.htm。
NCI-H23数据集包括具有活性和无活性两种类别的图集，其中顶点有60多种标记，边有2种标记。假设无活性的图权重为1，而具有活性的图权重为2。本文选取200个具有活性和200个无活性的图，然后组成了一个具有400个图的加权图集。
算法测试用的PC机使用Intel Pentium(R)2.6 GHz CPU和512 MB的内存，操作系统为Red Hat Linux，算法使用C++语言实现，并用g++编译。实验结果如图3所示。
从图3可以看出，当支持度比较小时，算法挖出到的频繁子图数目非常大，如在最小绝对支持度为60时，可挖掘到18 673个频繁子图，这比最小绝对支持度为120时挖掘到的675个频繁子图多了27倍；运行时间则是随着最小支持度的增加而减少，在最小绝对支持度为96时，运行时间只需0.69 s，总体上算法具有良好的效率。
3.2 股票市场网络的挖掘应用
结合中国股票市场，利用本文提出的算法挖掘股票市场网络中的频繁模式。一般股票价格会随着时间变化，不同时段股票跌幅或涨幅不一样。本文抽取20支股票，这些股票来自电子行业、啤酒行业、金融银行等领域，然后以一个季度为一个时段，统计这些股票在2010年四个季度里的涨跌情况，其中在每个季度里，分四种情况划分成四种网络：涨幅超过40%的股票网络、涨幅在40%以内的股票网络、跌幅在20%以内的股票网络以及跌幅超过20%的股票网络。股票网络中，顶点表示股票，不同股票，标记也不同，而股票间的关联就是边，不同股票的边标记也不同，同一个网络中的任意两支股票均有一条具有标记的边相连。在实际中，对于涨幅比较高或者跌幅比较大的情况应给予额外关注，为此对涨幅超过40%和跌幅超过20%的网络加大权重，本文设定这两种网络权重为2，而其他两种网络则给予1的权重。总共得到9个网络图组成的图集，其中有3个网络图属于涨幅超过40%或者跌幅超过20%，给予的权重为2，其余6个网络图权重为1。利用本文WGDM算法挖掘这个加权动态网络图集的频繁模式，而用GASTON算法挖掘无加权动态网络图集(即所有图权重都为1)，其中设定绝对最小绝对支持度min_sup为4时，可以发现两种具有5个顶点的频繁模式如图4所示。
实际中，相同行业的公司、企业的发展趋势比较有相同之处，其股价也较有可能同涨同跌。如图4所示，本文挖掘出的频繁模式，都是由银行组成，而GASTON算法挖掘出的频繁模式由银行和汽车两个不同行业组成。所以本文算法的挖掘结果，与实际比较吻合，进一步验证了本文算法的有效性。
挖掘加权动态网络的频繁子图困难在于产生的候选子图数量过多，而且子图同构检测问题也会影响算法的效率。对此，本文算法利用支持度的反单调性对搜索空间进行裁剪，并采用参考文献[7]的策略将挖掘图划分成挖掘路径、树和循环图的三个子问题，减少了候选子图数量和子图同构检测次数，提高了算法效率。而且将算法应用于实际的股票市场网络，挖掘结果也验证了本文算法的有效性。本文算法还可进一步拓展应用到其他网络的频繁模式挖掘。
参考文献
[1] RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in networks[J]. PNAS， 2004， 101(9)： 2658-2663.
[2] XU J J， CHEN H C. CrimeNet explorer： a framework for criminal network knowledge discovery[J]. ACM Transactions on Information Systems， 2005， 23(2).
[3] BERGER-W T Y， SAIA J. A frameworkfor analysis of dynamic social networks[C]. KDD’06. Philadelphia：[s.n.]， 2006： 523-528.
[4] 耿汝年，董祥军，须文波.基于全局图遍历的加权频繁模式挖掘算法[J].计算机集成制造系统，2008，14(6)：1220-1229.
[5] 王映龙，杨珺，周法国，等.加权最大频繁子图挖掘算法的研究[J].计算机工程与应用，2009，45(20)：31-34.
[6] 封军，郑诚，郑晓波，等.基于加权有向图的权频繁模式挖掘算法[J].微型机与应用，2010，29(20)：4-7.
[7] Jiang Chuntao， COENEN F， ZITO M. Frequent sub-graph minjing on edge weighted graphs[C]. DaWak’10 Proceedings of the 12th international conference on Data Warehousing and knowledge discovery， Spinger-Verlag， 2010：77-88.
[8] 高琳，覃桂敏，周晓峰.图数据库中频繁模式挖掘算法研究综述[J].电子学报，2008，36(8)：1603-1609.
[9] NIJSSEN S， KOK J N. Aquick start in frequent structure mining can make a difference[C]. Proceeding of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2004). Seattle， WA， USA：Springer-Verlag， 2004： 4571-4577.