第19卷第20期系統(tǒng)仿真學報@Vol. 19 No.202007年10月Journal of System SimulationOct, 2007WEB站點結構優(yōu)化仿真劉業(yè)政，林文龍，焦寧，姜元春(合肥工業(yè)大學管理學院電子商務研究所合肥23000)摘要: WEB站點結構優(yōu)化技術是解決wwW瀏覽中搜尋與獲取有益信息的困難問題及信息搜尋行為的效率低下問題的有效方法。基于WEB站點的超鏈體系鮚構特征與網頁節(jié)點的訪問頻度值特征，建立了一種站點結構優(yōu)化的數學模型，其目標是使整個站點具有較小的平均訪向代價。分析了站點超鏈體系結構特征與節(jié)點訪問頻度特征，采用仿真算法分別模擬了WEB站點的超鏈體系結構與頁面節(jié)點的訪問頻度值，并通過量化新增超鏈接的影響因素設計了相應的站點結構優(yōu)化方法. .實驗結果表明:優(yōu)化后的站點結構具有較小的平均訪問代價。關鍵詞: WEB站點結構優(yōu)化;超鏈體系結構;節(jié)點訪問頻度; 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為用戶往往需要通過一條花費更多訪問代價的路徑才到達引言其興趣目標頁面.站點結構優(yōu)化技術就是通過考慮優(yōu)化網站wWW瀏覽中的兩個常見問題是:搜尋與獲取有益信息信息組織的超鏈體系結構來使所有的用戶都可以以更小的的困難問題及信息搜尋行為的效率低下問題。有益信息搜尋訪問代價瀏覽WEB站點更有效地獲取所需的信息。-個結與獲取的困難主要根源在于以超鏈接形式組織的WEB信息構優(yōu)化的站點，可以減少用戶的“無謂”點擊行為，從而減體系結構的零亂,這種零亂性使用戶不知道當前所處網頁節(jié)少WEB服務器的請求事務次數，減輕服務器負擔，可以使.點的具體位置;不知道怎樣才能到達其想要去的興趣目標頁用戶更有效地到達其訪問的目標頁面，節(jié)省用戶訪問時間，面，即www“迷航"。通常迷航的用戶在面對眾多的超鏈提高用戶對站點的滿意度。接選擇時會產生--些無益于到達其興趣目標頁面的“無謂”本文采用仿真的方法研究降低WEB站點平均訪問代價點擊行為，這種“無謂”的點擊行為- -方面增加了WEB服的站點結構優(yōu)化問題:將WEB站點抽象成樹結構模型(對站務器負擔，另-方面也增加了網絡的數據流量,容易造成網點結構的描述建模問題，通常有樹(67、 圖吲、超圖凹等幾種絡阻塞，導致網絡訪問速度的下降，從而進一步影響了信息描述方式。由于我們考慮的站點結構優(yōu)化模型主要刻畫的是搜尋行為的效率。對這兩個問題很難有-一個完美的解決方案,群體用戶從主頁出發(fā)，以一種自頂向下點擊超鏈接的形式來目前對這些問題的解決采取的方法可以分為三類:搜索引擎搜索到達各自訪問目標頁面的行為，因此相比較而言，能刻技術:基于WUM(Web Usage Mining)技術開發(fā)各種瀏覽導畫站點層次化語義結構的樹描述方式更適于對這種用戶帶航工具; WEB站點結構優(yōu)化技術1161。有訪問目標的站點結構優(yōu)化問題進行建模)，通過分析模型一般來說，用戶與站點的設計開發(fā)人員對WEB站點信中網頁節(jié)點的出度特征與訪問頻度特征,采用仿真的方法分息組織的超鏈體系結構存在不同的觀點,這種差異通常表現別模擬了WEB站點超鏈體系結構以及WEB頁面的訪問頻度,并中國煤化工設計了相應的站點結收稿日期: 20608-14修回日期: 2006-10-24構優(yōu)CNMHG基金項目:國家自然科學基金資助(70672097)作者簡介:劉業(yè)政(1965-), 男，安徽和縣人，教授，博導，研究方向為1問題建模數據挖掘與GDSS:林文龍(1979-), 男，福建龍巖人，博士，研究方向為WEB挖掘:焦寧(1981-), 男，安徽太和人，碩士,研究方向為數據定義1 (WEB站點樹結構模型) WEB站點可以表示為一挖捆;姜元春(1980-),男，山東萊西人，博士，研究方向為數據挖掘?！?685.第19卷第20期Vol. 19 No.202007年10月系統(tǒng)仿真學報Oect. 2007棵樹T=(V.E),其中V為站點頁面集合，E為頁面之間的超的冪律性回，Faloutsos 將獲取的三個Intermet 快照鏡像與冪鏈接集合。根節(jié)點r表示站點首頁,對于任意的節(jié)點v∈V, .律關系進行了對比，顯示出它們的相關系數在96%以上,最其所代表的頁面所包含的超鏈接數目稱為節(jié)點v的出度,記高能達到9%。WEB冪律規(guī)律的一個典型模式是網頁節(jié)點為8%稱出度為0的節(jié)點為葉子節(jié)點,代表網站的內容節(jié)點:出度與其節(jié)點等級的冪成比例，即設節(jié)點的等級r是按出度稱出度大于0的節(jié)點為非葉子節(jié)點，非葉子節(jié)點有兩種情降序排列序列中的索引值，則有:況,一是在網站中 只起導航作用而不包含可訪問內容的純導8,=ar,"(1)航節(jié)點,二是起導航作用并包含可訪問內容的復合節(jié)點,視式中a為比例系數，R為等級指數，Faloutsos 的實驗結果表復合節(jié)點為- -純導航節(jié)點和一個與其所包含的可訪問內容明等級指數R -0.82--0.74之間。相對應的內容節(jié)點的復合體,記包括復合節(jié)點復合體中的內盡管Intemet呈現出的大范圍模式規(guī)律提供了進行比隨容節(jié)點在內的所有內容節(jié)點的集合為Vco機圖更精確仿真WEB站點結構的可能，但據我們所知，這定義2 (節(jié)點訪問頻度)指節(jié)點所代表的頁面所包含的些大范圍模式基本上是從整個WEB拓撲結構方面來研究可訪問內容部分被訪問的頻繁程度?？紤]-一個足夠長的時的..對于單個WEB站點的超鏈體系結構，目前并沒有一種段，設群體用戶對節(jié)點v所包含的可訪問內容部分的訪問次能完全確切的模擬方法?？紤]到我們的研究目的及模型的需數為click()， 則節(jié)點v的訪問頻度可以定義為要，這里我們主要考慮利用Faloutsos 的節(jié)點出度的冪律模p.=click(1)/Sew click(1).式來仿真站點結構。設站點包含的頁面數目IM,非葉子節(jié)點定義3(訪問代價)用戶從根節(jié)點r出發(fā),到達其訪問目中復合節(jié)點所占的比例為B,給定-一個初始的站點頁面，通標節(jié)點v的最少點擊次數為節(jié)點v的訪問代價,記為C(r,以), .過公式(1)給其分配-一個出度值與相應的子節(jié)點頁面,再對子或簡記為c()。節(jié)點頁面重復同樣的過程，直到獲得所需要大小的網站時算定義4(WEB站點平均訪問代價)群體用戶到達各自訪法中止生成站點結構并從中按比例系數β隨機抽取一部分非問目標節(jié)點的訪問代價均值稱為站點平均訪問代價,可以表葉子節(jié)點為復合節(jié)點，該仿真過程可以用算法1描述如下。示為C(T)=E p.c(,).算法1 WEB 站點結構仿真算法。定義了WEB站點平均訪問代價的概念，我們考慮對輸入:網站網頁節(jié)點數1V,比例系數a, β;WEB站點樹結構模型和網頁節(jié)點的訪問頻度進行仿真建輸出:仿真的站點結構;模，以及降低WEB站點平均訪問代價的站點結構優(yōu)化方法。過程:2仿真建模()初始化網站節(jié)點集合V=NULL,邊集合E=NULL;(2)初始化網頁節(jié)點隊列Q=NULL;對上述WEB站點結構優(yōu)化問題進行仿真建模，我們首(3)新建網頁節(jié)點v=new web page,將v加入隊列Q中:先需要知道的是實際WEB站點的超鏈體系結構規(guī)律以及用(4) while隊列Q不空戶對真實站點的訪問規(guī)律,由此建立站點超鏈體系結構數據a) If v的大小已達到M, returm T=(V,E);的仿真算法和站點網頁節(jié)點訪問頻度數據的仿真算法,在此b)從隊列e中取出一一個新節(jié)點v;基礎上考慮優(yōu)化約束條件，對站點結構進行優(yōu)化。c)按照公式(1)的規(guī)律給節(jié)點v分配出度值&2; .2.1 WEB站點結構仿真d) Fori=1 to 8,將WEB站點抽象成樹結構，直觀地可以用隨機樹產生i)新建網頁節(jié)點w=new web page;算法來生成站點的超鏈體系結構。盡管著眼于局部環(huán)節(jié)，i)V=V Uw, E=E U(,w);Internet呈現出明顯的隨機性(任意一個主體都可以在iI)將w加入隊列Q中:Internet.上創(chuàng)建包含有任意個頁面、任意個超鏈的站點),但iv) If V的大小已達到M, return T=(V,E);近年來的研究表明，Intemet 整體卻呈現出一定的大范圍模(5)按比例系數β隨機抽取-部分非葉子 節(jié)點為復合節(jié)式規(guī)律)，這些規(guī)律包括:站點中的網頁數量、用戶數量點。遵守冪律分布:網站中網頁被請求和傳送的次數服從Zipf2.2節(jié)點訪問頻度仿真分布:用戶的訪問步長遵守冪律分布: WEB頁面的大小顯大量用戶對WEB站點的訪問是一-種 群體的人類行為，示出重尾分布以及關于WEB結構的幕律模式、小世界模式Zipf指出指導人類行為的一條根本性原則是以最小的代價等。WEB結構的小世界模式表現為Internet的拓撲結構不是換取中國煤化工信息搜尋理論12將均勻的，而是呈現出一個個“小世界”網絡，“小世界”網ZipfCN M H G訪問行為，假設用戶絡內部高度聚集，而且整個網絡中任意兩個節(jié)點間的最短距在WEB蹈點時歷問行為是一-柙帶有歷問目的的信息搜尋行離都很短。Faloutsos 則指出，Internet 拓撲結構顯示出極強為，并且總是傾向于最大化搜尋活動的獲取率，即單位費用●4686●第19卷第20期Vol. 19 No. 202007年10月劉業(yè)政，等: WEB站點結構優(yōu)化仿真Oct, 2007上獲得的信息量,由此可以推測WEB頁面的訪問頻度也遵多超鏈接的做法,將會導致一一些導航頁面上的超鏈接數目太循Zipf分布。Giassman 通過分析300個不同用戶對40,000多,使用戶在該導航頁上正確選中能到達其目標頁面的超鏈個WEB頁面的10,000次訪問請求,從實驗上證明了WEB接的選擇困難度增加，也容易導致用戶選擇-些不能到達其頁面訪問頻度的Zipf分布定律I)。根據Zipf定律，給定一目標頁面的超鏈接，從而給用戶的瀏覽造成更大的不便。下個Zipf分布，在不考慮純導航節(jié)點的情況下，訪問頻級為i面量化這兩個因素，并給出相應的優(yōu)化方法。的網頁節(jié)點v的訪問頻度為:定義5 (超鏈接)超鏈接h為二元組h=8penalty(h)={ uchlarn)l3)(3)按照公式(2)的規(guī)律給包括復合節(jié)點復合體中的內δ,≤&容節(jié)點在內的m個內容節(jié)點分配訪問頻度值;式中: 8為預定的選擇困難度閾值，children(s)為節(jié) 點s的所(4)葉子節(jié)點的訪問頻度為其所代表的內容節(jié)點的訪有內容子節(jié)點集合(與children()不同， 若s為復合節(jié)點，問頻度;則children(s)不包括復合節(jié)點復合體中的內容節(jié)點:若s為(5)非葉子節(jié)點中復合節(jié)點的訪問頻度值取為復合體內容節(jié)點，則children()-null).中內容節(jié)點的訪問頻度值。由此可以得到超鏈接h的增益計算公式為: .gain(h)=2.3優(yōu)化求解E P.(t)-c(s)-1)- penalty(h)4)通過上述的WEB站點結構仿真算法與節(jié)點訪問頻度仿真算法，我們模擬了初始的網站鏈接結構與網站所有的網頁在添加超鏈接的實際優(yōu)化工作中,通常我們忽略增益值節(jié)點訪問頻度值,對應于這個初始的站點結構,根據定義4,低的超鏈接,以保證用盡量少的超鏈接獲取盡可能多的增益我們可以求得初始的WEB站點平均訪問代價, - -般來說這或是對站點增加的超鏈接總數做限制,為此我們采取兩種優(yōu)個代價值會比較大，我們考慮對該WEB站點的超鏈體系結化策略，優(yōu)化策略之一是設置最小增 益值min gain, 添加所構進行優(yōu)化。有候選超鏈接集合中增益值大于min_ gain 的超鏈接，優(yōu)化對WEB站點超鏈體系結構的優(yōu)化主要有以下幾種手策略之二是設置增加的最大超鏈接總數max_ rumber,依次段:增加新鏈接、刪除已有鏈接、調整鏈接的位置或是調整添加增益值最大的前max_ yrumber 個超鏈接。設采用上述優(yōu)網頁節(jié)點的位置?？紤]到站點原有的超鏈導航體系結構對站化策略后在原有的WEB站點超鏈接體系結構上增加了一-組點老用戶的重要性，在進行優(yōu)化變換降低WEB站點平均訪新的超鏈接集合H,則超鏈接集合H的增益值可以計算如下:gain(H)=問代價同時,我們希望能夠避免破壞站點原有的超鏈導航體S 2(9)-()-penalb>(H)5)系，因此我們只考慮在原有站點超鏈體系結構上增加一組合適的超鏈接來優(yōu)化站點結構。給定一一個初始的站 點結構及網上式中: penalty(H)= E penaly(h)6)頁節(jié)點的訪問頻度值分布,我們的問題是:如何增加- -組合由此可以得到優(yōu)化后的WEB站點平均訪問代價C(7")適的新超鏈接以期獲得最低的WEB站點平均訪問代價。為中國煤化工- 般來說增加超鏈接能減小相應一 部分內容節(jié)點的訪7)問代價,因此直觀的做法是在站點首頁上添加指向所有內容YHCNMHG節(jié)點的超鏈接,使站點結構盡可能的扁平化,將能獲得最小3實驗的網站平均訪問代價。但是這種在首頁等導航頁面中增加過我們在Windows 2000 平臺上用MATLAB7.0實現了上●4687.第19卷第20期Vol. 19 No. 202007年10月系統(tǒng)仿真學報Oct, 2007述的仿真工程，對節(jié)點數目1V=10000的網站做了仿真實驗?，F;同時頁面的訪問頻度也會隨著時間變化而變化，表現為:實驗分兩步:首先通過WEB站點結構仿真算法(算法中a隨著時間的推移,舊頁面的訪問頻度下降,新頁面的訪問頻度取20, β取80%，等級指數R取-0.82)與節(jié)點訪問頻度仿上升。因此從本質上說，本文建立的WEB站點結構優(yōu)化模真算法產生模擬的WEB站點結構與網頁節(jié)點訪問頻度值，型是一種靜態(tài)模型，進-步的研究方向是建立一種動態(tài)仿真的網站具有1575個非葉子節(jié)點與8425個葉子節(jié)點,我WEB站點結構優(yōu)化的仿真模型。們按比例系數β隨機的選取了1260 個非葉子節(jié)點作為復合參考文獻:節(jié)點，則包括復合節(jié)點復合體中的內容節(jié)點在內，仿真的網1] Ramakrishnan Srikant, Yinghui Yang. Mining web logs to improve站結構共有9685 個內容節(jié)點，其中訪問頻度最大的為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;然后分別采用優(yōu)化策略一[2] John Garofalakis, Panagiotis Kappos, Dimitris Mourloukos. Web Site與優(yōu)化策略二對站點結構進行優(yōu)化，圖1是優(yōu)化策略- -的實Opimizatio Using Page Popularity幾TEEE Internet Computing驗結果，圖2是優(yōu)化策略二的實驗結果，實驗中選擇困難度(S1089 7801), 999 3(4): 22-29.閾值δ取當前站點最大的節(jié)點出度值。[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優(yōu)化策略- -的實驗結果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優(yōu)化策略二的實驗結果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] 張家才，周登勇從開放的復雜巨系統(tǒng)來看Intenet中的大范圍模式凹系統(tǒng)仿真學報。2002, 14(): 1450-1454 (ZHANG lacai,隨著因特網的快速增長，www瀏覽已經成為人們最主ZHOU Deng-yong. View the Large Scale Modes of the Internet as An要的日常生活之一, 優(yōu)化WEB站點結構有利于改善wwwOpen Complex Giant Systrm 0 Joumnal of System Simulation, 2002,瀏覽行為的質量。本文分析了WEB節(jié)點出度的冪律模式與14(1): 1450-1454.)節(jié)點訪問頻度的zipf分布規(guī)律,設計了相應的仿真算法與站[1] G K Zipf. Human behaviour and the principle of least effort [M].Reading, MA: diso-Wesley, 1949.點結構優(yōu)化方法，實驗表明，優(yōu)化后的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站點是一-個動態(tài)性很強的進化與演變實體。隨著CNMHG時間的推移，WEB站點的一部分舊頁面會消失、-部分新頁面會出現、-部分舊超鏈接會消失、- 部分新超鏈接會出●4688●