基于小世界网络的用户位置行为兴趣模型*

张少中，俞东云

（浙江万里学院电子信息学院 宁波315100）

1引言

在商务活动中，对顾客而言，总是希望花最少的时间和精力购买到自己最满意的商品或服务；对商家和企业而言，总是希望投入最少的花费了解并满足用户的需求。通过了解用户的位置信息，分析用户的位置变化习惯和特征，并与位置资源内容信息结合起来，可以挖掘并发现用户的服务需求，为商家的定向广告和定向服务提供有利支持。位置行为分析是网络结构挖掘，它不同于传统的数据挖掘中基于个体目标数据模式抽取的方法，而是基于目标之间的关系进行模式挖掘[1,2]，这种基于对象间的关系进行模式挖掘的目的是在目标网络中提取正确的、新颖的、有用的结构模式。结构模式指的是网络结构中的蕴涵的规律、内在机制、变化趋势等知识。

网络结构挖掘方法是这类研究中最受关注的问题，其中小世界网络模型[3]是Watts和Strogatz在1998年提出的基于人类社会关系分析的网络模型，用于描述具有相互作用的个体所构成的社会或者生态系统，小世界网络已被成功应用于说明各种社会网络结构。Batul J Mirza提出了一种“跳转连接”的图模型推荐方法，采用小世界网络模型描述结点间的关系，利用“jumping connections”将图中具有相似偏好的用户连接成一个有向边，该有向边所指用户的偏好就是连接该用户的前一个用户推荐集[4]；Adriana Iamnitchi等提出了一种基于小世界网络的文件共享模型，该模型能够根据用户的兴趣分析共享文件的关系，提出一种表示用户感兴趣的数据共享图[5]。Kashif Ali提出了一种基于小世界网络的网格资源发现方法[6]；窦文采用一种全局可信度的方法进行P2P网络拓扑结构的构建[7]；郑耿忠等将小世界网络引入无线传感器网络分析，研究无线传感器网络拓扑结构，发现其中隐藏的规律从而有效提高网络性能[8]；梁活民等结合Cayley图和小世界网络，采用基于群论中的半直积方法构造了一个具有良好性质的静态互连网络[9]。

本文采用小世界网络模型进行位置资源结点特征分析，对用户的位置行为路径和特征进行描述和分析，获得用户所处的地理位置、行为路径特征与当前位置资源直接的相似性，并将用户位置信息看作一个树根，将位置资源内容看作结点，采用改进的最短路径算法计算根结点到各个结点的路径长度，从而分析出用户最感兴趣的位置资源结点。

2 结点推荐度与位置资源结点网络结构

小世界网络是一种无向无权网络，其网络中的连接边只有两种情况，例如，对于任何两个结点之间是否存在邻接边可以表示为0、1两种情况，其中0为两结点之间不存在边；1为存在边。但是许多真实网络中结点之间的联系不能单纯地仅用存在和不存在来表示。在与商务信息相关的位置服务中，在某一位置或者区域范围内的商务信息结点的关联程度差异很大，采用小世界网络模型的无向无权图难以表示位置资源结点之间的联系。本文在小世界网络模型中引入推荐度方法，用于建立小世界网络的边连接权值，构建位置资源网络，从而更准确描述位置信息资源之间的关联程度。本文采用局部推荐度与全局推荐度描述结点间的关联程度。

假设整个位置资源网络为N，N中包含的资源结点集合为O，O由n个不同的资源结点构成，即：O={o1,o2,o3,…,on}。采用P2P网络可信度的方法，位置资源网络可定义局部推荐度和全局推荐度。

定义1（局部推荐度）设pi,j表示结点i对结点j的推荐度，该推荐度取决于结点i与结点j的交互历史，有其中Ii,j为结点i与结点j在某固定时间τ内产生直接交互的次数，具体可以是用户位置从结点i直接到达结点j的次数，Si,j为在结点看来交易成功的次数，其中，当Ii,j=0 时，pi,j=0。

定义2（全局推荐度）在网络N中，结点i对于任意结点j的全局推荐度为Tj，设：

其中N为网络规模，pi,j为局部推荐度，Kj为与结点j发生关联的结点集合，当Kj=覫时，即所有结点均不与结点j发生关联时，此时的结点j的全局推荐度为0。

3 基于小世界网络的用户位置行为分析与聚类

3.1 用户位置行为分析小世界网络的路径长度和聚类系数

小世界网络包括了两个重要的参数，平均路径长度和聚类系数。其中平均路径长度用来度量整体网络结点之间关联的程度和有效性，聚类系数用来表示邻近结点之间的紧密程度。用户的位置行为分析是通过用户所处位置和路径来搜索用户到其位置资源结点的路径权值，进而分析用户可能感兴趣的位置资源结点。路径权值是关联用户兴趣和位置资源最基本的组成元素，就是推荐度值。用户位置结点与位置资源结点的路径权值记为w，用来描述用户位置结点vi和位置资源结点uj间的关联程度。w(vi,uj)的定义如下。

定义3 用户位置结点vi和位置资源结点uj间的路径权值为：

其中，gj(Γ*)为推荐度。

定义4 网络中结点之间的路径长度用路径权值的倒数表示，即：

当 w(vi,uj)=0时，L(vi,uj)=∞。

3.2 用户位置行为小世界网络聚类分析算法

给定规则网络为G=(V,E)，网络度数为k，V为结点集合，E为边集合，其子图是一个小世界网络，该子图可以通过删除规则网络中的某些连接边的方法得到，得到的网络能够使函数f=aL+bC|m最大化，其中，a和b为常数，m为整数,L和C分别是特征路径长度和聚类系数。给定用户位置信息并确定结点属性集合，由于关于小世界网络的优化问题是一个NP难题，需要在聚类系数和路径长度间进行平衡处理。将该位置结点作为用户兴趣结点，采用的小世界网络聚类算法如下。

算法1 小世界网络的用户位置行为聚类

（1）重复删除1条边，删除后可以使得函数f最大，直到共有m条边被删除。

（2）加入1条边，使得函数f最大，并进行调整，如果加入的边与删除的边相同，则转到（3）。

（3）删除 1 条边，使得函数 f最大，则转到（2）。

（4）输出当前满足fmax的参数L和C。

这样获得的网络即为满足条件的小世界网络，其结点集合为：V′={vi,ui|vi,ui∈V∧L(vi,ui)≤L}。

4 改进的最短路径搜索算法

在位置资源环境中，用户的兴趣对推荐系统来说是未知的，需要通过搜索聚类子空间所有位置资源的特征才能给出用户可能感兴趣的商品，因此，本文以经典的Dijltstra算法为基础，通过改进其搜索策略，提高其搜索速度。使用一种最短路径根树算法对经典Dijltstra算法进行改进，该算法构建了一个最短路径根树，在最短路径根树中所包括的结点就是已经搜索到最短路径的那些结点和路径。在该根树中，每个结点都有一个父亲结点，表示为Pa(u)，使用一系列的标记记录从结点u到根的路径，记为SP。在搜索过程中，首先从候选结点集合中选择与源点距离最小的一个结点，将其加入根树中，重复这个过程，直到所有的结点都包含在根树为止。这样在这个根树中，所有的源点到其他结点的最短路径就都搜索到了。改进的最短路径算法如下。

算法 2 选择一个结点vi作为树Tree的根结点s，对于每一个SPk(k

（1）s→hl路径在 SPj上，则将该路径融入 s。

（2）hl是 SPk的中间结点，而且也在 SPj上，则删除 hl，将其父结点和子结点连接。

（3）hl→t路径在 SPj上，则将该路径融入 t，直到所有的SPk(k

（4）除了结点s和uj外，没有其他结点在另一条路径上，则得到的路径为最短路径D。

5 实验与分析

5.1 实验设计

通过对Movieslens数据集[10]改造，令其中的电影数据表示位置资源结点，通过用户的打分建立电影资源的小世界网络，利用部分用户打分作为测试数据，即为用户位置结点进行模型和算法的评价和测试。本文选择的Movieslens兴趣网络包括943个用户对1 682个电影的100 000条打分评价，实验中使用900个用户对1 682个电影的50 000条评价进行模型训练，使用其他用户的1 000条进行验证测试。

算法1实验结果见表1。

算法2实验中，用户兴趣的有效性分析采用准确性和时间效率值表示。当用户的兴趣结点同时在推荐集合和测试集合中的时候，表明该预测是正确的；当用户的兴趣点在推荐集合中，但是不在测试集合中的时候，表明该预测是错误的；当用户的兴趣点不在推荐集合中，但是却在测试集合中，表明该预测也是错误的。

表1 不同参数下模型错误边的数目

本文采用经典最短路径算法与本文提出的改进的最短路径算法进行比较，为简化实验，本文采用全样本空间搜索方法，没有限定某一聚类子空间，对算法的执行没有影响。其精确度和时间分析如图1和图2所示。

5.2 性能分析

从表1的实验统计结果可以看出，本文提出的小世界模型及其聚类算法可以实现用户的位置行为分析和聚类，在网络结构中多余的边数和缺失的边数相对于网络复杂度来说在可以接受的范围内，并且可以通过对参数的调整提高其精度，减少错误的边数和缺失的边数的数目。当参数选择合适的情况下，例如本文中当参数a、b和m值分别取 0.4、0.6、100 和0.3、0.7、200 时，算法具有较好的精度。

图1 两种算法的精确度比较

图2 两种算法的时间复杂度比较

从图1的实验结果可以看出，改进的最短路径算法可以正确推荐用户基于位置兴趣结点，并较经典的最短路径算法具有一定程度提升，其准确率根据测试集合样本数目的不同会有小的波动，其准确率基本在80%左右，可以满足目前商务应用需求。从图2可以看出，改进的最短路径算法较经典最短路径有较大改进，这种情况随测试集样本数量的增加变得尤为明显，当样本接近1 000个时，经典最短路径算法等待时间较长。

6 结束语

本文引入了一种小世界网络模型用于用户基于位置的行为分析，可为商务活动提供有价值的个性化服务。采用推荐度计算方法和小世界网络进行用户行为属性聚类，将资源结点推荐转化为路径搜索问题，通过将用户位置作为一个树根，把位置资源作为用户的兴趣结点，采用改进的最短路径算法计算根结点到各个结点的推荐度，从而给出用户最感兴趣的位置资源结点。实验结果表明，采用该方法建立的用户位置行为兴趣模型能够很好地描述用户基于位置的兴趣和意愿，算法在结果精度和计算时间上都具有良好的性能。

1 Joseph A Cazier,Benjamin B M Shao,Robert D St Louis.Sharing information and building trust through value congruence.Information System Front,2007(9):515～529

2 Culnan M J.Mapping the Intellectual Structure of MIS,1980-1985:a co-citation analysis.MIS Quarterly,1987，11(3):341～353

3 Watts D,Strogatz S.Collective dynamics ofsmall-world networks.Nature,1998

4 BatulJ M,Benjamin J K,Ramakrishnan N.Studying recommendation algorithms by graph analysis. Journal of intelligent information systems,2003,20(2):131～160

5 Adriana I,Matei R,Ian T F.Small-world file-sharing communities.INFOCOM,2004

6 Ali K,Datta S,Aboelaze M.Grid resource discovery using small world overlay graphs.Proceedings of the 18th IEEE Canadian Conference on Electrical and Computer Engineering,2005

7 窦文.信任敏感的P2P拓扑构造及其相关技术研究.国防科技大学博士学位论文，2003

8 郑耿忠，刘三阳，齐小刚.基于小世界网络模型的无线传感器网络拓扑研究综述.控制与决策，2010,25(12):1 761～1 768

9 梁活民,肖文俊.一种具有小世界网络特征的常数度结构化覆盖网络.计算机学报,2010,33(9):1 541～1 547

10 MovieLens.http://movielens.umn.edu