The web structure yields significant insights into web algorithms for searching, structuring, discovering, mining, and revealing web information. We formalize our view of the web structure in terms of the integer linear programming that converts the web directed graph to the optimal hierarchical structure. The model represents a high level structure regardless of various measures such as the cosine similarity and tf-idf measure of the vector space model as well as the PageRank of Google. Another advantage for our approach is that the corresponding sensitivity analysis yields an allowable range for the optimal structure so that the model can be estimated even though dynamic changes take place in the web pages, links, and structures.
The WWW can be viewed as a hierarchy of web objects. The WWW can be seen as a set of web sites, and a web site can be seen as a digraph with web nodes and arcs, where the web nodes correspond to HTML files having page contents and the arcs correspond to hypertext links interconnected with the web pages. The web-as-a-graph approach can be a starting point to generate a structure that can be used for web site designers, search engines, web crawling robots, and web marketers and analysts.
One of the typical examples of web site structuring is tree modeling, such
as breadth first search (BFS), depth first search (DFS), web catalogues or
site maps [
The BFS, including backlink count method or RageRank [
On the other hand, the DFS is an easy method to adopt, and, from a cognitive science point of view, the search methods are similar to the behaviors of human snoopers. But, the DFS is inappropriate for structuring the web because a long series of web pages means as many clicks as there are pages which, in turn, entails massive time consumption to access each page.
A topological ordering algorithm [
We formalize our view of the web structure in terms of the integer programming that converts the web directed graph to the optimal hierarchical structure. The structure of a web site can prevent the search robots or crawling agents from confusing in the midst of huge web pages in the web sites. Therefore, in this paper, we introduce an attribute called, "the weight," to evaluate the significance of web pages.
This paper is organized as follows: In Section 2, we present the data model of web sites, the web schema, and conventional approaches. In Section 3, we discuss several weight measures endowed on web nodes. In Section 4, we will discuss on the integer linear programming model of the web structure. In Section 5, we will present an example of our model and present the robustness of our model with experimental results. Finally, we conclude the paper.
A web site can be defined as a set of web nodes Nw = {N1, ..., Nn}, a
directed graph Gw = (Nw, Ew), an arc function xij : Nk → {0, 1}, ∀(i, j)∈Ew
consisting of a finite web node set Nw, a finite web arc set Ew of ordered
pairs of web nodes, and the web arc elements (i, j) respectively, where i, j ∈
{0, 1, 2, 3, ... , n-1}, and n =|Nw| the cardinality of web pages. There is a
mapping system for the nodes corresponding to web pages and the arcs to
Uniform Resource Identifiers [
Nw = [ Ni ,{(i, j),∀i}, wi ] (2-1)
Where the Ni represents a web node corresponding to an HTML file (we set a node identifier as i ). Where the homepage is defined as a default page (index.html) predetermined by the web server. The {(i, j), ∀i, j ∈Ew} is the set of web arcs having hypertext links to which the web page indicates.
There are three approaches to investigate the web digraph domain as (1)
the whole web [
In order to generate the web structure, we introduce the representative
weight measures such as cosine measure and tf-idf measure from Vector
Space Model (VSM), and PageRank. For the first time, most web ranking
algorithms utilize a similarity measure in terms of VSM, which has been
extensively studied in the information retrieval community [
Another common way of computing a web page's weight, W, is the tf-idf,
which is obtained as an normalized vector, W' = < w'1,...,w'm >T, where each
w'i is the product of a term frequency (tf) factor and an inverse document
frequency (idf) factor. The tf factor is proportional to the frequency of the ith
word within a web page. The idf factor is a factor divided by the number of
times that the word appears in the entire set of web pages that corresponds to
the content discriminating power of the ith word that appears rarely in
documents has a high idf, while a word that occurs in a large number of
documents has a low idf. Typically, idf is computed by logarithms from the
total number of documents and is the number of documents containing the
word. If a word appears in every document, its discriminating power is 0. If
a word appears in a single document, its discriminating power can be very
large. Once the vector is computed, the normalized vector, W, is typically
obtained by their norms. The similarity between a query, Q, and a web page,
Ni, can then be defined from which the weight specified as the inner product
of the two. There are other measures from VSM in terms of local weights
such as the Binary model [
There are two major link-based search algorithms, HITS and PageRank.
The basic idea of the HITS algorithm is to identify a small sub-graph of the
web and apply link analysis on this sub-graph to locate the authorities and
hubs for the given query. The sub-graph that is chosen depends on the user
query. The selections of a small sub-graph (typically a few thousand pages),
not only focus the link analysis on the most relevant part of the web, but also
reduce the amount of work for the next phase. The main weaknesses of
HITS are known to non-uniqueness and nil-weighting. Haveliwala [
One of the representative arc oriented approaches is the PageRank
algorithm [
weight(Wj ) =
The similarity measure in this paper is the weight of web node. We introduce the cosine measure, tf-idf measure, and PageRank measure as the weight measure which can be used to determine the topological ordering of web sites. The prototype system has been experimentally tested to search for the structure of the test web site. The link structure of the site is shown in reference Fig. 3.1 and 3.2. The circle in the figures represents a web node and the arrow represents a hyperlink or a web arc.
First of all, the cosine measure from the VSM is introduced [
(3.1) a Tjq || a j ||2|| q ||2 = m 2 ∑ aij i=1 ∑m qi2 i=1
In the tf-idf measure, the tf factor itself is sometimes normalized by
dividing it by the frequency of the most-frequent non-stop term in the
document as, tfnorm = tf/tfmax. The idf factor is typically computed by
[df(wi)/N]-1, and most often the log2[N/ df(wi)] is used, where, N, is the total
number of documents and, df(wi), is the number of documents containing the
ith word. Refer to equation (3.2) [
weight( Wj ) = Q ∗ Wj = [qi ] ∗ ⎡⎣(tfi ⋅ log2 [ N / df ( wi )])⎤⎦T = ∑ qi ⋅(tfi ⋅ log2 [ N / df ( wi )]) i (3.2)
The PageRank measure is that, if source page, i, has a link to target page,
j, then the author of source page, i, is implicitly conferring some importance
to page, j. Let Nj be the out-degree of page, i, and let Rank(p) represents the
importance of page, p. Then, the link (i, j) confers a certain number of units
of rank to, j. This simple idea leads to the following iterative fix-point
computation that yields the rank vector over all of the pages on the web. If, n,
is the number of pages, assign all pages the initial value 1/n. Let, Bj represent
the set of pages pointing to j. Links between web pages propagate the ranks
[
In Google, we usually set the value of the damping factor to 0.85 [
The model can be applied to transform a digraph into a tree. First, except
for the root node, the tree node's indegree should be 1. Second, All cycles
which may exist in a graph should be removed during the transformation
phase. Cycle detection is implemented by DFS using Stack based algorithm
[
∑ i,j∈N ,j≥1 (i,j)∈A
wijxij s.t
xij = 0 ∑ i∈N (i,0)∈A
∑ i∈N (i,j)∈A xii = 0 for all i xij + x ji ≤ 1 ∀i , j xij = 1 for all j ≠ 0 m−1 xij1 + k∑=1 x jk jk+1 + x jmi ≤ m for 2 ≤ m ≤ N − 1 xij = 0 ∀i , j ∉ N xij = 0 or 1 ∀i , j (4.1) (4.2) (4.3) (4.4) (4.5) (4.6) (4.7) (4.8)
The variable xij is 1 if there exists a web arc from node i to node j, zero
otherwise. Set A represents a set of all existing links between any of two
Web pages in a Web site, where notation (i, j) is used to represent a link
from node i to node j. The weight parameter wij represents the average
distance from node i to node j. There are several alternatives for deriving the
weight of a node and to generate a distance to the link, including the number
of inward or outward links [
When the query terms are altered, measurements of the web Node are also altered. In this case, sensitivity analysis is used to determine whether the entire problem needs to be reformulated and recalculated or not. The standard IP problem forms separated basic variables between nonbasic variables. After applying a simplex algorithm, the above IP problem is reformed.
The criteria of optimality in a simplex algorithm is that an objective function's coefficient of a non-basic variable, i.e., c j = CBV B−1a j − c j (aj is a column vector of N for xj , cj is objective function's coefficient value for a nonbasic variable xj) must be non-negative. Also, the feasibility condition of the current basis solution is that RHS of the equation, i.e., B-1b must be nonnegative. When the weight of the web node is changed, but and if this change does not influence the above two conditions (i.e., the optimality and feasibility condition), then the current basis is conserved.
Fig. 3.1 represents a digraph consisting of 7 web pages, i.e., N0 to web page N6. The weight of an arc is the mean average weight value of two terminal nodes of the arc. After reorganizing the IP problem, each of the BV (Basic variable), NBV (Nonbasic variable), objective function coefficient cBV, cNBV, basis matrix B, RHS (Right Hand Side) can be described.
If the web page is changed, then the corresponding objective function's coefficients are also influenced. If it does not break the primal feasibility condition, i.e. B-1b≥ 0, then the current basis will not change. In this case, the current solution's feasibility condition and optimality condition is maintained. This also means that the current basis is not changed. In case a link is deleted, the constraint can be inserted into the formulation. If the current solution does satisfy the new constraint, the current basis is maintained, otherwise, a dual simplex algorithm can be used. Consider the case where two links between nodes, W1 and W4, are disconnected. Then, the two constraints(x14=0 and x41=0) should be included into the previous IP formulation. As the current solution satisfies the inserted constraints, the current basis is maintained. In this case, the objective function coefficient, the element of N matrix for the new inserted variable, and all constraint types, except non-negative constraints, can be included in LP formulation. In this case, the current basis is not conserved.
By the example site in section 2, the number of nodes is increased from 1 to 7. The node weights are derived from the cosine of VSM, tf-idf, and PageRank. A total of four structuring methods are applied such as DFS, BFS, Semantic, and LP. Fig. 6.2 PageRank weight measure traverses w.r.t. the number of nodes We conclude that the LP solution produces the optimal solution with optimal structure. In other words, our approach generates the optimal hierarchical structure among many structuring methods. Our method shows its openness of the mechanism without respect to the weight measure such as cosine measure, if-idf measure, and PageRank measure.
8.000
The goal of this paper has been to generate the optimal hierarchical structure of a web site from directed graphs. With respect to the weight measure, the optimal solution can be derived: from a user's point of view, the optimum approach will be consonant with the user's preferences in terms of query with tf-idf or cosine measures, on one hand; or, from a web robot's point of view, the optimum will be represented by the search robot's point of view. This model guarantees that the optimal hierarchical structure will be generated with respect to the measurement and the optimization model. A mathematical model is pertained onto a web site in terms of the integer linear programming by which the web digraph can be converted to the hierarchical structure. The optimal solution from the hierarchical structure and the corresponding sensitivity analysis yield a robustness of the model in maintaining the solution in a dynamic manner.
The model can secure the optimum under any weight measure conditions, and by using the LP model, a user is always able to get the optimal result even though any actions, such as Adding, Deleting, Inserting, etc., are undertaken within a web site. Under the circumstances of frequent web contents change, the LP model can be a very good tool for developing an advanced search engine schematic. The LP model also shows its openness: Using significant similarity measures (such as tf-idf, cosine measure, and PageRank) does not affect the optimal model, the corresponding solution, and sensitivity analysis, which implies that the model can easily be adapted by and integrated into the current Web search robots as well as the web site managers having various similarity measures.
This work was supported by the Korea Science and Engineering Foundation (KOSEF) through the Advanced Information Technology Research Center (AITrc).