网络挖掘中的相关问题探讨

    丁沂

    摘要：当前网络挖掘还处在一个不断发展的阶段，还未形成一个被大众广泛接受的研究框架，关于网络挖掘的主要问题、研究方法、技术和应用相关的研究文献也比较少。文章对网络挖掘领域的研究问题以及未来的研究方向进行了探讨。

    关键词：网络；结构；数据挖掘

    在过去的十几年中，人们对现实世界中表现出的复杂的“连通性”表现出与日俱增的兴趣，这种兴趣的核心是网络。网络是现实事物之间相互关联的一种模式，在很多场合人们都能发现网络的存在。首先，人们身在其中的社会网络，它体现了人与人之间的社交联系。这种社交联系的复杂性随着人类历史进程所发生的各种技术进步不断增强，这些技术包括方便人们长途旅行的交通技术、网络通信技术和无线互联技术等。过去半个世纪以来，社会网络在地理上的含义越来越弱化，但在其他方面却变得越来越丰富。人们使用的信息也有类似的网络结构，它们的复杂性也在不断增加。大量信息源对少数高质量信息提供者支配信息生产的传统局面形成了冲击。在这样的环境中要理解任何一条信息，不仅要看其内容本身，还要理解其引用其他信息的方式。社会的技术系统和经济系统也日益依赖于复杂的网络。这使得人们越来越难以推理它们的行为，对它们进行调整的风险也越来越大。网络使人们的技术和经济系统容易受到很大的影响，这种影响会通过网络结构传播开来，有时局部问题会导致全局的崩溃。在某些情况下，网络研究的重点通常不在网络结构本身，而在于它所带来的另一种复杂性，即网络作为一个大型的、由各种关联成分构成的总体，以一种难以预知的方式，反作用于中央权威行动的复杂性。

    在电子商务、市场营销、知识管理、Web挖掘等众多领域，人们在做决策的时候往往需要考虑各种类型的网络。从20世纪90年代末开始，大量关于新的网络模型、技术和应用的论文发表在《自然》《科学》以及很多高级别的学术期刊上。与此同时，FaceBook和MySpace等社交网络站点也随着这股潮流越来越流行，社会网络数据挖掘，也可以简称为网络挖掘受到越来越多研究者的关注。网络数据挖掘和传统的数据挖掘有着本质的区别，比如关联规则挖掘旨在从单个数据对象中提取模式，而网络挖掘是从Internet，WWW和社交网络等网络数据中提取不同对象之间的关系，即有价值的结构模式。

    1网络挖掘中的主要研究问题

    网络挖掘主要包括静态结构挖掘和动态结构挖掘两个方面：静态结构挖掘关注网络的一个快照，在某一个指定的时间点观测到的节点和连边；与静态网络挖掘相比，动态网络挖掘基于多个不同时间点的网络数据分析网络。静态分析关注某一个观测时间点网络节点和连边配置的结构规则；动态分析旨在发现网络随时间变化的模式。总而言之，静态分析的重点在网络结构，动态分析的重点在于网络演化的过程和机制。

    1.1静态结构挖掘

    静态网络结构挖掘有3个主要的研究问题：（1）如何定位网络中的重要资源？（2）如何降低网络的复杂性并生成网絡的“最大图像”？（3）如何从网络中提取拓扑属性？

    1.1.1定位网络资源

    网络可以看作是资源的集合，网络中重要资源包括重要的节点、连边以及网络中的关键路径。例如在WWW网络中，Web文档的内容就是WWW网络中的重要资源，用户在WWW网络中搜索与他们需求匹配的高质量的Web页面。网络中的用户、文档、关系以及通信渠道对于一个网络的功能至关重要。重要资源定位技术在网络科学中得到广泛的应用，例如：在Web上搜索高质量的页面；在Internet上定位某些关键的电缆，这些电缆的故障会降低互联网的健壮性；在协作网络中发现解决某些特定问题的专家等等。

    1.1.2降低网络的复杂性

    由于网络由大量节点和连边组成，因此网络显得非常复杂。随着网络规模的不断扩大，理解网络的结构也变得越发困难。例如：当一个市场管理者面临着一个由成千上万的消费者组成的网络时将变得手足无措；一个研究者试图理解一个不太熟悉学科中的引文网络所包含的智能结构也是一件困难的事情。因此，研究者需要从复杂网络中提取“最大图像”，从而降低网络的复杂性，并确保这个“最大图像”与原来网络具有一致的结构。为了达到这个目的，网络首先被分割为若干子群，每个子群包含若干节点和连边，从而提取子群之间的关系。网络分隔技术在Web社区发现、引文网络中的主题发现，犯罪网络中的主要成员发现等领域也得到了广泛的应用。

    1.1.3提取网络拓扑属性

    近年来，对大规模网络的拓扑属性的研究受到越来越多研究者的关注，很多因素导致了这种趋势。首先，计算机不断提高的计算能力让大规模网络数据的搜集和分析成为可能。例如，对Web网络研究需要处理的节点多达上百万。其次，近年来小世界和无标度网络模型的流行也激励了研究者去发现现实世界中存在的统一的组织原则。最后，FaceBook，MySpace等在线社会网络站点的流行促使研究者去研究这种网络现象。

    静态结构挖掘提供了一个发现网络结构模式的方法，但是网络不是静态的而是不断变化的，如何揭示网络的动力学以及网络的演化机制导所致的拓扑结构是动态结构挖掘领域的研究重点。

    2动态网络挖掘

    回顾人类历史的长河，任何一次传染病的大规模流行，都是人类文明进程带来的，反过来，每一次大规模的传染病又对人类文明本身产生深远的影响。人类社会的日益网络化促进了现代公共卫生体系的不断完善，以努力减少疾病的威胁，但另一方面，这种网络化进程使得人员和物资的流动日益频繁和便捷，反过来加速了传染病的快速扩散。在技术网络领域，如果不加干预，整个Internet可以在几十秒至几十分钟内因为计算机病毒的蔓延而完全崩溃。一次次严峻的考验让人们不得不重新考虑如下问题：在拥有发达医疗水平和生物技术的现代公共卫生体系的今天，为什么新的病毒还能迅速蔓延？为什么在每年投入了巨额费用的防止病毒措施之后，Internet上计算机病毒的传播仍然防不胜防？人们可以将生物种群和计算机网络中的个体定义为节点，而将个体之间存在的关联途径定义为节点之间的边。迅速发展的复杂网络理论正有效地增进人们对爆发大规模生物和计算机病毒流行的传染机制的认识。研究表明，当网络规模无限增大时，无标度网络的临界值趋于零，即使是很微小的传染病源也足以在庞大的网络中蔓延。

    网络是在不断变化的，新节点可能会加入系统，老节点可能会被移除。另外，新的连边可能会出现在以前并不相连的两个节点之间，节点之间原有的连边可能在某个时刻崩溃。因此，理解网络的演化机制和动力学至关重要。网络的演化机制会导致某种类型的网络拓扑结构的形成，从而直接影响系统的功能。动态网络挖掘主要包含两个研究问题：（1）如何描述网络动力学；（2）如何对网络建模以及预测网络动力学。网络动力学的描述方法通常相对简单，通常都是利用在一段时间内观测到的拓扑统计量的变化，例如网络平均度和聚集系数的变化。

    网络结构动力学的建模和预测是一个极具挑战性的问题。由于大多数网络都呈现出无标度特征，当前大多数研究都关注在无标度网络的演化过程。其中关键的问题是究竟什么机制导致了网络中节点度的幂律分布。生长、偏好依附、竞争、独立偏好等机制通常用来解释大量真实网络中无标度拓扑特征的形成。

    3结语

    网络挖掘未来研究主要包括理论研究、技术研究和实证研究3个方面。在理论研究方面，随着网络结构挖掘研究的日益成熟，需要建立一个更加综合的研究框架，新的研究问题、技术和发现可以融合到这个框架里面，例如，网络中信息、创新和疾病的传播都是非常具有前景的研究领域。另外在网络演化研究方面，需要开发新的模型从而揭示网络演化的机制，这些研究对网络理论的建立极具价值。在技术研究方面，未来的研究将瞄准网络结构模式挖掘新技术和新方法的开发。传统的网络分隔方法仍然缺乏有效性，这种方法从大规模网络中提取子结构的能力是非常有限的。在实证研究领域，网络结构挖掘在支持知识管理和决策应用方面的意义和影响仍然需要被验证，大量实证研究也需要被用来验证和解释这些新的结构挖掘技术和方法。