（管理科学与工程专业论文）基于最小生成树的上海板块股票网络分析.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特i i i i 以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 翠、畸尼嗍峭6 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 答名：弘、吆砖 剔性辄 劲杰， 日期：嘲多均1 1 日 摘要 股票价格的变化不仅与上市公司的基本面有关，还受其他相关上市公司的影 响。正确理解股票间关联程度有利于投资者能够更好的构建投资组合，进行长期 投资。最小生成树以简单明了的网络图形象地表示股票间关联程度。目前国内只 通过简单相关系数计算股票间距离，构建并研究股票静态最小生成树网络。静态 最小生成树不能表示股票间关联程度的变化过程，股票间简单相关系数可能还包 含股票大盘指数的影响。本文将静态和动态最小生成树方法相结合，构建a 股 上海板块股票网络，分析股票聚类结构和网络拓扑性质。 论文的主要研究工作有以下三个方面： ( 1 ) 静态最小生成树网络聚类分析。简单相关系数、偏相关系数和符号时 间序列来计算节点间距离，并构建上海板块1 2 2 只未s t 股票的最小生成树网络 和分层树。通过比较，基于偏相关系数的最小生成树网络的行业分布特点最明显， 聚类效果最好。这也说明了偏相关系数更准确地表示了上海板块股票间的相互影 响程度。 ( 2 ) 静态最小生成树网络拓扑性质分析。节点度分布、平均路径长度和聚 类系数的检验结果表明，这三种指标对应的最小生成树网络是无标度网络，但不 是小世界网络。本文还引进了吸引率和组系数，组系数最高的是金融地产，最低 的是原材料；吸引率最高的是工业和可选消费，平均吸引率最高的是信息技术。 ( 3 ) 动态最小生成树网络分析。本文以上海板块中金融地产、信息技术和 医药三大行业为研究对象，构建基于股票间偏相关系数的动态最小生成树网络。 该动态网络包含六个静态最小生成树，每个最小生成树的时间窗口尺度为两年， 两个最小生成树间隔六个月。结果表明随着时间的推移，行业内股票间的联系更 加密切，聚类效果增强。 关键词最小生成树；聚类分析；度分布；吸引率；组系数 北京t 业人学管理学硕i j 学位论文 i i a b s t r a c t 1 1 1 a b s t r a c t c h a n g e so fs t o c kp r i c e sn o to n l yr e l a t ew i t ht h ef u n d a m e n t a l so fl i s t e dc o m p a n i e s ，b u ta l s o a r ei n f l u e n c e db yo t h e rr e l a t e dl i s t e dc o m p a n i e s i ti si m p o r t a n tf o ri n v e s t o r st ou n d e r s t a n dt h e r e l a t i o n s h i p sa m o n gs t o c k s i n v e s t o r sc a nc o n s t r u c tab e t t e ri n v e s t m e n tp o r t f o l i o m i n i m u m s p a n n i n gt r e e ( m s t ) i sac o m m o n l yu s e dn e t w o r ka p p r o a c ht or e s e a r c hc l o s e n e s sb e t w e e ns t o c k s ， w h i c hc a l lh e l pt oi d e n t i f yp o t e n t i a lt r a d i n gr u l e sa n di n f o r m a t i o n c u r r e n t l y , d o m e s t i cs c h o l a r s f o c u so na n a l y z i n gc l u s t e r so fs t o c k si nt h es t a t i cm s tb a s e do ns i m p l ec o r r e l a t i o nc o e f f i c i e n t s b e t w e e ns t o c k s ，n o ta n a l y z i n gt h en a t u r eo fn e t w o r kt o p o l o g y s t a t i cm s tm e a n st h a tt h e r ei so n l y o n em s tc o n s t r u c t e dd u r i n gt h ec o r r e s p o n d i n gr e s e a r c ht i m ea f e a h o w e v e r , s m i l em s tc a n t s h o wc h a n g e so fr e l a t i o n s h i p sb e t w e e ns t o c k s i na d d i t i o n ，s i m p l ec o r r e l a t i o nc o e f f i c i e n t sb e t w e e n s t o c k sm a yi n c l u d et h ei m p a c to ft h es t o c km a r k e ti n d e x b o t hs t a t i cm s ta n dd y n a m i cm s ta r e a p p l i e dt oc o n s t r u c ta n ds t u d yt h en e t w o r ko fas h a r e so fs h a n g h a id i s t r i c tl i s t e do ns h a n g h a i s t o c ke x c h a n g e t h em a i na c h i e v e m e n t so ft h i sp a p e ra g ea sf o l l o w s ： ( 1 ) c l u s t e ra n a l y s i so ft h es t a t i cm s tn e t w o r k t h e r ea r e12 2s t o c k si ns h a n g h a id i s t r i c t s e l e c t e df o rt h es t u d y , w i t ht h et i m er a n g ef r o ma u g 1 砒2 0 0 7t oa u g 2 7 m2 0 0 9 i na d d i t i o no f s i m p l ec o r r e l a t i o nc o e f f i c i e n t sb e t w e e ns t o c k s ，p a r t i a lc o r r e l a t i o nc o e f f i c i e n t sb e t w e e ns t o c k s w h i c hr e d u c et h ei n f l u e n c eo fs h a n g h a ic o m p o s i t ei n d e x ，a n ds t o c ks y m b o ls e q u e n c e sa r eu s e dt o c o m p u t ed i s t a n c e sb e t w e e ns t o c k s t h e nt h ed i s t a n c e sa r eu s e dt oc o n s t r u c tt h ec o r r e s p o n d i n g m s ta n dh i e r a r c h i c a lt r e e a f t e rc o m p a r i s o n ，t h es t o c kc l u s t e re f f e c t so fm s tb a s e do np a r t i a l c o r r e l a t i o nt o e 伍c i e n t sa r et h eb e s t ( 2 ) n e t w o r kt o p o l o g ya n a l y s i so fs t a t i cm s t t h et e s tr e s u l t so fn o d ed e g r e ed i s t r i b u t i o n ， a v e r a g ep a t hl e n g t ha n dc l u s t e r i n gc o e f f i c i e n ts h o wt h a tt h et h r e em s t n e t w o r k sa r ea l ls c a l e - f r e e n e t w o r k s b u tn o ts m a l l - w o r l dn e t w o r k s t h i sp a p e ra l s oi n t r o d u c e sa t t r a c t i v er a t ea n dg r o u p i n g c o e f f i c i e n tt o t e s t r e s u l t ss h o wt h a tf i n a n c eh a st h eb e s tg r o u p i n gc o e f f i c i e n t ，i n d u s t r i a l sh a st h e b e s ta t t r a c t i v er a t ea n di n f o r m a t i o nt e c h n o l o g yh a st h eb e s ta v e r a g ea t t r a c t i v er a t e ( 3 ) d y n a m i cm s tn e t w o r k sa n a l y s i s t h i sp a p e rs e l e c t st h r e ei n d u s t r i e so fas h a r ei n s h a n g h a id i s t r i c tf o rr e s e a r c h ，w h i c ha r ef i n a n c e ，i n f o r m a t i o nt e c h n o l o g ya n dm e d i c i n e ，w i t ht h e t i m er a n g ef r o mj a n 1 吼2 0 0 5t oj u n e3 0 m2 0 0 9 d y n a m i cm s tn e t w o r k sa r ec o n s t r u c t e db a s e do n p a r t i a lc o r r e l a t i o nc o e f f i c i e n t sb e t w e e ns t o c k s n ed y n a m i cm s t n e t w o r k sc o n t a i ns i xs t a t i cm s t n e t w o r k s e a c hs t a t i cm s th a sat i m ew i n d o ww h o s ew i d t hi st w oy e a r s ，a n dt h ed i s p l a c e m e n t b e t w e e nt w oc o n s e c u t i v ew i n d o w si ss i xm o n t h s r e s u l t ss h o wt h a tw i t ht h ep a s so ft i m e ，s t o c k s i na ni n d u s t r ya r eb e c o m i n gm u c hc l o s e r 1 1 1 北京t 业人学管理学硕i j 学位论文 k e yw o r d s m i n i m u ms p a n n i n gt r y ；c l u s t e ra n a l y s i s ；d e g r e ed i s t r i b u t i o n ；a t t r a c t i v er a t e ； g r o u p i n gc o e f f i c i e n t i v 1 3 研究思路与研究特色5 1 3 1 研究内容与研究思路5 1 3 2 研究特色5 第2 章网络相关理论7 2 1 最小生成树规则网络7 2 1 1 最小生成树概念7 2 1 2 节点间的相近性度量距离8 2 1 3 最小生成树的算法9 2 1 4 分层树l o 2 1 5 理论假设1 l 2 2 其他网络1 1 2 2 1 随机网络1 1 2 2 2 小世界网络1 2 2 2 3 无标度网络1 3 2 3 本章小结1 4 第3 章距离的计算方法1 5 3 1 简单相关系数1 5 3 2 偏相关系数1 6 3 3 符号时间序列1 7 3 3 1 数据符号化1 8 3 3 2 符号序列间距离2 0 3 4 本章小结2 0 第4 章a 股上海板块的实证研究2 1 4 1 数据来源与预处理2 1 4 1 1 数据来源2 l 4 1 2 数据预处理2 2 4 1 3 股票行业分类标准2 2 4 2 上海板块股票静念最小生成树2 4 4 2 1 股票间距离的计算2 4 4 2 2 构建最小生成树2 6 4 2 3 构建分层树2 8 4 3 静态最小生成树网络实证结果分析3 0 4 3 1 聚类结果分析3 0 4 3 2 关联网络拓扑性质分析3 2 v 北京t 业人学管理学硕 j 学位论文 4 4 三大行业股票动态最小生成树 4 4 1 构建过程及结果 4 4 2 实证结果分析 4 5 相关建议 4 5 1 投资建议 4 5 2 对其他省市上市公司的发展建议 4 6 本章小结 结束语 结论 创新点 不足 参考文献 附录a 股上海板块股票名称表 攻读学位期间发表的论文 致谢 v l ”的铊躬躬们钳钙钙钙稻钉钉弱卯 第1 章绪论 1 1选题意义 1 1 1研究背景 第1 章绪论 股票市场是资本进行配置的主要场所之一，在经济和社会发展过程中占据 着重要的地位。我国改革开放以来资本市场的发展过程可以划分为：萌生阶段 ( 1 9 7 8 1 9 9 2 年) ，股票市场处于自我演变、缺乏监管和区域性试点的状态：初 步发展阶段( 1 9 9 3 1 9 9 8 年) ，国务院证券管理委员会和中国证监会的成立标志 着股票市场开始逐步纳入全国统一监管框架，全国性市场也开始发展；进一步 规范和发展阶段( 1 9 9 9 年至今) ，我国经济开放不断全面化，金融改革不断深 化，股票市场的深度和广度同益扩大。截至2 0 1 0 年3 月底，沪深交易所上市公 司已达1 8 0 7 家，总市值为2 4 5 万亿元人民币，居全球第三，总市值与2 0 0 9 年 g d p 的比例超过7 0 。我国股票主要在上海证券市场和深圳证券市场上市，其 中上海证券市场以大型上市企业为主，突出了上海作为国际金融中心的作用。 股票市场为加快改革开放、促进国民经济的持续发展和布局优化提供强劲的动 力。 在肯定成就的同时，我们也不能忽略股票市场存在的不足。一方面，我国 股票市场存在着浓重的投机氛围，许多投资者只重视短期操作，而不关注长期 投资，媒体也没有正确引导投资者进行股票长期投资，这使得我国股票市场没 有真正起到投资融资和优化配置资源等作用。另一方面，面对股票市场每天产 生的大量交易数据，投资者往往根据主观判断来选择不同的股票进行分散化投 资，构造投资组合，而这些投资组合不仅浪费投资者大量时间和精力，也达不 到投资者分散风险的要求。因此，如何充分分析股票价格时间序列数据及股票 间关联是引导投资者合理构造投资组合和长期投资的关键。 受公司自身特征、行业发展情况及宏观经济的影响，股票市场中各股票的 价格波动存在一定的相互关联。r n m a n t e g n a ( 1 9 9 9 ) 引入最小生成树方法研 究了美国s & p 5 0 0 只股票数据之问的交叉相关问题，第一次从网络的角度来研 究股票聚类【l 】。这项研究表明了包含在股票价格序列中的经济信息可以通过专 门的筛选过程观察到。 近些年来，国内外学者以股票时间序列间相关性为指标，构建股票市场的 最小生成树网络和无标度网络，研究股票网络的聚类结构和整体网络拓扑性质。 大批经济学家、数学家，甚至物理学家进入该领域，通过对金融时间序列进行 北京t 业人学管理学硕f ! 学位论文 网络实证研究，找出资产运行的内在规律性，发现交易数据中潜在的规律和经 济信息，在股票市场、外汇市场等多个领域取得了很大的进展。 基于以上背景，本文对原有最小生成树网络方法进行丰富和创新。 1 1 2研究意义 首先，股票市场反映企业的期望前景和风险，提供投资者需要的宝贵决策 信息。投资者希望通过得到的信息来预测未来价格的变化以获得收益。而最小 生成树方法使投资者仅通过股票关联网络就能得到有意义的经济信息。 其次，股票间的相关性及聚类特点以一种简单明了的最小生成树网络展现 出来，不需要其他更多的数据和假设。不同聚类的股票间波动的相关性小，这 可以帮助投资者在进行配置时可以取得良好的多元化效果。 再次，通过对股票市场最小生成树的聚类和网络拓扑性质的研究，有利于 了解股票市场局部和整体性能。 1 2国内外研究现状 股票市场包含大量信息，国内外学者从金融时间序列相关性的角度来研究 和理解股票市场的结构和特征。这些研究多数是用方差模型、主成分分析法、 随机矩阵分析法等方法对现有股票市场进行实证分析，来分析股票市场的风险 波动性和内在的聚类结构。近年来，从网络角度来解释股票市场中各类现象得 到了很大的重视。其中最为重要的研究之一是m a n t e g n ar n ( 1 9 9 9 ) 的文章，他 通过股票价格序列间的简单相关系数( 即皮尔森相关系数) 来构造股票间的最 小生成树及其分层树，节点代表股票，连线代表股票之间的距离。该研究中出 现的股票聚类与实际经济意义上的分类相对应，这意味着股票价格自身提供了 有意义的经济信息。用最小生成树和分层树来分析股票市场结构的这种方法引 起了许多学者的关注和兴趣。 g b o n n a n o 等( 2 0 0 0 ) g l 过构建股票收益率时间序列的最小生成树和层级树， 研究了纽约证券交易所( n y s e ) 1 0 0 只股票之间的聚类结构和网络拓扑性质。当 计算收益率的时间尺度从一天变成半个小时再到十九分钟三十秒时，所研究股 票集的最小生成树结构从一个有多个中心节点的复杂组织退化到只有一个中心 节点的单层组织，股票间的关联性降低【2 1 。作者( 2 0 0 1 ) 通过实证研究了金融时间 序列中包含的三层股票市场复杂性【3 】。作者( 2 0 0 3 ) 还用n y s e 的1 2 年交易期间 大量真实数据和用随机市场模型和单因素模型所模拟的数据来建立最小生成 树，发现模拟数据无法表现出真实数据的实际特征【4 1 。作者研究了一个确定网 络聚类自然性质的聚类方法【5 1 ，利用最小生成树方法研究了不同时间尺度的股 第1 章绪论 票组合和股票指数等，表明有用的经济信息可以从有噪音的相关矩阵中提取出 来【6 】。这与作者用其他方澍7 8 】做出的结果相符合。此外，作者( 2 0 0 3 ) 分别利用 股票收益率和股票波动率来构建n y s e 的最小生成树，实证表明收益率得出的 最小生成树比波动率得出的最小生成树要稳定【9 】。 j p o n n e l a 等( 2 0 0 2 ) 基于超度量空间的概念，根据股票收益率相关系数矩阵 构建s & p 5 0 0 的最小生成树，并称其为“资产树”。一个资产树只反映了所给定 时间市场拓扑性质。作者以两年为刻画一颗资产树的时间窗口，以一个月为移 动频率，动态地研究了资产树的演变过程，证明m a r k o w i t z 最佳股票组合往往 处在树的外边【1 0 】，检验了资产树的鲁棒性】和资产树在股票市场危机( 如黑色星 期一) 如何收缩和回归正常【1 2 1 。作者还介绍了一种用于构建股票网络结构的新 方法【l3 1 ，。资产图，它与资产树相似，都是基于资产收益之间的相关系数，但 形成一个分离的图。在短期内，资产图比资产树衰退得慢，但在长期内，资产 树要比资产图衰退得慢，其无尺度行为也比资产图可靠。 k i m 等( 2 0 0 2 ) 就s & p 5 0 0 只股票价格的关联性建立其无权网络，在无权网络 中，股票间是否有边取决于股票间相关系数是否大于事先设定的值，作者分析 节点的影响力( i s ) ，发现i s 绝对值的分布从幂律分布，呈现出无标独特性【1 4 , 1 5 】。 r c o d h o 等( 2 0 0 7 ) 为了研究法国2 0 0 6 年前后的两个股票行业标准哪个更合 理，对伦敦股票交易所的f t s e l 0 0 成分股进行实证分析，通过研究最小生成树 中节点间相关性和平均路径长度的时间依赖性，结果表明2 0 0 6 年之后颁布的新 标准更加合理；同时作者还比较了用实际数据和随机市场模拟数据所得出的最 小生成树性质【l6 j 。 c g i l m o r e 等( 2 0 0 8 ) 利用最小生成树方法来研究欧盟股票市场指数的变化 过程，描述了最小生成树和分层树的动态变化过程。2 0 0 4 年新加入的成员国与 其他成员国之间的关系较松散一些，但总体来说，市场间距离逐渐变短，这表 明欧洲市场国际股票组合所得的利润在减少【1 7 】。其他类似研究也表明各国之间 联系逐渐加强，这导致在全球范围内投资的投资者的潜在利润在减少【1 8 , 1 9 , 2 0 】。 w o o s u n g 等( 2 0 0 6 ) 建立了韩国k o s p l 2 0 0 只股票的最小生成树，研究了其 平均路径长度、度分布等性质和聚类结构，结果没有形成与韩国经济部门分类 相一致的聚类，但将k o s p l 2 0 0 只股票改为摩根斯坦利韩国指数成分股时，最 小生成树就能形成明显的与经济部门分类相一致的聚类，这也说明了韩国等新 兴市场与美国等成熟市场不刚列j 。作者( 2 0 0 8 ) 又研究了用日本东京股票市场收 益率的最小生成树网络结构，定义组系数( g r o u p i n gc o e f f i c i e n t ) ，检验传统工业 分类的有效性，结果表明该系数随时间成递减趋势。作者利用s & p 5 0 0 指数作 为国际市场来削弱外界的影响后，调整后的收益率形成的最小生成树聚类更符 合工业分类，这表明国际市场影响着如同本市场【2 2 1 。 北京y , i k 人学管理学硕i ：学位论文 以上研究中的股票间距离都是基于股票收益率时间序列之间的简单相关系 数。j gb r i d a 等( 2 0 0 7 ) 丰富了这个理论，将符号时间序列分析法( s t s a ) 用于构 建最小生成树及分层树，即将股票收益率时间序列根据阈值转变成符号时间序 列后再计算股票间距离。该方法用于研究意大利股票市场3 0 只大型上市公司股 票，形成了有经济意义的聚类【2 3 1 。作者还将该方法用于分析美国道琼斯市场， 得到的拓扑结构还运用蒙特卡罗模拟方法进行检验，表明结果并非随机【2 4 】。 g a r a sa 等( 2 0 0 7 ) 研究了雅典股票交易所( a s e ) 1 9 8 7 2 0 0 4 期间交易的三种 不同股票组合的属性。作者使用最小生成树法和随机矩阵理论( r m t ) ，同时检 验股票资产组合和整个市场的每个演变过程。三种不同股票组合对应的最小生 成树的相关系数和平均路径长度分布有一个类似行为，但节点度随着时间的变 化而变化，这归因于金融危机【z 5 1 。 c o m n e l lc 等( 2 0 0 7 ) 将随机矩阵理论、最小生成树、平均聚类链接分析法和 平面最大过滤图用于分析纽约股票交易市场，检测是否存在聚类。这四种方法 都能检测出股票经济部门聚类的一些特性，但单个方法不能提取所有股票相关 系数矩阵的信剧2 6 】。作者同样将随机矩阵理论和最小生成树法用于检测伦敦股 票市场一个经济部门的股票是否有相同收益行为，结果也表明不同方法检验同 一部门信息的敏感性不刚2 7 】。 最小生成树法还用于分析美国联邦数据库中3 4 种利息的周数据之间的聚 类关系【2 8 1 ，不同国家外汇兑换利率之间的聚类关系【2 9 】。 在国内，李守伟等( 2 0 0 6 ) 综述了随机网络、规则网络和复杂网络这三种网 络方法对金融时间序列间相关性的研究，并用实际数据得出沪深股市的价格变 动具有高度的一致性【3 0 1 。孙博文等( 2 0 0 6 ) 利用最小生成树方法构建了我国上交 所和深交所所有股票的的拓扑结构，并发现该拓扑结构连通性满足幕律关系【3 。 胡冰( 2 0 0 7 ) 利用最小生成树和分层树，通过研究1 9 9 8 2 0 0 2 年间的上证3 0 指数 样本股组合距离矩阵而得到有经济意义的拓扑图，验证了最小生成树方法在我 国股票市场的适用程度，并比较了用不同种距离构建的分层树【3 2 1 。黄纬强等 ( 2 0 0 8 ) 分别运用最小生成树方法和平面最大过滤图法构建我国上证1 8 0 指数和 深证1 0 0 指数相应的股票关联网络，分析网络的基本拓扑统计性质和聚类结构 【3 引。黄飞雪等( 2 0 0 9 ) 改变了按成长价值属性和大盘，j 、盘属性来对确定证券投资 风格的方式，利用最小生成树法及分层树法分析上证5 0 指数的风格分布特征 3 4 , 3 5 1 o 综上所述，国内外相关研究主要以某个股票市场所有股票或者某个指数的 成分股为研究变量，而没有对某个典型地区的股票进行过研究。国外基于最小 生成树理论主要研究整个股票市场的变化过程，特别是验证股市灾难带来的影 响，较少地考虑整个股市网络的拓扑性质。同时，国内研究主要有三个不足点， 第1 章绪论 ( 1 ) 以静态角度为主，只用一棵最小生成树来研究特定时间内的股票市场特点， 没有进行动态研究，( 2 ) 构建最小生成树的指标单一，只根据股票时间序列之 问的简单相关系数，( 3 ) 只分析股票聚类情况，不考虑股票网络拓扑性质，如 平均聚类系数、聚类系数和度分布等。 1 3研究思路与研究特色 1 3 1研究内容与研究思路 本文的基本内容是用最小生成树方法来构建我国上海股票市场的a 股上海 板块样本的关联网络，股票间距离分别用股票收益率序列间的皮尔森相关系数、 偏相关系数和股票收益率时间序列根据阈值转化后的股票符号时间序列这三种 指标计算，分析和比较这三种关联网络的聚类结果，并用平均路径长度、聚类 系数、节点度分布、吸引率和组系数来描述三种关联网络的网络拓扑性质。此 外，本文以上海地区金融地产、医药、信息技术三个行业股票为研究对象，以 两年为时间窗口，半年为时间移动步伐，构建一系列的最小生成树集，动态地 描述2 0 0 5 年1 月到2 0 0 9 年7 月这三个行业股票的聚类变化过程。 本文的研究思路为：第一章为绪论，提出论文的选题背景与意义，整理相 关文献综述，总结国内相关研究的不足，提出本文研究核心；第二章为网络相 关理论，描述了最小生成树规则网络和随机网络、小世界网络和无标度网络等 三个其他网络的特点；第三章为节点间距离的计算指标，分别讲述了简单相关 系数、偏相关系数和符号时间序列这三个指标的特点和转化过程；第四章是对 上交所上市的a 股上海地区板块进行实证，包含静态最小生成树网络和动态最 小生成树网络的研究；最后是总结和展望。 1 3 2研究特色 本文的主要研究特色如下： ( 1 ) 本文第一次运用最小生成树方法研究a 股上海地区股票网络的聚类 结构和网络拓扑性质。上海在我国证券市场具有重要地位，实证结果对投资者 的投资决策和对推动其他地区上市公司的发展具有重要的参考价值。 ( 2 ) 丰富了构建最小生成树的指标，股票间的偏相关系数和股票符号时间 序列比股票间的相关系数消除更多的噪音和不定因素，聚类效果更好。 ( 3 ) 丰富了描述网络拓扑性质的指标，不仅使用平均路径长度、聚类系数、 度分布，还引入了吸引率和组系数这两个指标。 北京t 业人学管理学硕i ：学位论文 ( 4 ) 除了静态地描述a 股上海板块股票的特点，也同时动态地描述了金 融地产等三大行业的聚类变化过程。 第2 章网络相关理论研究 第2 章网络相关理论 现实世界存在着许多网络，从互联网到运输网，从科研合作网络到社会关 系网络等等。生活中的各种系统可以抽象为网络，其中网络中的节点代表系统 元素( 如人、动物、计算机终端、国家等) ，边代表相连元素之间预先确定的关 系( 如友谊、商业联盟、捕食关系等) 。各种网络的研究受到了高度的重视。在 网络中，有一种网络性质不需要根据节点和边的具体位置和形态就可以表现出 来，这种性质称为网络拓扑性质，相应的结构为网络拓扑结构【3 6 1 。起初，科学 家用一些规则的结构来表示真实系统各因素之间的关系，这样的网络为规则网 络，如最小生成树网络等；在1 9 世纪5 0 年代末，科学家用一种新的办法来构 造网络，即节点之间是否有连线不再是根据一个概率决定的【37 1 ，这样生成的网 络为随机网络；上个世纪9 0 年代，科学家发现了小世界网络和无标度网络。 本文的网络符合以下限制： ( 1 ) 无向：边没有表现出固有的方向，边代表两个节点相互的作用，隐含 这样描述的系统是对称的。 ( 2 ) 简单：不能用多重边连接同一对节点，节点也不能通过边与自身相连。 ( 3 ) 连通：任何节点都可以通过一定路径到达任何其他节点。 ( 4 ) 随机网络和小世界网络中的边是没有权重的，即每条边代表的大小是 相同的；而最小生成树规则网络中的边是有权重的。 2 1最小生成树规则网络 2 1 1最小生成树概念 规则网络是在一定规则下建立起来的，网络中任意两个节点的联系遵循既定 的规则。最小生成树( m i n i m u ms p a n n i n gt r e e ，m s t ) 是一种规则网络图，边连 接图中所有顶点而没有环，且边距离之和最短。许多如求修筑连接n 个城市的铁 路的最低造价等实际问题可转化为求一个最小生成树问题。最小生成树是一种无 预先管理的聚类方式，借助合理的筛选，能够通过移除最弱的连接来去除关联度 较低的信息，有利于发现研究集合中隐藏的、有意义的知识，在通信、计算机科 学、经济管理和金融等领域中广泛应用。 在给定的无向图g = ( y ，e ) 中，矿代表研究变量集合，每个研究变量是图中 一个节点，e 代表连接研究变量之间的边集合，( “，v ) 代表连接节点“与节点v 的 北京t 业人学管理学顾i ：学位论文 边( 即( “，y ) e ) ，而“，) 代表此边的权重，若存在丁为e 的子集( 即r e ) 且为无循环图，使得w ( d = y j ( “，v ) 的从r ) 最小，则该r 为g 的最小生成树。其 l 蒹r 基本性质为： ( 1 ) 最小生成树是一个简单的无向无环连通图。 ( 2 ) 最小生成树的边数一定是节点数减一，即i e h v | 1 。如果边数等于或 大于节点数，则可能出现循环图，或用多重边连接同一对节点。如果边数小于 节点数减一，则肯定存在某个节点没有与其他节点相连接。 ( 3 ) 对同一研究变量集合来说，其所对应的最小生成树不是唯一的。 ( 4 ) 若u 是节点集矿的一个真子集，若( 口，v ) 其中一个端点在u ( u ) ， 另一端点不在u ( 即v v u ) ，且它们具有最小权重值的一条边，则一定存在g 的一棵最小生成树包含此边( “，v ) 。 2 1 2节点间的相近性度量一一距离 构建研究变量集合的最小生成树主要分两个步骤：首先确定研究变量之间 的相近性度量距离，得到整个研究集合的距离矩阵d ；然后通过算法从距离 矩阵中得到最小生成树。 在最小生成树网络中，节点间距离表示着变量之间相似性，对于节点i ，_ ， 和k ，它们的距离d 。一般满足下列三个条件： d 豇o d o = o f = ( 正定性) ( 2 一1 ) d 扩= 办 ( 对称性) ( 2 2 ) d 口如+ 如 ( 三角不等式) ( 2 3 ) 计算两个节点距离的方式有许多，常用的距离主要有以下几种。先设任意 节点i 和，对应的变量向量有q 个不同值y 。 ( 1 ) 欧几里德距离，公式为： d u = 即两个节点的距离是每个变量之差的累积平方和的平方根。 ( 2 - 4 ) 第2 章网络相火理论研究 ( 2 ) 明考斯基距离，公式为： d g = 协k = l 叫p p 5 ， li 该距离是欧几里德距离的扩展，每个变量之差的p 次方的累积绝对值之和的p 次方根。 ( 3 ) 切比雪夫距离，公式为： d l = 珑 珞一| ( 2 - 6 ) 两个节点间的距离是任意一个变量值之差的最大绝对值。 ( 4 ) 块距离，公式为： 略= 陬一i ( 2 7 ) 两个节点间的距离即每个变量值之差的累积绝对值总和。 ( 5 ) 自定义距离，公式为： d ，( p 。，p ：) ：| - 羔i 一i 肚i n 见( 2 8 ) lk f f i ll 用户可指定指数p 。和开方次数p ：。 胡冰利用上述各种距离对上证3 0 进行分层聚类实证研究，结果表明不同的 距离所产生的结果差异不大【3 2 1 。因此本文还是应用欧几罩德距离来计算节点间 的距离。第三章将详细描述用于计算节点间距离的三种指标。 2 1 3最小生成树的算法 最小生成树有三种算法，分别为普里姆( p r i m ) 算法【3 8 】、克鲁斯卡尔 ( k r u s k a l ) 算法和索林( s o l l i n ) 算法【3 8 1 ，这三种算法都使用了一种叫贪 婪算法的设计策略。 ( 1 ) 普罩姆算法。普里姆算法是一种构造性算法。假设g = ( 矿，e ) 是一个具 有珂个节点的带权连通无向图，r = ( 【，t g ) 是g 的最小生成树，其中u 是r 的顶 点集，您是r 的边集，则由g 构造最小生成树r 的步骤如下： 初始化u = ，v 是矿中任一个节点，以v 到其他节点的所有边为候选边。 重复以下步骤( 刀一1 ) 次，使得其他( 刀一1 ) 个节点被加入到u 中。 北京t 业人学管理学硕i ：学位论文 a ) 从候选边中挑选权值最大的边输出，设该边在y u 中的节点为h ，将叱加 入u 中，删除和关联的边； b ) 考察当前矿一u 中的所有节点y ，修改候选边：若( ，v ，) 的权值小于原来 和v ，的候选边，则用( ，v ，) 取代后者作为候选边。 ( 2 ) 克鲁斯卡尔算法。克鲁斯卡尔算法是一种按权值的递增次序选择合适 的边来构造最小生成树的方法。假设g ：( y ，e ) 是一个具有刀个节点的带权连通无 向图，r = ( 【，t e ) 是g 的最小生成树，其中u 是r 的节点集，扭是r 的边集，则 由g 构造最小生成树r 的步骤如下： 将u 的初值等于y ，即包含g 中的全部节点，扭的初值为空集，即图r 中 每一个节点各自构成一个连通分量。 按照边的权重值从大n d , 丰i i e n 的顺序，考虑g 的边集f 中各条边。若被 考虑的边的两个节点属于r 的两个不同的连通分量，则将此边作为最小生成树 的边加入到疆中，同时把两个连通分量连接成一个连通分量，若被考虑边的两 个节点属于同一连通分量，则舍去此边，以免造成回路，如此下去，当r 中的 连通分量个数为l 时，此连通分量便是g 的一棵最小生成树。 ( 3 ) 索林算法。索林算法在每个阶段都选择若干条边。在一个阶段开始时， 已选择的边和全部节点一起构成了一个生成森林( s p a n n i n gf o r e s t ) 。在一个阶 段中，我们为森林里的每棵树各选一条边。这条边是权重最小且刚好有一个顶 点在这棵树里的边。选择的边添加到正在构造的生成树中，如果两棵树选择了 同一条边，则删除同一条边的多个副本。同样，当图中有若干条边的代价相同 时，如果两棵树选择了两条不同的边，则这两条边分别和两棵树连在一起，当 然，这两条边具有相同的权重。在第一阶段开始时，已选边的集合是空的，算 法结束的条件是已经没有可供选择的边了，或者是当一个阶段结束时只剩下了 一棵树。 这三种算法的出发点不同，没有本质上区别，结果也完全一致。但克鲁斯 卡尔算法采用了边目录方式存储，该算法所用的空间内存要比普里姆和索林算 法少很多，更适合求边较稀疏的网络的最小生成树，所以本文采取克鲁斯卡尔 算法。 2 1 4分层树 最小生成树对应着唯一的分层树，分层树可以更直观地反映节点间聚类结 w l = f ，= j 。原先的三角不等式更严格了，即为： d ； m a x d k ( i ，) ，d k ( 1 ，歹) ) ( 2 1 0 ) 在绘制分层树的过程中，保证形成的绘制序列无交叉和对新增节点问或老 节点集合与新增节点的联结节点的记忆是两个重要的步骤。 2 1 5理论假设 在用最小生成树及其分层树研究变量间关系的研究中，假设条件很少，这 是该方法真实客观的原因之一。本文研究仅有的一个理论假设为： 假设1 ：假设最小生成树能很好地描述变量组合间的关系。 该假设是基于一种“后验 动机，即要根据该假设得到的研究结果从经济 学的角度是有意义的。 2 2其他网络 2 2 1随机网络 随机网络( r a n d o mn e t w o r k ) 是指网络中节点之间的连接是完全随机的，没 有一定的规律可言，典型的随机网络是e r 模型，由著名匈牙利数学家e r d o s 和r e n y t ”】于1 9 5 9 年为描述通信和生命科学中的网络而提出。在e r 模型这样 的随机网络中，尽管连接时随机设置的，但大部分节点度( 节点度是指该节点 直接相连的节点数目) 会大致相同，即节点度的分布方式遵循钟形的泊松分布， 有一个特征性的“平均数 。节点度比平均数高许多或低许多的节点都比较少， 随着节点度的增大，其概率呈指数式迅速递减，所以随机网络又称指数网络， e r 随机网络和其节点连接数的泊松分布如图2 1 和图2 2 所示。 ( 网络来源：_ h t t p ：b l o g 1 m t w c o m b p e o n a r c h i v e s 2 0 0 9 6 6 6 6 2 h t m l ) 。 北京t 业人学管理学硕f ：学化论文 图2 - 1 典型的e r 随机模型 f i g u r e2 - 1 。e rr a n d o mn e t w o r k 图2 - 2 随机网络中节点度泊松分布 f i g u r e2 - 2 p o i s s o nd i s t r i b u t i o no fn o d ed e g r e e si ne rr a n d o mn e t w o r k 2 2 2小世界网络 很多实际的网络既不是完全规则也不是完全随机，而是介于这两个极端之 间，这就是小世界网络，经典例子是人际网络中的“六度分离m 】，。t r a v e r s 和 m i l g r a m ( 1