基于复杂网络的知识网建模研究

文章编号：MC - 2008-03

收稿日期：2008-05-26

出版日期：2008-06-30

© 2008 MC– 厦门大学信息与技术学院

基于复杂网络的知识网建模研究

范彦静，王化雨

（山东师范大学信息科学与工程学院，山东济南 250014）

fandongjing000@163.com

摘要：随着人类社会进入知识经济时代，对知识学习、知识管理等领域都有了持久深入的研究，而如何对知识进行识别、获取、开发、分解、储存、传递，也成为了重点的研究方向。知识网的创建更好的解决了这个问题。知识网由知识点组成，每个知识点又由若干个更小的知识点组成，知识点之间又存在着联系。如何研究知识网中知识点的组成呢？本文利用了复杂网络中的社团理论对知识网进行了建模;并用复杂网络建模中的基于无权网络的BA模型，对知识网中的节点及节点的关系进行了详细的分析研究，从而从一个崭新的角度扩展了人工智能的知识表示方法。

关键词：复杂网络；知识网；社团结构

中图分类号：TP391文献标识码：A

Knowledge Network Modeling Based on

Complex Networks

FAN Yan-jing, WANG Hua-yu

(School of information Science &Engineering, Shandong Normal University, Jinan 250014, China)

fandongjing000@163.com

Abstract: As human society entered the era of knowledge economy, lasting in-depth studies have been done to knowledge learning, knowledge management, and other fields. How to identify, acquire, develop, decompose, store, and transmit knowledge has become the focus of research. The creation of knowledge network supplies a better solution to this problem. Knowledge network is composed of knowledge points. Each knowledge point is composed of several even smaller knowledge points, while relations exist between them. How to study the composition of the knowledge networks? This article uses the theory of community structure in the complex networks to build the model of knowledge network，and then use theory of complex networks of the BA model to build a knowledge network model, and to analyze the knowledge nodes in the network and the relationship between them. Therefore, it extends the notation of artificial intelligence knowledge from a new perspective.

Key words: complex networks; knowledge network; community structure1 引言

人类社会正进入知识经济时代，知识化、网络化正成为现代经济发展的重要特征。知识的研究具有悠久的历史传统，但是随着知识经济的发展和IT的广泛应用，知识学习、知识管理等领域有了持久深入的务实研究，尤其在90年代中后期以来，知识管理正在朝网络化方向发展，而知识网的创建可以更好的对知识进行识别、获取、开发、分解、储存、传递。知识网可由知识点组成，每个知识点又由若干个更小的知识点组成，知识点之间又存在各种各样的联系，最终可扩张成由知识点构成的网络，称之为知识网。怎么研究这些知识网络中的知识点的组成？由于一个大知识点中的小知识点之间联系是相对紧密的，而大知识点之间联系是相对稀疏的，鉴于此，我们可以利用复杂网络中社团的理论，把知识网中的大知识点称为社团，更小的知识点可以称为社团的结点，因此这样，就可以用社团结构中的理论来对知识网进行建模分析，从而可以更好的用于日常学习中的知识获取和分析。

2 复杂网络简介

任何一种网络都可以看作是由一些节点按某种方式连接在一起而构成的一个系统，曾经关于网络结构的研究常常着眼于包含几十个到几百个节点的网络，而近几年关于复杂网络的研究中则常常可以见到上万个节点的网络，网络规模尺度上的改变也促使网络分析方法做相应的改变，而复杂网络是近年来随着网络规模、理论和计算机技术的飞速发展而出现的一个新的研究方向。它的出现不仅顺应了现代科技的发展趋势，而且反映了在以信息科学为支柱的新世纪中，各学科理论及应用交叉、渗透和融合的发展趋势。在研究方面具有开创性的是1998年Watts 和Strogatz[1]引入小世界模型描述从完全规则网络到完全随机网络的转变，小世界网络既有与规则网络类似的集聚特性，又具有与随机网络类似的较小的平均

路径长度；1999年Barabasi 和Albert[2,3]指出许多现实复杂网络的度分布遵循幂律分布

()r p k ck−

=

，

其中r与网络的规模无关，称为无尺度网络。无尺度特性使得现实网络系统的整体（真实网络具有“小世界”效应和“无标度”特性），开创了复杂网络的新纪元，将复杂网络的研究推向了一个全新的领域。

对复杂网络的研究重在其统计性质，对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步【4】。

2.1 平均路径长度（The Average Path Length）

网络研究中，一般定义两节点间的距离为连接两者的最短路径的边的数目，网络的直径为任意两点间的最大距离，网络的平均路径长度则是所有节点对之间距离的平均值，它描述了网络中节点间的分离程度，即网络有多小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多，称之为小世界效应。

2.2 成团系数（The clustering coefficient）

成团系数c用来描述网络中节点的聚集情况，即网络有多紧密，比如在社会网络中，你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友。其计算方法为假设节点通过k条边与其它k个

节点相连接，如果这个节点都相互连接，它们之间应该存在

(1)/2

k k−

条边，而这k个节点之间实际存

在的边数只有E的话，则它与

(1)/2

k k−之比就是节点的成团系数。网络的成团系数就是整个网络中

所有节点i的成团系数的平均。显然，只有在全连通网络中（每个节点都与其余所有的节点相连接），成团系数才能等于1，一般均小于1。在完全随机网络中，c∝1

N−。然而实证结果却表明大部分大规

模真实网络中的节点倾向于聚集在一起，尽管成团系数c远远小于1，但都远比

1

N−大。

2.3 度分布（The degree distribution）

图论中节点i的度k为节点连接的边的总数目，所有节点i的度k的平均值称为网络的平均度，定

义为。网络中节点的度分布用分布函数

()

p k

来表示，其含义为一个任意选择的节点恰好有k条边的

概率，也等于网络中度数为k的结点的个数占网络结点总个数的比值。

2.4 介数（Betweeness）

介数分为边介数和节点介数。节点的介数为网络中所有的最短路径中经过该节点的数量比例，边的介数含义类似。介数反映了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。这对于在网络中发现和保护关键资源和技术具有重要意义。

3 知识网建模研究

知识表示作为人工智能领域的中心课题之一，虽然目前已经有了很多种表示方法，例如产生式、逻辑、语义网络、概念依从、框架、脚本等，但仍然是一个没有完全解决的问题，问题表示的优劣，对求解结果及求解工作量影响甚大。因此我们对知识进一步抽象建立知识网，知识网是一类特殊的概念图，属于语义网络的范畴，考虑到知识网符合复杂网络的定义，因此可以利用复杂网络的理论来研究知识网。

知识网具有社团结构的性质。即知识网络不是由一大批性质完全相同的节点随机地连接在一起的，而是许多类型的节点的组合。相同类型的节点之间存在较多的连接，而不同类型的节点之间的连接则相对较少。我们把满足同一类型中的节点以及这些节点之间的边所构成的子图称为网络中的社团(Community) 。由于社团的定义不一样，社团有可能在另外一种情况下就是结点，即结点和社团是可以相互转化的。社团可以看作是结点的上层结构，这样通过分析看出，知识网的形成是一个搜索活动，它始终在“由上层到下层”和“由下层到上层”两个方向之间交替着。所以我们可以利用具有社团结构的网络建模来对知识网进行建模分析，从一个崭新的角度扩展了人工智能的知识表示方法。

目前，学者们已经提出了一些具有社团结构的网络模型，代表性的模型主要包括以BA模型为代表的基于无权网络的模型。

3.1 BA 模型

BA 模型是复杂网络建模中的一个经典模型，它很好地解释了幂律度分布的产生机理，在复杂网络的文献中受到了极大的关注。

为了解释节点的度幂律分布的产生机理，Barab ási 和 Albert 提出了一个无标度网络模型。他们认为实际网络具有如下两个重要特性：

第一，增长(Growth)特性，即网络的规模是不断扩大的。例如每个月都会有大量的新的科研文章发表，而 WWW 上则每天都有大量新的网页产生。

第二，优先连接 (Preferential Attachment) 特性，即新的节点更倾向于与那些具有较高连接度的节点相连接。这种现象也称为“富者更富(Rich Get Richer)”或“马太效应(Matthew Effect)”。例如，新发表的文章更倾向于引用一些已被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站点。

基于网络的增长和优先连接特性，BA 无标度网络模型的构造算法如下：

1) 拓扑增长：

0m 个节点的网络开始，每次引入一个新的节点并且连到m 个已存在的节点上，这里m ≤0m ；

2) 优先连接：一个新节点与一个已经存在的节点i 相连接的概率

i Π与节点i 的度i k 之间满足线性关系。即 i i j j k k Π=

Σ

经过t 步后，这种算法产生一个有 0N t m =+个节点、mt 条边的网络。

图1 BA 无标度网络的演化（02m m ==）

Fig.1 The evolution process of BA scale-free network （02m

m ==） 图1 BA 无标度网络的演化（m =0m = 2）。初始有两个节点，每次新增加的一个节点按“富者更富”的优先连接机制与网络中已存在的两个节点相连。

对于知识网来说，每个知识点可以分为很多的知识元，而在知识元之间的相互链接就成了知识点，两个知识元只要出现在一个知识点中，它们之间就有边相连，在一个知识领域内，核心词汇的连接度就

虽然与真实的知识网络相比，BA 模型还是有一定的缺陷，但是其后大部分的模型都是在 BA 模型上作了各种扩展和变型，以改变模型的行为或使其更能表现发生在实际网络中的过程。

4 结束语

现有的任何一个网络模型还不能完美地刻画具有社团结构的知识网的特征。鉴于此，有必要从实际知识网络的统计特性出发，综合具有社团结构的网络建模的成果，对知识网的建模进行更深入的研究，提出一种知识网络模型，并能较好的刻画网络的基本特性，包括平均集聚系数、社团的数目、社团规模分布、边的权值分布（节点的度分布）。

参考文献：

[1] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks [J]. Nature, 1998, 393(6684):397-498.

[2] Barabasi A L, Albert R. Emergence of scaling in random networks [J].Science, 1999, 286(5439):509-512.

[3] Barabasi A L, Albert R, Jeong H. Mean-field theory for scale-free random networks. Physica A, 1999, 272(1-2):173-187.

[4] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006年.

作者简介：

范彦静：（1982－），女，山东菏泽人，硕士研究生，山东师范大学信息科学与工程学院，研究方向为复杂网络。

王化雨：（19—），男，副教授，研究方向为计算机图形学，人工智能。