基于有向关联势的关键结点发现方法
陈新泉*
作者简介：陈新泉，(1974-)，男，副教授，主要研究方向：数据挖掘、模式识别. E-mail: chenxqscut@126.com
（重庆三峡学院计算机科学与工程学院，重庆 404000）
5 摘要：为解决重要网站发现、关键文献推荐、热点人物评选等一些应用问题，本文提出了一
种基于有向关联势的关键结点发现方法。这种方法的第一种形式是基于δ近邻有向关联势的
关键结点发现算法(算法1)，该算法形式具有比PageRank 方法简单、时空代价小的优点。
这种方法的第二种形式是基于全局有向关联势的关键结点发现算法(算法2)，该算法比
PageRank 方法更为简洁。为便于对这种方法进行理论上的收敛性分析，在马尔可夫链理论
10 的指导下，给出了第二个算法形式的修改版本(算法3)。通过理论分析得知，算法3 的迭代
过程可形成一个能收敛到稳态向量的马尔可夫链。通过1 个人工构造的例子和1 个UCI 数据
集的仿真实验，验证了这3 个算法形式都是收敛的。为进一步发掘出这种方法的应用价值，
最后给出了几点较有价值的研究展望。
关键词：有向关联相似性度量；δ近邻势；马尔可夫链
15 中图分类号：TP181
Key Node Discovery Method Based on Direct-Relational
Influence
CHEN Xinquan
20 (School of Computer Science & Engineering, Chongqing Three Gorges University,
ChongQing 404000)
Abstract: In order to find important sites, recommend key literature, select hot people, and some
other application problems, this paper presents an key node discovery method based on
direct-relational influence. The first form of this approach is a key node discovery algorithm based
25 on δ near neighbor direct-relational influence (Algorithm 1), which is more simple and efficient
than PageRank algorithm. The second form of this approach is a key node discovery algorithm
based on global direct-relational influence (Algorithm 2), which is more concise than PageRank
algorithm. To find some theoretical convergence analysis, we give a modified version of the
second algorithm (Algorithm 3) according to Markov chain theory. From some theoretical analysis,
30 we know that the iterative process of Algorithm 3 can form a Markov chain which will converge
to a steady vector finally. It is verified that these three algorithms are convergent by an artificial
example and a simulated experiment of a UCI data set. In the end, it gives a more valuable
research prospect to further explore the application value of this approach.
Keywords: Direct-Relational Similarity Measure; δ near neighbor influence; Markov Chain
35
0 引言
PageRank [1, 2, 3]是Google 公司用来标识网页重要性的一种方法。它是一个与查询无关
的静态算法，可通过离线方式来计算所有网页的PageRank 值。虽然这种算法可有效地减少
在线查询时的计算量，但它忽略了主题相关性，导致结果的相关性和主题性降低。
40 与PageRank 的不同的是，Hilltop 仅考虑专家页面的链接，忽略了大量非专家页面的影
响，所以它不能反应整个Internet 的民意。当没有足够的专家页面存在时，可能会返回空的
结果，所以Hilltop 更适合于对查询结果进行求精排序。
除了上面的网页排序问题，其它领域中的一些待分析问题也具有类似的数学模型，如文
献引用分析，人际关系分析等一些具有实用价值的应用问题。
45 本文第2 节列出了几个基础定义。为有效地求解上述具有广泛应用背景的数学模型，在
 第3 节提出了一种基于有向关联势的关键结点发现方法。这种方法具有2 种典型的算法形式，
即基于δ 近邻有向关联势的关键结点发现算法(算法1)和基于全局有向关联势的关键结点发
现算法(算法2)。在第4 节给出了这种模型及算法的几个应用例子。第5 节通过几个仿真实
验验证了本文所给出的3 个算法形式都是收敛的。第6 节对本文作简要的总结并指出进一步
50 的研究方向。
1 问题描述及相关的定义
1.1 问题描述
设在某m 维向量空间中存在着一个数据点集S={X1,X2,…,Xn}，该空间的距离相异性度量
为dis(·,·)。
55 1.2 基本定义
定义1(对等关联相似性度量)：若数据点集S 中的点Xi 到点Xj 存在着对等的关联关系，
则点Xi 与点Xj 的对等关联相似性度量可定义为：
s(Xi,Xj) = 1/(1 + dis(Xi,Xj)) (1)
式(1)中，dis(Xi,Xj)为该空间中点Xi 与点Xj 的一种距离相异性度量。
60 显然，这种对等关联相似性度量满足对称性。
定义2(夹角余旋相似性度量)：若点Xi 到点Xj 存在着对等的关联关系，则点Xi 与点Xj
的夹角余旋相似性度量可定义为：
s(Xi,Xj) = cos(α(Xi,Xj)) = <Xi,Xj> / (‖Xi‖2 * ‖Xj‖2) (2)
式(2)中，<Xi,Xj>为点Xi 与点Xj 的标量积，‖·‖2 为向量的模。
65 显然，这种夹角余旋相似性度量满足对称性。
定义3(有向关联相似性度量)：若点Xi 到点Xj 存在着关联指向关系，则点Xi 到点Xj的
有向关联相似性度量可定义为：
s<Xi,Xj> = u<Xi,Xj>/(1 + dis(Xi,Xj)) (3)
式(3)中，u<Xi,Xj>为点Xi 到点Xj 的关联度，其取值范围一般设定为：u<Xi,Xj> ∈ [0, 1]。
70 关联度的一种最简单的取法是，若点Xi 到点Xj 存在有向关联关系，则设定u<Xi,Xj> = 1；
若点Xi 到点Xj 不存在有向关联关系，则设定u<Xi,Xj> = 0。
显然，这种有向关联相似性度量一般并不存在对称性。
定义4(δ 近邻有向关联点集)：数据点集S 中的点P 的δ 近邻有向关联点集δ(P)定义为：
δ(P) = {X | δ < s<X,P> ≤ 1, X∈S} (4)
75 式(4)中，s<X,P>为数据点集S 中的点X 到点P 的有向关联相似性度量。
为便于讨论，可采用一个有向图模型来描述数据点集S 中的这种有向关联关系。
定义5(δ 近邻有向关联图)：δ 近邻有向关联图Gδ(S)定义为：
Gδ(S) = (V, E) (5)
式(5) 中， Gδ(S) 的顶点集为V=S={X1,X2,…,Xn} ， 有向边集E={<Xi,Xj>|Xi∈δ(Xj),
80 Xj(j=1,…,n)∈V}。其中，有向边<Xi,Xj>的边权重设定为点Xi 到点Xj 的有向关联相似性度量
s<Xi,Xj>，即：w<Xi,Xj> = s<Xi,Xj>。
在S={X1,X2,…,Xn}中，根据事先设定的距离相异性度量d(·,·)和已知的有向关联指向关
系，可构造出每个点Xi(i=1,…,n)的δ 近邻有向关联点集δ(Xi)，然后再根据δ(Xi)(i=1,…,n)就
可构造出Gδ(S)来。
 δ(85 Xi)(i=1,…,n)的一种省时省空间的存储结构是数组式邻接表结构。δ 近邻有向关联图
Gδ(S)的出向邻接表存储结构是这种数组式邻接表结构的逆向存储结构，即δ(Xi)(i=1,…,n)的
这种数组式邻接表结构与Gδ(S)的入向邻接表存储结构所存储的信息完全相同。
定义6(δ 近邻有向关联势)：点X 的δ 近邻有向关联势定义为：
Σ
∈
= < >
( )
( ) ,
P X
I X s P X
δ
δ (6)
90 式(6)中，s<P,X>为S 中的点P 到点X 的有向关联相似性度量。
定义7(全局有向关联势)：点X 的全局有向关联势I(X)定义为：
Σ∈
= < >
P S
I (X ) s P, X (7)
2 基于有向关联势的关键结点发现方法
2.1 基于δ 近邻有向关联势的关键结点发现算法
95 2.1.1 算法描述
算法名称：基于δ 近邻有向关联势的关键结点发现算法(算法1)
输入：数据点集S={X1,X2,…,Xn}，设定的相异性度量dis(·,·)，先验的关联度值u<·,·>，
关联关系阈值δ，势阈值Δ。
输出：数据点集S={X1,X2,…,Xn}的关键结点。
100 步骤：
Step1. 根据设定的相异性度量dis(·,·)，关联关系阈值δ，定义3 和定义4，构造出每个
点Xi(i=1,…,n)的δ 近邻有向关联点集δ(Xi)。
Step2. 初始化每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)。一种初始化方法为：
SumI ← 0;
105 //计算每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)。
for(i = 1; i ≤ n; i++)
{
Iδ(Xi) ← Σ
∈
< >
( )
,
P Xi
i s P X
δ
;
SumI ← SumI + Iδ(Xi);
110 }
/* 如果有先验信息，Iδ(Xi)可设置其它的初始值。这里的有向关联相似性度量s(·,·)可根
据定义3 来计算，也可根据具体应用实例来确定。 */
//归一化每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)
for(i = 1; i ≤ n; i++)
115 {
Iδ(Xi) ← Iδ(Xi) / SumI; (8)
}
Step3. 对每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)，在其δ 近邻有向关联点集δ(Xi)
范围内，进行迭代更新操作。具体操作步骤为：
120 do{
//迭代更新每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)
for(i = 1; i ≤ n; i++)
 {
Iδ(Xi) ← Σ( )
∈
< >
( )
( ) * ,
P Xi
i I P s P X
δ
δ ; (9)
125 /* 也可将上面的更新公式修改为带衰减因子α∈[0, 1]的迭代更新公式，即为：Iδ(Xi) ← α
* Σ( )
∈
< >
( )
( ) * ,
P Xi
i I P s P X
δ
δ + (1 – α) * Iδ(Xi); */
}
//归一化每个点Xi(i=1,…,n)的δ 近邻有向关联势Iδ(Xi)
SumI = Σ=
n
j
j I X
1
( ) ;
130 for(i = 1; i ≤ n; i++)
{
Iδ(Xi) ← Iδ(Xi) / SumI;
}
}while({Iδ(X1), Iδ(X2) , Iδ(Xn)}全大于0，且仍未完全稳定下来);
135 Step4. 将数据点集S={X1,X2,…,Xn}中的δ 近邻有向关联势大于势阈值Δ的数据点判定为
关键结点。
2.1.2 算法的讨论及分析
(1) 算法时空复杂度分析：
在Step1 中，若采用简单的逐一判断构造方法，需要Time=O(n2)，Space=O(n2)。若采
140 用合适的数据结构及改进技巧，可以降低构造δ 近邻有向关联点集的时空代价，具体的方法
及讨论可参见文献[4]。在本文所构造的模型所对应的应用问题中，一般都存在着一些先验
信息(如在文献引用领域、网站链接领域中，可以很容易地获得每个结点的入度和出度数目)。
在这种情况下，该算法就能取得Time=Θ(n+|E|)，Space=Θ(n+|E|)的时空代价。这里的|E|为由
学术论文网Tag：代写论文 代写代发论文 论文发表 代发论文