基于社交网络分析用户访问模式
付玉*
作者简介：付玉，（1988-），女，工学硕士，宽带通信、社交网络分析. E-mail: fuyutju@yahoo.com.cn
（北京邮电大学信息与通信工程学院，北京 100876）
5 摘要：Web 数据中包含了大量的用户浏览信息，如何有效地从其中挖掘出用户浏览兴趣模式
是一个重要的研究课题。本文针对网络截获数据进行Web 挖掘，并使用社交网络分析的方法
分析用户的访问兴趣。首先将Web 数据进行预处理，提取出有效反应用户兴趣的Web 数据。
然后通过聚类的方式根据用户兴趣划分类别。在Newman 的基于局部搜索的快速复杂网络聚
类算法FN 的基础上加入了边的权重的概念。最后依据社交网络分析中中心点的概念，用顶
10 点的度数和顶点的聚类系数来判别每个类别中的关键节点，使用关键节点来代表每个类别的
用户兴趣特点。
关键词：计算机应用；Web 挖掘；社交网络分析
 0 引言
30 伴随着Internet 技术的发展，网络资源同时迅速增长。在庞大的Web 资源中，用户往往
被淹没于其中而难以准确获取到自己所需信息和知识。如何根据用户的不同提供个性化的服
务是Internet 向智能化发展的方向。要实现高效个性化的Web 服务，可以通过访问兴趣将用
户聚类，然后根据不同的用户群的兴趣类别提供量身定制的服务。
在Web 上用户按照自己的兴趣进行访问，这种感兴趣程度可以通过用户在Web 站点上
35 的浏览行为体现出来。通过对具有相似访问兴趣的用户群进行划分，发现用户的类属模式[1]。
通过Web 挖掘可以研究用户的Web 浏览行为，通过分析和研究用户访问情况中的规律，可
以识别电子商务的潜在客户，增强对用户的网络信息服务的质量和交付，并改进Web 服务
系统的结构和性能。聚类结果可以在改进站点结构，提供网页推荐服务以及电子商务中发掘
潜在客户等应用中提供决策依据。
40 本文使用在网络中截获的数据，通过协议分析的方法对数据进行还原并对数据进行预处
理；改进Newman 提出的快速复杂网络聚类算法FN，并将其应用于Web 数据挖掘中；并通
过社交网络分析的方法提取各类别中的关键页面，这些页面将反应某类用户的兴趣偏好。
 1 数据预处理
1.1 数据预处理
45 网络中截获的数据无法直接使用，需要进行预处理。数据预处理的主要目的就是将截获
数据整理成图形数据库，供挖掘阶段使用。首先需要对数据进行净化，删除与事务数据库无
关的数据，包括在传输过程中产生错误的数据以及其他协议如FTP、SMTP 等产生的数据。
然后根据截获的网络数据中的IP 地址识别用户，如果IP 地址不同则认为是不同的用户。最
后使用正则表达式分类网址[2]。以用户为起始节点，以页面为结束节点形成原始数据库。将
50 原始数据库转化为图数据库，顶点代表网址页面，边代表两个网址页面顶点有共同的用户，
边得权重代表共同访问两个网址页面的用户数。
1.2 基本概念
1.2.1 图结构模型
定义1 ： 无向图结构模型。设{ , } 1 2 n V = V V LV 是一非空集合，
E {e e v v v v V} i j i j = = , , , ∈ ，其中i j v ,v 是无序对，并且i j i j 55 ∀e ,e ∈ E,e ≠ e 。称(V,E)
为无向图，记为G(V,E)，V 中的元素为顶点，V 为顶点集， E 为边集[3]。
定义2 ： 带权图结构模型。设{ , } 1 2 n V = V V LV 是一非空集合，
E {e e v v v v V} i j i j = = , , , ∈ ，其中i j v ,v 是无序对，W(E(G)) {w e e E} ij ij = ( ) ∀ ∈ ，
w(eij ) 为边eij 的权重。称G(V, E,W) 为带权图，V 为顶点集， E 为边集，W 为边的权重
60 值集合。
1.2.2 社会网络分析
社会网络分析(social network analysis，SNA)旨在分析社会人物之间的关系和交互，为的
是发现和理解社会结构。现阶段SNA 方法已经被用于研究组织行为，以及组织之间的关系，
计算机之间的通信以及许多其他领域并取得了很好的效果。
G(V, E,W) 表示带权网络， 其中{ , } 1 2 n 65 V = V V LV 为顶点集合，
E {e e vi v j vi v j V} = = , , , ∈ 为边的集合，W(E(G)) {w e e E} ij ij = ( ) ∀ ∈ 为边的权重集合，
定义一下几个网络特征：
顶点的权重度：是指该顶点与其它顶点相关联的边的总权重值。顶点i V 的权重度i W 为
该顶点的临接边得权重值。
= Σ
j
i ij ij 70 W e w
顶点的聚类系数：假设网络中有一个节点i V 与i A 个其它节点相邻，这i A 个节点就称为
节点V 的邻居。显然，在这i A 个节点之间最多可能有( −1) 2 i i A A 条边。而这i A 个节点之
间的边数i E 和最多可能的边数( −1) 2 i i A A 之比就定义为节点V 的聚类系数，即
= 2 ( −1) i i i i C E A A
75 带权网络G 中，如果顶点具有较高顶点权重度即和其他节点有较强的连接强度，或顶
 点具有较高的聚类系数即与之相连的节点之间具有较大的相互连接密度和强度[4]，则认为该
顶点是带权网络G 中的关键顶点，可以用于表示带权网络G 的特征。
1.2.3 网络聚类算法
2004 年，Newman 提出了基于局部搜索的快速复杂网络聚类算法FN。其优化目标是极
80 大化Newman 和Girvan 在同年提出的网络模块性评价函数Q函数。Q函数定义为簇内实际
连接数目与随机连接情况下簇内期望连接数目之差，用来定量地刻画网络簇结构的优劣，一
种计算形式如下：
Σ=
⎥ ⎥⎦
⎤
⎢ ⎢⎣
⎡
⎟⎠
⎞
⎜⎝
= − ⎛
k
s
s s
m
d
m
Q m
1
2
2
其中，k 表示网络簇个数，m 表示网络连接总数， s m 表示网络簇中的连接总数， s d 表
85 示网络簇s 中节点度之和[5]。
一般地，好的网络簇结构对应较大的Q值。候选解的局部搜索策略为：选择且合并两
个现有的网络簇。从初始解开始(每个网络簇仅包含一个节点)，在每次迭代中，FN 算法执
行使Q值最大化的合并操作，直到网络中只剩下一个网络簇。通过这种自低向上的层次聚
类过程，FN 算法的时间复杂性是O(mn)，m 和n 分别表示网络的连接数和节点数。
90 2 带权重的快速复杂网络聚类算法
开始时将图G 中的每个节点为一个社团，即可将网络G 表示为n× n 的对称矩阵E ，
其中元素eij 表示网络中连接两个不同社团的节点的边的权重ij ij Σe w 占所有边的总权重
ΣΣ
= =
n
i
n
j
ij w
0 0
比例的1 2 ，这两个节点分别位于社团i 和社团j ，此时eij + e ji 就是社团i 与社团j 之
间所连接的边的权重在总权重中所占的比例；矩阵中的对角线元素ii 95 e 则等于社团i 内部的边
的权重占总权重的比例，设矩阵中对角线上各个元素之和为Tre = Σi eiiwii ，它给出了网络
中连接某个社团内部各节点的边的权重占总权重的比例；定义每行(或每列)中各元素之和为
= Σ
j
i ij ij a e w ，它表示与第个社团中的页面节点相连的边的权重占总权重的比例。在此基
础上，用下面的式子来定义模块度的衡量标准
Q (e w a2) Tre e2
i
ii ii i 100 = Σ − = −
式中： e2 ——矩阵所有的元素之和。上式的物理意义是：网络中连接两个同社团的节
点的边的权重的比例，减去在同样类别结构下任意连接两个同社团的节点的边的权重的比例
的期望值。如果社团内部边的权重的比例不大于任意连接时的期望值，则有Q = 0 。Q的
上限为1，而Q越接近这个值，就说明社团聚类特性越明显[6]。
105 重复计算当任意两个社团合并后的Q值，每一次都取Q值增加最多的社团i 与社团j 合
并。合并两个社团时Q的改变量可以用
 ΔQ = eijwij + e jiwji − 2aia j = 2(eijwij − aia j )
计算，当取得最大的Q值即ΔQ < 0时停止合并，由此我们获得聚类状况最优时的社团
划分。
110 3 实验结果与分析
想吃采用北京某小区出口截获的网络数据作为分析对象。从网络截获数据中提取http
信息，用IP 地址标识用户，使用正则表达式来合并页面。使用图来表示Web 数据，图G 中
的节点V 代表用户访问的界面， E 代表有共同的用户访问i V 节点(界面i )和Vj 节点(界面
j )， ( ) w eij 代表共同访问i 节点和j 节点的用户数。图G 的顶点数为n ，边数为m 。
115
表1 逐步合并顶点时的Q 值
ID Start Target Q
0 -1 -1 -0. 0168066
1 90 8 -0.00470083
2 60 13 0.00583802
114 44 8 0.712522
115 14 8 0.711815
121 78 8 0.39204
注：逐次合并表中的Start 和Target 顶点直至Q 达到最大值，在本例中Q 在ID 为114 时达到最大值，
此时停止合并得到聚类效果最优的社团结构。
120 将G 中每一个顶点作为一个社团，G 可以表示为n× n 的对称矩阵E ，计算初始的Q
值。计算若任意两社团合并时的Q，逐次选则ΔQ值最大的社团i 与社团j 合并直到所有顶
点合并完或是ΔQ < 0，如表1。
当Q值最大时为效果最优的社团结构，同一社团代表一类用户感兴趣的页面集合。通
过社交网络分析的方法，将社团特性用关键节点表示有助于理解用户兴趣特点。在每个社团
中， 计算其顶点的权重度i W 和聚类系数i 125 C ， 取权重度大于总权重度的1 3 即
i i j ij ij W ≥ 1 3Σ Σ e w 的顶点和聚类系数最大的顶点为社团中的关键节点。关键节点逐次合
并邻接的非关键节点直至社团内部只存在关键节点为止。
具体的算法描述如下：
输入：G(V, E,W)为带权图，V 为顶点集， E 为边集，W 为边的权重值集合。
130 输出：graphml 文件
步骤：
Step1：将G 表示为n× n 的对称矩阵E ，计算初始Q值；
Step2：计算若任意两社团合并时的
While max(ΔQ) > 0 do
135 合并Q值最大的社团i 与社团j ，计算Q值；
Step3：计算各社团顶点的权重度= Σ
j
i ij ij W e w 和聚类系数= 2 ( −1) i i i i C E A A ，取
i i j ij W ≥ 1 3Σ Σ e 和i C 最大的顶点作为关键节点；
 Step4：广度优先遍历图，逐次合并非关键节点；
Step5：生成graphml 文件；
140 4 结论
本文在Newman 提出的快速复杂网络聚类算法引入权重的概念，将其应用于Web 数据
挖掘中得到具有相同访问偏好的Web 用户聚类；聚类之后，通过社交网络分析中判定关键
节点的方式来寻找网址页面，通过这些页面将简明的反应某类用户的兴趣偏好[7]。
学术论文网Tag：代写论文 代写代发论文 论文发表 职称论文发表