WEB站点结构优化仿真

第19卷第20期系统仿真学报@Vol. 19 No.202007年10月Journal of System SimulationOct, 2007WEB站点结构优化仿真刘业政，林文龙，焦宁，姜元春(合肥工业大学管理学院电子商务研究所合肥23000)摘要: WEB站点结构优化技术是解决wwW浏览中搜寻与获取有益信息的困难问题及信息搜寻行为的效率低下问题的有效方法。基于WEB站点的超链体系鲒构特征与网页节点的访问频度值特征，建立了一种站点结构优化的数学模型，其目标是使整个站点具有较小的平均访向代价。分析了站点超链体系结构特征与节点访问频度特征，采用仿真算法分别模拟了WEB站点的超链体系结构与页面节点的访问频度值，并通过量化新增超链接的影响因素设计了相应的站点结构优化方法. .实验结果表明:优化后的站点结构具有较小的平均访问代价。关键词: WEB站点结构优化;超链体系结构;节点访问频度; WEB站点平均访问代价中图分类号: TP393文献标识码: A文章编号: 1004-731X (2007) 20 4685-04Website Structure Optimization Based on SimulationLIU Ye-zheng, LIN Wen-long, JIAO Ning, JIANG Yuan-chun(nstitute of E Business, School of Management, Hefei University of Technology, Hefei 2000, China)Abstract: An efficient method for solving the problem of difficulties in searching for and acquiring useful information andthe problem of low efciency of information foraging behavior is website structure optimization. A mathematics optimizationmodel of website structure based on website hyperlink structure and web page popularity was proposed. The optimizationgoal is to minimize the website average access cost. The feathers of wcbsite hyperlink structure and the feathers of web pagepopularity were analyzed, and a website was generated based on simulation, and the corresponding website structureoptimization method by quantizing the impact of new added hyperlink was proposed. Experiment results show that afteroptimization, the website archives a much smaller average access cost.Key words: website structure optimization; hyperlink structure; page popularity; website average access cost为用户往往需要通过一条花费更多访问代价的路径才到达引言其兴趣目标页面.站点结构优化技术就是通过考虑优化网站wWW浏览中的两个常见问题是:搜寻与获取有益信息信息组织的超链体系结构来使所有的用户都可以以更小的的困难问题及信息搜寻行为的效率低下问题。有益信息搜寻访问代价浏览WEB站点更有效地获取所需的信息。-个结与获取的困难主要根源在于以超链接形式组织的WEB信息构优化的站点，可以减少用户的“无谓”点击行为，从而减体系结构的零乱,这种零乱性使用户不知道当前所处网页节少WEB服务器的请求事务次数，减轻服务器负担，可以使.点的具体位置;不知道怎样才能到达其想要去的兴趣目标页用户更有效地到达其访问的目标页面，节省用户访问时间，面，即www“迷航"。通常迷航的用户在面对众多的超链提高用户对站点的满意度。接选择时会产生--些无益于到达其兴趣目标页面的“无谓”本文采用仿真的方法研究降低WEB站点平均访问代价点击行为，这种“无谓”的点击行为- -方面增加了WEB服的站点结构优化问题:将WEB站点抽象成树结构模型(对站务器负担，另-方面也增加了网络的数据流量,容易造成网点结构的描述建模问题，通常有树(67、 图吲、超图凹等几种络阻塞，导致网络访问速度的下降，从而进一步影响了信息描述方式。由于我们考虑的站点结构优化模型主要刻画的是搜寻行为的效率。对这两个问题很难有-一个完美的解决方案,群体用户从主页出发，以一种自顶向下点击超链接的形式来目前对这些问题的解决采取的方法可以分为三类:搜索引擎搜索到达各自访问目标页面的行为，因此相比较而言，能刻技术:基于WUM(Web Usage Mining)技术开发各种浏览导画站点层次化语义结构的树描述方式更适于对这种用户带航工具; WEB站点结构优化技术1161。有访问目标的站点结构优化问题进行建模)，通过分析模型一般来说，用户与站点的设计开发人员对WEB站点信中网页节点的出度特征与访问频度特征,采用仿真的方法分息组织的超链体系结构存在不同的观点,这种差异通常表现别模拟了WEB站点超链体系结构以及WEB页面的访问频度,并中国煤化工设计了相应的站点结收稿日期: 20608-14修回日期: 2006-10-24构优CNMHG基金项目:国家自然科学基金资助(70672097)作者简介:刘业政(1965-), 男，安徽和县人，教授，博导，研究方向为1问题建模数据挖掘与GDSS:林文龙(1979-), 男，福建龙岩人，博士，研究方向为WEB挖掘:焦宁(1981-), 男，安徽太和人，硕士,研究方向为数据定义1 (WEB站点树结构模型) WEB站点可以表示为一挖捆;姜元春(1980-),男，山东莱西人，博士，研究方向为数据挖掘。●4685.第19卷第20期Vol. 19 No.202007年10月系统仿真学报Oect. 2007棵树T=(V.E),其中V为站点页面集合，E为页面之间的超的幂律性回，Faloutsos 将获取的三个Intermet 快照镜像与幂链接集合。根节点r表示站点首页,对于任意的节点v∈V, .律关系进行了对比，显示出它们的相关系数在96%以上,最其所代表的页面所包含的超链接数目称为节点v的出度,记高能达到9%。WEB冪律规律的一个典型模式是网页节点为8%称出度为0的节点为叶子节点,代表网站的内容节点:出度与其节点等级的幂成比例，即设节点的等级r是按出度称出度大于0的节点为非叶子节点，非叶子节点有两种情降序排列序列中的索引值，则有:况,一是在网站中 只起导航作用而不包含可访问内容的纯导8,=ar,"(1)航节点,二是起导航作用并包含可访问内容的复合节点,视式中a为比例系数，R为等级指数，Faloutsos 的实验结果表复合节点为- -纯导航节点和一个与其所包含的可访问内容明等级指数R -0.82--0.74之间。相对应的内容节点的复合体,记包括复合节点复合体中的内尽管Intemet呈现出的大范围模式规律提供了进行比随容节点在内的所有内容节点的集合为Vco机图更精确仿真WEB站点结构的可能，但据我们所知，这定义2 (节点访问频度)指节点所代表的页面所包含的些大范围模式基本上是从整个WEB拓扑结构方面来研究可访问内容部分被访问的频繁程度。考虑-一个足够长的时的..对于单个WEB站点的超链体系结构，目前并没有一种段，设群体用户对节点v所包含的可访问内容部分的访问次能完全确切的模拟方法。考虑到我们的研究目的及模型的需数为click()， 则节点v的访问频度可以定义为要，这里我们主要考虑利用Faloutsos 的节点出度的幂律模p.=click(1)/Sew click(1).式来仿真站点结构。设站点包含的页面数目IM,非叶子节点定义3(访问代价)用户从根节点r出发,到达其访问目中复合节点所占的比例为B,给定-一个初始的站点页面，通标节点v的最少点击次数为节点v的访问代价,记为C(r,以), .过公式(1)给其分配-一个出度值与相应的子节点页面,再对子或简记为c()。节点页面重复同样的过程，直到获得所需要大小的网站时算定义4(WEB站点平均访问代价)群体用户到达各自访法中止生成站点结构并从中按比例系数β随机抽取一部分非问目标节点的访问代价均值称为站点平均访问代价,可以表叶子节点为复合节点，该仿真过程可以用算法1描述如下。示为C(T)=E p.c(,).算法1 WEB 站点结构仿真算法。定义了WEB站点平均访问代价的概念，我们考虑对输入:网站网页节点数1V,比例系数a, β;WEB站点树结构模型和网页节点的访问频度进行仿真建输出:仿真的站点结构;模，以及降低WEB站点平均访问代价的站点结构优化方法。过程:2仿真建模()初始化网站节点集合V=NULL,边集合E=NULL;(2)初始化网页节点队列Q=NULL;对上述WEB站点结构优化问题进行仿真建模，我们首(3)新建网页节点v=new web page,将v加入队列Q中:先需要知道的是实际WEB站点的超链体系结构规律以及用(4) while队列Q不空户对真实站点的访问规律,由此建立站点超链体系结构数据a) If v的大小已达到M, returm T=(V,E);的仿真算法和站点网页节点访问频度数据的仿真算法,在此b)从队列e中取出一一个新节点v;基础上考虑优化约束条件，对站点结构进行优化。c)按照公式(1)的规律给节点v分配出度值&2; .2.1 WEB站点结构仿真d) Fori=1 to 8,将WEB站点抽象成树结构，直观地可以用随机树产生i)新建网页节点w=new web page;算法来生成站点的超链体系结构。尽管着眼于局部环节，i)V=V Uw, E=E U(,w);Internet呈现出明显的随机性(任意一个主体都可以在iI)将w加入队列Q中:Internet.上创建包含有任意个页面、任意个超链的站点),但iv) If V的大小已达到M, return T=(V,E);近年来的研究表明，Intemet 整体却呈现出一定的大范围模(5)按比例系数β随机抽取-部分非叶子 节点为复合节式规律)，这些规律包括:站点中的网页数量、用户数量点。遵守幂律分布:网站中网页被请求和传送的次数服从Zipf2.2节点访问频度仿真分布:用户的访问步长遵守幂律分布: WEB页面的大小显大量用户对WEB站点的访问是一-种 群体的人类行为，示出重尾分布以及关于WEB结构的幕律模式、小世界模式Zipf指出指导人类行为的一条根本性原则是以最小的代价等。WEB结构的小世界模式表现为Internet的拓扑结构不是换取中国煤化工信息搜寻理论12将均匀的，而是呈现出一个个“小世界”网络，“小世界”网ZipfCN M H G访问行为，假设用户络内部高度聚集，而且整个网络中任意两个节点间的最短距在WEB蹈点时历问行为是一-柙带有历问目的的信息搜寻行离都很短。Faloutsos 则指出，Internet 拓扑结构显示出极强为，并且总是倾向于最大化搜寻活动的获取率，即单位费用●4686●第19卷第20期Vol. 19 No. 202007年10月刘业政，等: WEB站点结构优化仿真Oct, 2007上获得的信息量,由此可以推测WEB页面的访问频度也遵多超链接的做法,将会导致一一些导航页面上的超链接数目太循Zipf分布。Giassman 通过分析300个不同用户对40,000多,使用户在该导航页上正确选中能到达其目标页面的超链个WEB页面的10,000次访问请求,从实验上证明了WEB接的选择困难度增加，也容易导致用户选择-些不能到达其页面访问频度的Zipf分布定律I)。根据Zipf定律，给定一目标页面的超链接，从而给用户的浏览造成更大的不便。下个Zipf分布，在不考虑纯导航节点的情况下，访问频级为i面量化这两个因素，并给出相应的优化方法。的网页节点v的访问频度为:定义5 (超链接)超链接h为二元组h=8penalty(h)={ uchlarn)l3)(3)按照公式(2)的规律给包括复合节点复合体中的内δ,≤&容节点在内的m个内容节点分配访问频度值;式中: 8为预定的选择困难度阈值，children(s)为节 点s的所(4)叶子节点的访问频度为其所代表的内容节点的访有内容子节点集合(与children()不同， 若s为复合节点，问频度;则children(s)不包括复合节点复合体中的内容节点:若s为(5)非叶子节点中复合节点的访问频度值取为复合体内容节点，则children()-null).中内容节点的访问频度值。由此可以得到超链接h的增益计算公式为: .gain(h)=2.3优化求解E P.(t)-c(s)-1)- penalty(h)4)通过上述的WEB站点结构仿真算法与节点访问频度仿真算法，我们模拟了初始的网站链接结构与网站所有的网页在添加超链接的实际优化工作中,通常我们忽略增益值节点访问频度值,对应于这个初始的站点结构,根据定义4,低的超链接,以保证用尽量少的超链接获取尽可能多的增益我们可以求得初始的WEB站点平均访问代价, - -般来说这或是对站点增加的超链接总数做限制,为此我们采取两种优个代价值会比较大，我们考虑对该WEB站点的超链体系结化策略，优化策略之一是设置最小增 益值min gain, 添加所构进行优化。有候选超链接集合中增益值大于min_ gain 的超链接，优化对WEB站点超链体系结构的优化主要有以下几种手策略之二是设置增加的最大超链接总数max_ rumber,依次段:增加新链接、删除已有链接、调整链接的位置或是调整添加增益值最大的前max_ yrumber 个超链接。设采用上述优网页节点的位置。考虑到站点原有的超链导航体系结构对站化策略后在原有的WEB站点超链接体系结构上增加了一-组点老用户的重要性，在进行优化变换降低WEB站点平均访新的超链接集合H,则超链接集合H的增益值可以计算如下:gain(H)=问代价同时,我们希望能够避免破坏站点原有的超链导航体S 2(9)-()-penalb>(H)5)系，因此我们只考虑在原有站点超链体系结构上增加一组合适的超链接来优化站点结构。给定一一个初始的站 点结构及网上式中: penalty(H)= E penaly(h)6)页节点的访问频度值分布,我们的问题是:如何增加- -组合由此可以得到优化后的WEB站点平均访问代价C(7")适的新超链接以期获得最低的WEB站点平均访问代价。为中国煤化工- 般来说增加超链接能减小相应一 部分内容节点的访7)问代价,因此直观的做法是在站点首页上添加指向所有内容YHCNMHG节点的超链接,使站点结构尽可能的扁平化,将能获得最小3实验的网站平均访问代价。但是这种在首页等导航页面中增加过我们在Windows 2000 平台上用MATLAB7.0实现了上●4687.第19卷第20期Vol. 19 No. 202007年10月系统仿真学报Oct, 2007述的仿真工程，对节点数目1V=10000的网站做了仿真实验。现;同时页面的访问频度也会随着时间变化而变化，表现为:实验分两步:首先通过WEB站点结构仿真算法(算法中a随着时间的推移,旧页面的访问频度下降,新页面的访问频度取20, β取80%，等级指数R取-0.82)与节点访问频度仿上升。因此从本质上说，本文建立的WEB站点结构优化模真算法产生模拟的WEB站点结构与网页节点访问频度值，型是一种静态模型，进-步的研究方向是建立一种动态仿真的网站具有1575个非叶子节点与8425个叶子节点,我WEB站点结构优化的仿真模型。们按比例系数β随机的选取了1260 个非叶子节点作为复合参考文献:节点，则包括复合节点复合体中的内容节点在内，仿真的网1] Ramakrishnan Srikant, Yinghui Yang. Mining web logs to improve站结构共有9685 个内容节点，其中访问频度最大的为website organization [CW1 Proceedings of the 10th international0.1025，最小的为1.0583-005, 由定义4可以求得初始的conference on World Wide Web, Hong Kong: ACM Press, 2001:430-437. .WEB站点平均访问代价为3.917;然后分别采用优化策略一[2] John Garofalakis, Panagiotis Kappos, Dimitris Mourloukos. Web Site与优化策略二对站点结构进行优化，图1是优化策略- -的实Opimizatio Using Page Popularity几TEEE Internet Computing验结果，图2是优化策略二的实验结果，实验中选择困难度(S1089 7801), 999 3(4): 22-29.阈值δ取当前站点最大的节点出度值。[3] EdmondH WuMichael K Ng. A Graph-Based OptimizationAlgorithm for Website Topology Using Ineresing Association Rules[CW Proceedings of the Seventh Pacific-Asia Conference onKnowledge Discovery and Data Mining (PAKDD 2003), Scoul, Korea:93.7Springer LNAL, 20:78-19053.64] T Nakayama, H Kato, Y Yamane. Discovering the gap between web3.5634site designers' exectations and users' behavior (C]/ Proc. of the NinthInr1 World Wide Web Conference, Amsterdam: ACM Press, 2000811-822.0.0.15min. gain)20.25[5] Youwei Wang, Dingwei Wang, W H Ip. Optimal design of link图1优化策略- -的实验结果structure for e-supermarket website []. IEEE Transactions on Systems,Man, and Cybernetis Part A: Systems and Humans (S0018-9472),2006, 36(): 38-355.56)] Eleni Chitopoulou. Techniques and Metrics for Improving WebiteStructure [CW www 2003, Budapest, Hungary: ACM Press, 2003.[门] Nan Liy, Cristopher C Yang. Exracting a websie's conteat stucturefrom its link structure [CV Proceedings of the 14th ACM intermatioualconfrence on Information and knowledge management, Bremen,155101520253035404550Gemany: ACM Press, 2005: 345-346.max Juomber] Mchler Alexander, Dehmer Matthias, Gleim Ridiger. Towards图2优化策略二的实验结果Proceedings of the 4th Intermational Workshop on Innovative Internet从图1和图2可以看出，增加max yrumber 与减小Computing Systems (2CS 04). LNCS 3473. Berlin/Heideberg:Springer, 2004: 136-150.min. gain都能降低站点的平均访问代价,另外还可以看出初[9] Michalis Faloutsos, Petros Paloutsos, Chnistes Faloutsos. On始添加的超链接的增益比较显著,站点管理员可以据此权衡Power-Law Relationships of the Intemet Topology (CV/ Proc. of ACM设定min_ gain 与max yrumber 的值。SIGCOMM, Cambridge, Massacuets, Unted States: ACM Pess,1999: 251-262.4结论10] 张家才，周登勇从开放的复杂巨系统来看Intenet中的大范围模式凹系统仿真学报。2002, 14(): 1450-1454 (ZHANG lacai,随着因特网的快速增长，www浏览已经成为人们最主ZHOU Deng-yong. View the Large Scale Modes of the Internet as An要的日常生活之一, 优化WEB站点结构有利于改善wwwOpen Complex Giant Systrm 0 Joumnal of System Simulation, 2002,浏览行为的质量。本文分析了WEB节点出度的幂律模式与14(1): 1450-1454.)节点访问频度的zipf分布规律,设计了相应的仿真算法与站[1] G K Zipf. Human behaviour and the principle of least effort [M].Reading, MA: diso-Wesley, 1949.点结构优化方法，实验表明，优化后的WEB站点具有更小[12] Peter Piolli, Suart K Card. Information Foraging [0. Psychological的平均访问代价，有助于改善www浏览中搜寻与获取有Review (0033-295X), 199, 106(4): 643-675.益信息的困难问题及信息搜寻行为的效率低下问题。13] S中国煤化工Word Wide Web (D.:169-752 1994, 27();WEB站点是一-个动态性很强的进化与演变实体。随着CNMHG时间的推移，WEB站点的一部分旧页面会消失、-部分新页面会出现、-部分旧超链接会消失、- 部分新超链接会出●4688●