基于复杂网络的大数据分析

第３５卷第５期　计算机仿真　２０１８年５月　文章编号：１００６—９３４８（２０１８）０５—０００１—０８　

基于复杂网络的大数据分析　

邵峰晶，孙仁诚，隋毅，王常颖　（青岛大学计算机科学技术学院，山东青岛２６６０７１）　摘要：作为大数据的特征，其中的个体数据不再是孤立，数据及其隐含的机理间具有复杂的关联关系，将所有数据构成难以　分割的整体。数据的动态生消会改变其原有的关联关系，影响数据的整体特性。大数据的这种特性使数据挖掘等面向主题　的分析方法呈现出局限：主题的预设和按主题的分析，割裂了主题间的相互作用关系．导致这些关系中隐含的机理被丢失。　针对上述问题，将大数据集视为复杂系统在信息空间的“数据”映像，基于复杂系统理论和复杂网络模型建立大数据分析的　系统级模型。建立了多要素及其间相互作用关系的形式描述和可计算的模型，将大数据分析问题转化为复杂网络的性质分　析：拓扑性质、动力学性质，“涌现”等系统特性，开展了海洋大数据、交通大数据等的分析应用实践。　关键词：大数据分析；复杂网络；复杂系统：涌现　中图分类号：ＴＰ３９１．９　文献标识码：Ｂ　

Ｂｉｇ　Ｄａｔａ　Ａｎａｌｙｓｉｓ　Ｂａｓｅｄ　Ｏｎ　Ｃｏｍｐｌｅｘ　Ｎｅｔｗｏｒｋ　ＳＨＡＯ　Ｆｅｎｇ－ｊｉｎｇ，ＳＵＮ　Ｒｅｎ－ｃｈｅｎｇ，ＳＵＩ　Ｙｉ，ＷＡＮＧ　Ｃｈａｎｇ－ｙｉｎｇｕ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｑｉｎｇｄａｏ　Ｕｎｉｖｅｒｓｉｔｙ，Ｑｉｎｇｄａｏ　Ｓｈａｎｄｏｎｇ　２６６０７１，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ａｓ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｂｉｇ　ｄａｔａ，ｄａｔａ　ａｒｅ　ｎｏ　ｌｏｎｇｅｒ　ｉｓｏｌａｔｅｄ．Ｔｈｅｒｅ　ｉｓ　ｃｏｍｐｌｅｘ　ｒｅｌａｔｉｏｎｓｈｉｐ　ａｍｏｎｇ　ｄａ—　ｔａ　ａｎｄ　ｃｏｎｎｏｔａｔｉｖｅ　ｍｅｃｈａｎｉｓｍ，ａｎｄ　ｔｈｅ　ｗｈｏｌｅ　ｄａｔａ　ｍａｋｅ　ｕｐ　ａｎ　ｉｎｄｉｖｉｓｉｂｌｅ　ｅｎｔｉｒｅｔｙ．Ｄｙｎａｍｉｃ　ｅｌｉｍｉｎａｔｉｏｎ　ｏｆ　ｄａｔａ　ｗｉｌｌ　ｃｈａｎｇｅ　ｉｔｓ　ｏｒｉｇｉｎａｌ　ｒｅｌａｔｉｏｎｓｈｉｐ　ａｎｄ　ｔｈｅ　ｏｖｅｒａｌｌ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｔｈｅ　ｄａｔａ．Ｔｈｉｓ　ｆｅａｔｕｒｅ　ｏｆ　ｂｉｇ　ｄａｔａ　ｐｒｅｓｅｎｔｓ　ｓｏｍｅ　ｌｉｍｉ－　ｔａｔｉｏｎｓ　ｔｏ　ｔｈｅ　ｔｈｅｍａｔｉｃ　ａｎａｌｙｓｉｓ　ｓｕｃｈ　ａｓ　ｄａｔａ　ｍｉｎｉｎｇ：ｔｈｅ　ｐｒｅｓｕｐｐｏｓｉｔｉｏｎ　ａｎｄ　ｔｈｅ　ｔｈｅｍａｔｉｃ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ｄａｔａ　ｃｕｔ　ａｐａｒｔ　ｔｈｅ　ｉｎｔｅｒｐｌａｙ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｔｏｐｉｃｓ，ｒｅｓｕｌｔｉｎｇ　ｉｎ　ｔｈｅ　ｌｏｓｓ　ｏｆ　ｔｈｅ　ｉｍｐｌｉｃｉｔ　ｍｅｃｈａｎｉｓｍｓ　ｉｎ　ｔｈｅｓｅ　ｒｅｌａｔｉｏｎｓｈｉｐｓ．Ｉｎ　ｏｒｄｅｒ　ｔＯ　ｓｏｌｖｅ　ｔｈｉｓ　ｐｒｏｂｌｅｍ，ａ　ｌａｒｇｅ　ｄａｔａ　ｓｅｔ　ｉｓ　ｃｏｎｓｉｄｅｒｅｄ　ａｓ　ａ”ｄａｔａ”ｉｍａｇｅ　ｏｆ　ｃｏｍｐｌｅｘ　ｓｙｓｔｅｍ　ｉｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｐａｃｅ．Ｂａｓｅｄ　ｏｎ　ｃｏｍｐｌｅｘ　ｓｙｓｔｅｍ　ｔｈｅｏｒｙ　ａｎｄ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　ｍｏｄｅｌ，ａ　ｓｙｓｔｅｍ－ｌｅｖｅｌ　ｍｏｄｅｌ　ｏｆ　ｂｉｇ　ｄａｔａ　ａｎａｌｙｓｉｓ　ｗａｓ　ｅｓｔａｂｌｉｓｈｅｄ，　ａｎｄ　ａ　ｆｏｒｍａｌ　ｄｅｓｃｒｉｐｔｉｏｎ　ｏｆ　ｍｕｌｔｉ－ｆａｃｔｏｒｓ　ａｎｄ　ｔｈｅ　ｉｎｔｅｒａｃｔｉｏｎ　ａｍｏｎｇ　ｔｈｅｍ　ｗｅｒｅ　ｐｒｅｓｅｎｔｅｄ．Ｗｉｔｈ　ｔｈｅ　ｃｏｍｐｕｔａｂｌｅ　ｍｏｄｅｌ，　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｂｉｇ　ｄａｔａ　ａｎａｌｙｓｉｓ　ｗａｓ　ｔｒａｎｓｆｏｒｍｅｄ　ｉｎｔｏ　ｔｈｅ　ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ：ｔｏｐｏｌｏｇｉｃａｌ　ｐｒｏｐｅｒｔｉｅｓ，ｄｙ—　ｎａｍｉｃ　ｐｒｏｐｅｒｔｉｅｓ，ｅｍｅｒｇｅｎｃｅ　ａｎｄ　ｏｔｈｅｒ　ｓｙｓｔｅｍ　ｆｅａｔｕｒｅｓ．Ｏｎ　ｔｈｉｓ　ｂａｓｉｓ，ｔｈｅ　ａｎａｌｙｓｉｓ　ｏｆ　ｂｉｇ　ｏｃｅａｎ　ｄａｔａ　ａｎｄ　ｂｉｇ　ｄａｔａ　ｏｆ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｗｅｒｅ　ｐｒｏｃｅｓｓｅｄ　ｔｏ　ｖａｌｉｄａｔｅ　ｏｕｒ　ｍｏｄｅ１．　ＫＥＹＷＯＲＤＳ：Ｂｉｇ　ｄａｔａ　ａｎａｌｙｓｉｓ；Ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ；Ｃｏｍｐｌｅｘ　ｓｙｓｔｅｍ；Ｅｍｅｒｇｅｎｃｙ　

１　引言　大数据是一个数据量庞大、数据类型多样、数据相互作　用关系复杂、动态产生或消失的异构数据集合。大数据重要　特征表现在：数据不再是一个个孤立的个体，数据之间及其　隐含的机理之间具有复杂的关联关系。这种复杂关系将这　个开放的异构数据集合的所有数据构成了一个不可分割的　整体，任何分割，都可能带来整体特性的丢失；其开放性使动　态生消的数据会改变数据间的既有相互作用关系，从而影响　数据集合的整体特性，这使得数据间的关联关系更为复杂。　大数据分析，旨在发现数据中隐含的机理、规律与知识。　

收稿日期：２０１８—０３—１０　

近年来数据仓库、数据挖掘／机器学习被广泛应用于大数据　分析。数据仓库是按主题基于统计的多维在线分析，分析的　结果是数据仓库中围绕主题的已知的数据的提取汇集。数　据挖掘、机器学习是预设一个主题，给出其分析模式算法，分　析的结果是主题数据内在规律的体现［１－２］。因此，对于给定　主题的大数据分析问题．上述大数据分析方法具有很好的适　用性，能够挖掘主题数据的内在规律，其分析结果是主题数　据规律的体现。然而实际应用中的大数据分析问题，往往涉　及若干主题，不同主题间存在复杂的、动态变化的相关性，单　个主题分别逐一研究，丢失了主题间的相关性．即使获取所　有主题规律，也无法获得问题的整体规律。在此试举两个典　型大数据分析的例子予以说明。　利用大数据分析的方法揭示海洋灾害（如赤潮、浒苔等）　

——１——　的特征与演化规律，已有许多有益的尝试，在数据仓库中．海　洋灾害特征、规律分析问题转化为数据仓库中的主题．通过　在线分析（Ｏｎｌｉｎｅ　Ａｎａｌｙｔｉｃａｌ　Ｐｒｏｃｅｓｓｉｎｇ，ＯＬＡＰ）实现了对相关　主题数据的多角度、多粒度统计分析＿３　］。但ＯＬＡＰ分析仅　能给出数据简单的聚集统计结果．而无法发现数据间隐含的　复杂关系和规律。针对这一局限，数据挖掘／机器学习技术　被应用到海洋灾害的分析预测。而海洋灾害预测问题影响　要素多，关系复杂，往往涉及若干主题，大量研究给出了与之　相关的多种因素的相关特征、机理、规律，但对其爆发激励仍　不能清晰把握。其关键原因在于赤潮、浒苔是由多因素、在特　定条件下相互复杂作用而导致的一种水域污染现象，是一种　复杂的多因素相互作用而产生的系统的“涌现”现象。孤立地　研究单个要素或几个要素与赤潮、浒苔爆发的关系，难以获　取赤潮、浒苔爆发的整体机理。再比如，许多研究成果表明　交通拥堵成因并不单纯是交通流量多达导致的，而往往是各　种因素共同作用的结果，道路网络、交通信号、驾驶人行为、　上下游交通流、气象条件等都会对交通拥堵产生作用。这些　共同作用的效应通常大于所有因素各自作用的效应之和．交　通拥堵是多要素复杂相互作用的“涌现”现象。　很显然，大数据分析必须放到系统级考虑，而不能以还　原论为指导，事实上，大数据问题是典型的复杂系统，大数据　的海量性、异质性、关系复杂性、动态性等特征对应着复杂系　统的个体规模庞大、同质异质个体并存、个体间复杂的非线　性作用以及实时开放的特性。因此，将大数据集视为复杂系　统在信息空间的“数据”映像［５］，基于复杂系统理论描述大　数据分析所涉及的多要素及其间相互作用关系，将大数据分　析问题转化为复杂网络的性质分析：拓扑性质、动力学性质，　“涌现”等系统特性。是获取大数据问题的整体特征、规律、机　理的有效方法。　复杂网络是复杂系统的有效模型，个体抽象为节点，个　体间的相互关系抽象为连边，典型的复杂网络模型有规则网　络，随机网络，小世界网络，无标度网络等。典型复杂网络模　型是对复杂系统中单一性质个体及其间关系进行描述。且对　问题的讨论仅局限于同一复杂系统。层次网络模型使用层　表示相同性质个体及其间关系．不同性质个体间关系由层间　连边表示。层次网络解决了不同类要素间相互关系的描述　问题，但其研究仍处于问题描述阶段，缺乏网络层间关系计　算分析的数学描述。基于此，提出了动态组网——多类要素　相互关系动态演化的形式描述．不同类要素间（跨网络）性　质，以及复杂网络性质高效分析算法。　２复合复杂网络模型　。］　定义１（复合网）：满足下列条件的四元组Ｇ＝（　，Ｅ，尺，　Ｆ）称作一个多子网复合复杂网络（简称复合网）：　１）Ｖ＝｛　，　，…，　｝，表示节点的集合，ｎｚ＝Ｉ　Ｉ是集　合　的阶；　２）Ｅ：｛＜＂１３ｈ，　ｆ＞Ｉ　＾，　２∈Ｖ，ｌ　，ｆ　ｍ｝　Ｖ×Ｖ，表示　一２～　节点间连边的集合；　３）Ｒ＝｛Ｒ。，Ｒ：，…，　｝，Ｒ　表示节点间一种相互作用关　系集合，　是节点间相互作用关系的总数：　４）映射Ｆ：Ｅ一２　。　当ｒｌ，：１时，复合网即是典型复杂网络模型，只描述了节　点间一种相互关系。　下面给出子网的定义．子网由复合网中具有给定关系的　边及其两端结点组成。　定义２（子网）：设Ｇ＝（　，Ｅ，Ｒ，Ｆ）为复合网，称Ｇ　＝　（　，Ｅ　，Ｒ　，Ｆ　）为Ｇ关于Ｒ　Ｒ的子网：　１）　２）Ｅ＝ｔ＜　，　＞ｌ　Ｆ（＜　，　ｆ＞）∈Ｒ　｝　３）Ｆ　：Ｅ　＿＋２　定义３（子网加载）：子网加载是将多个子网复合为一个　新的复杂网络。设复合网Ｇ。：（　，Ｅ　，Ｒ。，Ｆ　），Ｇ　＝（　，　Ｅ：，Ｒ：，Ｆ２），给定加载映射　：Ｖ。×　—Ｒ一，称Ｒ　为加载关　系。将发生加载运算时新生成的边称为网际边，网际边两端　所关联的节点称为网际节点。　定义４（子网退缩）：设复合网Ｇ＝（　，Ｅ，Ｒ，Ｆ），给定关　系集合Ｒ　ｃ尺，子网退缩是指得到一个复合网Ｇ关于关系集　合　一　的子网Ｇ　＝（　，Ｅ　，Ｒ　，Ｆ　）　１１　Ｖ　２）Ｅ　＝Ｅ一｛＜　＾，　＞Ｉ　Ｆ（＜　，　＞）∈Ｒ｝　

３）Ｆ：Ｅ—｝Ｒ—Ｒ　复合复杂网络模型不仅提供对同质要素、异质要素问相　互作用关系的描述，还能够通过子网加载、退缩等动态组网　运算实现跨主题的数据分析和特定问题的数据分析。在《伤　寒论》复合网模型研究中，将药物作为节点，药物间的配伍关　系作为连边建立了药物配伍网络，同时，以病证作为节点，病　证间的症状群关系作为连边，形成了病证网络，通过子网加　载运算，实现了药物和病证的跨主题分析，发现了治疗病证　的特效药物。另一方面，利用子网退缩运算，将药物一病证　复合网退缩得到太阳病子网、阳明病子网、少阳病子网、少阴　病子网、厥阴病子网、太阴病子网，通过子网分析发现了病证　的传变特征和规律＿９　。　在青岛市公交复合网络研究中．以公交线路作为子网，　两条公交线路具有公共站点为网际节点．得到公交线路子网　１２９个，网际边４０７１条（数据来源于２００７年青岛信息港）。通　过使用退缩运算获取公共站点子网，分析该网络直径为３，说　明任意两个站点问可最多不超过３次就可以实现换乘，节点　的度是该条线路可以换乘其他线路的数目，最大度为１１８，最　小度为１２，平均度为６３，每条公交线路平均与６３条公交线路　相交，占所有线路的４８．８％，可见青岛市公交线路换乘比较　方便㈨。