Pierre Bousquet
email: bousquet@cmi.univ-mrs.fr

Petru Mironescu
email: mironescu@math.univ-lyon1.fr

An elementary proof of an inequality of Maz'ya involving L 1 vector fields

We give a short elementary proof of the inequality

essentially established by Maz'ya [4].

Introduction

For any f ∈ L 1 (R n , R n ), we denote by u := (-∆) -1 f the Newtonian (logarithmic for n = 2) potential of f:

u(x) = R n Γ(x -y)f(y) dy,
where Γ is the fundamental solution of -∆:

Γ(x) :=      -1 2π ln |x| if n = 2 1 |S n-1 |(n -2) 1 |x| n-2 if n ≥ 3.
One of the main results in [START_REF] Bourgain | New estimates for elliptic equations and Hodge type systems[END_REF] states that

||Du|| L n ′ (R n ) ≤ C (||f|| L 1 + ||div f|| W -2,n ′ ) ( 1
)
where n ′ = n/(n -1).

In [START_REF] Maz'ya | Estimates for differential operators of vector analysis involving L 1norm[END_REF], Maz'ya established the following family of estimates related to (1)

Theorem 0 Let 1 ≤ q < n ′ and f ∈ L 1 (R n , R n ). Assume that R n f = 0. Let h := div f. i)] If q > 1 and ∇(-∆) -1 h ∈ L 1 , then ||Du|| L q (|x| n(q-1)-q dx) ≤ c ||f|| L 1 + ||∇(-∆) -1 h|| L 1 .
ii)] If q = 1 and (-∆) -1/2 h ∈ H 1 (where H 1 denotes the Hardy space), then

||Du|| L 1 (|x| -1 dx) ≤ c ||f|| L 1 + ||(-∆) -1/2 h|| H 1 .
These estimates partly solve Open Problem 1 in [START_REF] Bourgain | New estimates for elliptic equations and Hodge type systems[END_REF].

The aim of this note is to unify the two statements of Theorem 0 and to present a proof both shorter and more elementary than the original one in [START_REF] Maz'ya | Estimates for differential operators of vector analysis involving L 1norm[END_REF]. Our result is

Theorem 1 Let 1 ≤ q < n ′ and f ∈ L 1 (R n , R n ). Let h := div f. If ∇(-∆) -1 h ∈ L 1 , then ||Du|| L q (|x| n(q-1)-q dx) ≤ c ||f|| L 1 + ||∇(-∆) -1 h|| L 1 . Remarks. i) In Theorem 0, it is required that R n f = 0. In fact, this equality is implied by the assumptions f ∈ L 1 and ∇(-∆) -1 h ∈ L 1 . ii) If (-∆) -1/2 h ∈ H, then ∇(-∆) -1 h ∈ L 1 ,
but the converse is false. Thus, when q = 1, Theorem 1 requires a weaker assumption than Theorem 0.

We start by proving i). The Fourier transform of ∂ j (-∆) -1 h is

F j (ξ) = - k ξ j ξ k |ξ| 2 f k (ξ) = - k ξ j ξ k |ξ| 2 f k (0) + o(1) as ξ → 0.
The continuity of F j at the origin implies f j (0) = 0, i. e., f j = 0.

We next briefly justify ii).

If g := (-∆) -1/2 h ∈ H 1 , then the Riesz transforms of g satisfy R j g ∈ L 1 , 1 ≤ j ≤ n, so that ∇(-∆) -1 h = ı(R 1 g, ..., R n g) ∈ L 1 . In order to see that the converse is false, pick a temperate distribution g such that R j g ∈ L 1 , 1 ≤ j ≤ n, but g ∈ L 1 .
Such a g exists, see [START_REF] Stein | Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals[END_REF], 6.16, p. 184 and the references therein. If

f := -ı(R 1 g, . . . , R n g) ∈ L 1 , then (-∆) -1/2 div f = g ∈ L 1 , while ∇(-∆) -1 div f = -f ∈ L 1 . 2 Proof of Theorem 1 Let ρ 0 ∈ C ∞ c (R + ) be such that 0 ≤ ρ 0 ≤ 1 and ρ 0 (r) = 1 if r ≤ 1/4 0 if r ≥ 1/2 . We introduce ρ(y, x) = ρ 0 (|y|/|x|) for (y, x) ∈ R n × R n \ {0}. For 1 ≤ k ≤ n, we have ∂ x k u(x) = c n R n x k -y k |x -y| n f(y) dy = I 1 (x) + I 2 (x),
where

I 1 (x) = c n R n ρ(y, x) x k -y k |x -y| n f(y) dy , I 2 (x) = c n R n (1-ρ(y, x)) x k -y k |x -y| n f(y) dy.
We estimate ||I 2 || L q (|x| n(q-1)-q dx) using the following straightforward consequence of Hölder's inequality

x → f (y)g(x, y) dy

L q ≤ f L 1 sup y g(•, y) L q (dx) .
(

) 2
We have

|I 2 (x)| ≤ c |y|≥|x|/4 |f(y)| dy |x -y| n-1 so that, by (2), ||I 2 || L q (|x| n(q-1)-q dx) ≤ c |f(y)| dy sup y =0 |x|≤4|y|
|x| n(q-1)-q |x -y| (n-1)q 1/q .

The quantity

|x|≤4|y|
|x| n(q-1)-q |x -y| (n-1)q dx is finite and does not depend on y = 0 (since it depends only on the norm of y and is homogeneous of degree 0). This implies that ||I 2 || L q (|x| n(q-1)-q dx) ≤ c |f(y)| dy.

In order to estimate ||I 1 || L q (|x| n(q-1)-q dx) , we note that for |y| ≤ |x|/2 we have

x k -y k |x -y| n - x k |x| n ≤ c |y| |x| n .
Thus

|I 1 (x)| ≤ c 1 |x| n |y|≤|x|/2 |f(y)||y| dy + J(x)
where

J(x) := 1 |x| n-1 R n ρ(y, x)f(y) dy .
Using (2), we obtain

||I 1 || L q (|x| n(q-1)-q dx) ≤ c |f(y)||y| dy sup y =0 |x|≥2|y| dx |x| n+q 1/q +c||J|| L q (|x| n(q-1)-q dx) ≤ c||f|| L 1 + c||J|| L q (|x| n(q-1)-q dx) .
It then remains to estimate ||J|| L q (|x| n(q-1)-q dx) .

To start with, we asume, in addition to the hypotheses of Theorem 1, that f ∈ C ∞ . Then we have

0 = R n div (y 1 ρ(y, x)f(y)) dy = R n ρ(y, x)f 1 (y) + y 1 |y||x| ρ ′ 0 |y| |x| i y i f i (y) + y 1 ρ(y, x)div f(y) dy. Thus R n ρ(y, x)f 1 (y) dy ≤ c |y|≤|x|/2 |y| |x| |f(y)| dy + R n y 1 ρ(y, x) div f(y) dy . (3)
We claim that, with h = div f, we have Then div k = ∆(y 1 ρ(y, x)), div l = 0 and

(k + l) i =                      y 1 ∂ ∂y 1 ρ(y, x) -y 2 ∂ ∂y 2 ρ(y, x) if i = 1,
y 1 ∂ ∂y 2 ρ(y, x) + y 2 ∂ ∂y 1 ρ(y, x) if i = 2, y 1 ∂ ∂y i ρ(y, x) if i ≥ 3. Thus |k + l| ≤ c |y| |x| 1 |y|≤|x|/2 .
Therefore,

R n y 1 ρ(y, x) div f(y) dy = - R n div (k + l)(-∆) -1 (div f) = R n (k + l)∇(-∆) -1 (div f).
By taking the absolute values in the above identity, we find that (4) holds under the additional assumption that f is smooth. The general case follows by noting that (-∆) -1 div and ∇(-∆) -1 div commute with convolution of vector fields with a scalar mollifier. Applying (4) to f * ρ ε , where ρ is a compactly supported mollifier, and letting ε → 0, we find that (4) holds for all f. The same is true with f instead of f 1 on the left hand side. Using again (2), it follows that ||J|| L q (|x| n(q-1)-q dx) ≤ c ||f|| L 1 + ||∇(-∆) -1 h|| L 1 .

(

) 5
This completes the proof of Theorem 1.

R n y 1

 1 ρ(y, x) div f(y) dy ≤ c |y|≤|x|/2 |y| |x| |∇(-∆) -1 h(y)| dy. (4) Indeed, let k := ∇(y 1 ρ(y, x)) and l := -∂ ∂y 2 (y 2 ρ(y, x)), ∂ ∂y 1 (y 2 ρ(y, x)), 0, . . . , 0 .

Now, ( 3 )

 3 and (4) imply that R n ρ(y, x)f 1 (y) dy ≤ c |y|≤|x|/2 |y| |x| |f(y)| + |∇(-∆) -1 h(y)| dy.


Eric Pairel
email: eric.pairel@univ-savoie.fr

Three-dimensional metrology with the virtual fitting gauges

Keywords:

The metrology implemented in several classical software equipping the coordinate measuring machines, does not correspond to the standardized tolerancing by zones, virtual conditions and perfect datum features fitted outside the matter. On the basis of these concepts and by generalizing them, a conceptual model of "fitting virtual gauges" is presented. On a part presenting two positional tolerances, the plans of inspection according to the traditional metrology and according to the metrology by fitting gauges, are compared from the point of view of their simplicity and their potential results. A fitting gauges based software is under development. It will make it possible "to save" a certain number of parts declared not conform by traditional threedimensional metrology.

INTRODUCTION AND POSITION OF THE PROBLEM

The standardized geometric tolerancing is a tolerancing by zones and virtual conditions whose locations are related to perfect features, known as datum, fitted to the surfaces of the part [START_REF]Technical drawings --Fundamental tolerancing principle[END_REF], [START_REF]Dimensioning and Tolerancing[END_REF], [START_REF] Etesami | Position Tolerance Verification Using Simulated Gaging[END_REF], [START_REF] Jayaraman | Geometric tolerancing: 1. Virtual boundary requirements[END_REF]. For example, the perpendicularity tolerance of a drilling related to a plane, means that the drilling axis must be contained, in spite of its perpendicularity defect, in a cylindrical zone whose axis is perpendicular to a perfect plane fitted on the imperfect surface of the part. By imagining a cylindrical zone rigidly linked to a perpendicular perfect plane, the whole constitutes a kind of virtual gauge which, compared to the part, can be relocated in the directions allowed by the plane fitted on the part, in order to find a location making it possible to inscrib the drilling axis in the cylindrical zone.

Unfortunately the classical software which equip the coordinate measuring machines (CMM), do not make it possible to check the geometric tolerances according to such an approach by virtual gauge. The metrology allowed by those software is based on the measuring of distances between perfect geometric features, which either are fitted at the sampled points on the surfaces of the part, or built by the user. This method imposes an interpretation of the geometric tolerances and lead, in many cases, to a degraded inspection, unfavourable for the acceptance of the part. We will illustrate this metrology through an example of inspection of positional tolerances in section 4.2.

On the basis of the concepts of zone, of virtual conditions and perfect datum features used by standardized tolerancing, we have developed, during several years [START_REF] Pairel | The gauge model: A new approach for coordinate measurement[END_REF], a conceptual model of virtual gauges. We have called it the model of the fitting gauges because its virtual gauges seek to be fitted on the digitized surfaces, outside of the matter.

After a presentation of this model to the section 2, we will show its use in section 4, for the inspection of standardized geometric tolerances which will enable us to compare this new three-dimensional metrology, that we call metrology by fitting gauges, with the traditional metrology allowed by the classical software.

THE FITTING GAUGES MODEL

Base of the elementary gauges

The model of the fitting gauges is founded on the association of a "gauge" to the different kind of clouds of sampled points.

Elementary surfaces which can be digitized on the parts are all of one of the seven classes of surfaces [START_REF] Briard | The Mating Function in CAD/CAM Systems[END_REF].

Figure 1: The Gauge-surfaces.

Gauge-plane Gauge-cylinder

Gauge-sphere

Gauge-cone

Gauge-prisme Gauge-screw Gauge-freeform Gauge-tore Gauge-revol

Gauge-Dplanes Gauge-Aplanes

At each elementary surface is associated an elementary gauge. We name this first family of virtual gauges, the Surface-gauges (see Figure 1).

The gauges cone, torus and of revolution are of the same class. Moreover we add two very useful gauge-surfaces in three-dimensional metrology. They are characterized by an intrinsic size. We call them respectively Gauges-Dplanes and Gauges-Aplanes (see Figure 1).

From these gauge-surfaces we give the possibility of extracting from them, new kinds of clouds of points, which we call the Extracted-clouds:

• A point can be extracted in the center of a gaugesphere.

• A virtual segment represented by two points can be extracted from a gauge of revolution (cylinder, cone or unspecified revolution) .

• Finally a planar polygon represented by a set of points can be extracted from the median plane of the Gauge-Dplanes and of the Gauges-Aplanes .

The Figure 2 recapitulates the Extracted-clouds that can be extracted from the Gauge-surfaces. With each kind of Extracted-cloud, we associate an elementary gauge. We call this second family of elementary gauges the Gauge-zones (see Figure 3).

Figure 3: The Gauge-zones.

Construction of a compound gauge

The elementary gauges can be associated together to build more complex gauges called Compound Gauges.

Each elementary gauge is provided with a Cartesian frame which makes it possible to locate it in a single Cartesian frame of construction, which will become the Cartesian frame of the compound gauge. Thus, in its turn, the compound gauge can be used as component of a new compound gauge. The gauges can be compound indefinitely, nevertheless, from the practical point of view, a gauge of order 2, i.e. which contains a gauge compound of elementary gauges, is sufficient to check the most complicated standardized geometric tolerances.

"Fitting" behavior of the elementary gauges

Any elementary gauge seeks to be fitted as well as possible on the cloud of points with which it is associated.

For example, let us consider a gauge compound of two gauge-cylinders, parallel one to another and distant of 50 mm, each one being associated with a cloud of points representing a drilling.

If the two cylinders have fixed diameters, then the assembly of the compound gauge with the clouds of points can be impossible if drillings have too small diameter or if they are badly localised one towards another. If the assembly is possible, the compound gauge will take any assembled location with respect to the clouds of points (see Figure 4). If one of the gauge-cylinders has a variable diameter, this one will take a maximum value compatible with the assembly of the compound gauge (see Figure 5). If the two gauges have variable diameters, they both will increase or decrease by the same quantity until the compound gauge does not have any more mobility compared to the clouds of points (except that of the translation along the axes of the gauges) (see Figure 6).

Figure 6: Assembly of a gauge compound of two cylinders with variable diameters.

Chronological order of the fits

It is possible to define a chronological order of fits of the components of a compound gauge. We define for that an attribute of priority which can be given to any gauge. This attribute can take the three following values: Primaryfitting, Secondary-fitting and Tertiary-fitting.

A primary-fitting gauge fits itself first by rigidly moving the compound gauge of which it is part. During this time the other gauges are neutralized so that they can be found temporarily not assembled with their clouds of points.

The fit of the primary-fitting gauge sets up a geometrical joint with its clouds of points. For example if it is a Cylinder, a cylindrical-joint is setted up so that the compound gauge only has two degrees of freedom of movement left, the translation and rotation along the axis of the cylinder, to

Zone-sphere Zone-cylinder Zone-plane permit to the other gauges to try to be assembled and to be fitted with their clouds of points.

An other gauge may take the following priority, Secondaryfitting, if its fit removes degrees of freedom of movement left to the compound gauge by the primary-fitting gauge. That depends at the same time on the class of this second gauge and of its location compared to the first gauge.

In the same way, a third gauge can take the priority tertiaryfitting if there remain degrees of freedom to the compound gauge which it can remove.

It is not necessary to envisage a fourth level of priority because no more degree of freedom can exist after the fit of the Tertiary-fitting gauge. The compound gauge is inevitably completely linked to the clouds of points. This can be shown thanks to the classes of surfaces [START_REF] Briard | The Mating Function in CAD/CAM Systems[END_REF]. Moreover according to the class of the primary-fitting and secondaryfitting gauges, the joint can be complete as soon as they are fitted. As soon as there are no more degrees of freedom for the compound gauge, it is not possible any more to give an under priority level to the others gauges, which all are fitting without priority and which will be fitted simultaneously after the priority-fitting gauges.

By definition, and to simplify the construction of the compound gauges, each of the three priority level can be given only to one component at the same time. If several gauges must be fitted simultaneously before the others, we will start by gathering them to constitute a first compound gauge which we will then use as a priority-fitting component in a new compound gauge.

Intrinsic mobilities of a component gauge

It is possible to allow a component gauge to move in translation and/or rotation along the axes of its cartesian frame starting from its initially definite location. Up to three translations and three rotations can be given to it. These mobilities make it possible to check the standardized orientation tolerances but also to measure the variations of location of surfaces of the part.

DEVELOPMENT OF A SOFTWARE OF METROLOGY BY FITTING GAUGES

We are currently developing an experimental software exploiting the model of the fitting gauges. This development is carried out in an commercial CAD environment in order to provide a three-dimensional display of the assembly of the gauges with the clouds of points, to offer all the awaited functionalities of a modern software package (back-up file, management of the modifications...) and, for the next versions, a strong integration with the CAD software (more or less automatic construction starting from the geometry of the part and its geometric tolerances). A first version should be proposed in 2009.

CHECKING BY FITTING GAUGES VS. TRADITIONAL CHECKING

Part example

In order to highlight the advantages of metrology by virtual fitting gauges compared to the traditional three-dimensional metrology, we will compare the inspection plans and the results of measurement obtained by these two metrologies for the same example part presenting several very current geometric tolerances in mechanics.

It consists in a prismatic experimental part which will be assembled by using its planar surface A and its two drillings B. A central boring must respect a positional tolerance compared to these first surfaces (voir Figure 7). The four elementary surfaces, the plane and three borings, are digitized individually in some points and the four corresponding clouds of points are stored in a file.

Inspection plan by traditional three-dimensional metrology

We present the least unfavourable plan for the acceptance of the part which ca be made by traditional metrology. Let us note that the fact that several plans are possible for the same checks is a major disadvantage of traditional threedimensional metrology.

Stage 1: Identification of elementary surfaces and construction of a Cartesian frame of the part

A plane of least squares is fitted with the cloud of points sampled on the surface A of the part. It is used to define the Z axis of the Cartesian frame of the part to be built.

A cylinder of least squares is fitted with each drilling of diameter 8. The axes of these two cylinders are limited by two points, one with its intersection with plane A, the other distant of 12mm from this plane. A point is built at the middle height on each one of these axes.

The two medium points are used to define the direction Y of the Cartesian frame of the part and the medium point of these two points enables to fix the origin of the Cartesian frame (see Figure 8). The points at the ends of the axes of the cylinders are projected in the plane (X, O, Y) of the Cartesian frame of the part. The distances between these projected points and the theoretical points previously definite are measured. The positional defect is then the double of the maximum distance thus measured for each cylinder. This value is compared with a tolerance calculated for each cylinder by making the difference between its diameter and the diameter at the maximum material equal to 8 mm.

This inspection is approximate and does not lead to the same results than the inspection by material gauge reproducing the virtual condition of the drillings defined by the tolerance. In particular, it can result in rejecting a part conforme to the tolerance.

Stage 3: Inspection of the positional tolerance of the central boring of diameter 10 :

As for the cylinders of diameter 8, points are built on the axis of the cylinder of diameter 10 and are projected on the plane (X, O, Y) of the Cartesian frame of the part. The positional defect of the boring of diameter 10 is the double of the maximum distance between the projected points and the origin of the Cartesian frame. This value is compared with the tolerance of 0.1 mm.

The result of this inspection is close to that obtained by virtual gauge because the maximum material condition is not specified on the reference B. That would not have been so in the opposite case because the datum becomes "floating" which cannot be reproduced with the traditional software.

Inspection plan with fitting virtual gauges

Stage 1: Identification of elementary surfaces :

As for traditional three-dimensional metrology, a numerical theoretical surface is fitted on each sampled surface of the part. However these surfaces are outside of the material and are thus similar to elementary gauges fitted on their sampled surfaces. No Cartesian frame is built.

Stage 2: Inspection of the positional tolerance of drillings of diameter 8 :

In a Cartesian frame, initially coincident with the Cartesian frame of the sampled points, we build a compound gauge CG1, by the addition of a Primary-fitting Gauge-plane and of two fitting Gauge-cylinders of equal and variable diameters. These two gauge-cylinders are located in a symmetrical way compared to the origin of the Cartesian frame of construction (see Figure 9). Once fitted, the gauge-plane leaves three degrees of freedom of displacement to the compound gauge. This makes it possible for the two Gauge-cylinders "to inflate" to the maximum inside the sampled drillings. The diameter that they take then must be larger than the diameter to the maximum material size defined by the tolerance, i.e. larger than 8 mm.

Stage 3: Inspection of the positional tolerance of the central boring of diameter 10 :

The tolerance relates to the axis of the boring of diameter 10. It is thus necessary to start by extracting a cloud of two points representing the ends of this axis. The method is similar technically with that employed in traditional threedimensional metrology but it is automated by a menu of creation of an "extracted axis".

The secondary datum of the tolerance must be established simultaneously on two drillings diameter 8. The primary reference is the same one as the one of the previous tolerance, inspected with the compound gauge CG1. Also, it is possible to use this last compound gauge as a Primary-fitting component of the new gauge CG2 to be built. To finish the construction of gauge CG2, a Fitting Zone-cylinder just needs to be added yet at the origin of the Cartesian frame (see Figure 10).

Once that the component CG1 is fitted with the clouds of points, by respecting the chronology of fits defined between its own components (Gauge-plane at first then two gauge-cylinders simultaneously), the compound gauge CG2 does not have any more mobility left in respect to the part. The Zone-cylinder then will take the smallest diameter containing the two points, ends of the axis of the central cylinder. This diameter can directly be compared with the tolerance value of 0.1 mm.

Figure 10: Compound gauge CG2, for the inspection of the positional tolerance of the boring of diameter 10.

Measuring of the location deviations of the central boring

One of the reproaches made to standardized tolerancing and to traditional three-dimensional metrology is that they do not allow to measure precisely the location deviations of the manufactured surfaces. Metrology by fitting gauges allows it, in a very precise and simple way. One just needs to give the gauge the mobilities corresponding to the components of location deviation that one wishes to measure. For example, by giving the Zone-cylinder of the previous gauge CG2, mobilities in translation and rotation according to axes X and Y of its Cartesian frame, the gauge will be able to fit itself onto the Extracted-cloud by taking a diameter equal to zero. The values of the components of mobility, Tx, Ty, Rx and Ry, are then

Z CG1 Y CG1 X CG1 FITTING PRIMARY-FITTING Variable diam. Z CG2 Y CG2 X CG2 PRIMARY-FITTING FITTING Variable diam.
measured, which makes it possible to evaluate the eventual corrections that need to be made to the process carryingout the boring of diameter 10 (see Figure 11).

CONCLUSION AND PROSPECTS

As we have just illustrated it, metrology by the fitting gauges is simpler to use than traditional three-dimensional metrology. Indeed, this last one requires a rather great competence to convert the geometrical conditions, definied by geometric tolerances, into distances to be measured between features. A tolerance may be inspected differently according to the appraiser. This disadvantage does not exist with metrology by fitting gauges because the meaning of a geometric tolerance is normally single and the virtual checking gauge corresponds directly to this meaning.

Moreover the mobilities, left at the tolerance zones by the datum of the geometric tolerances cannot be reproduced with the traditional metrology. The virtual conditions cannot be reproduced either. Conversely, the fitting gauges integrate these mobilities automatically and make it possible to reproduce the virtual conditions. The consequence of these incapacities of the traditional software is that the inspections, which they allow, are more constraining than those defined by the geometric tolerances. The parts can then be rejected whereas they respect these last ones. This risk is eliminated with metrology by fitting gauges.

At the time we write these lines, a first version of a software of metrology by fitting gauges is about to be completed. It will enable us to show that on a series of 59 experimental parts, several are declared not good, by the traditional inspection plan presented in this article, and good by the inspection plan by virtual fitting gauges.

Figure 2 :

 2 Figure 2: The Extracted-clouds.

Figure 4 :

 4 Figure 4: Assembly of a gauge compound of two cylinders with fixed diameters.

Figure 5 :

 5 Figure 5: Assembly of a gauge compound of two cylinders which one has a variable diameter.

Figure 7 :

 7 Figure 7: Tolerances of the experimental part.

Figure 8 :

 8 Figure 8: Identification of the surfaces and construction of a Cartesian frame of the part.Stage 2: Inspection of the positional tolerance of drillings of diameter 8 :Along the Y axis of the Cartesian frame of the part, a theoretical point is built for each cylinder at (36.07 / 2) mm

Figure 9 :

 9 Figure 9: Compound gauge, CG1, for the inspection of the positional tolerance of the drillings of diameter 8 .

Figure 11 :

 11 Figure 11: Compound gauge, CG3, for the measuring of the components of location deviation of the boring of diameter 10.


Alexander Heußner

Model Extraction for Sockets-based Distributed Programs

The following short report introduces an approach to utilize unbounded, reliable fifo queues as basis for an operational semantics of distributed applications whose implementation is based on the Berkeley Sockets Api. After a sketch of Tcp and the Sockets Api, a first draft of a formalization of distributed programs is given as well as a straight-forward translation into the abstract formal model of queueing concurrent processes.

Introduction

Distributed programs that communicate by point-to-point connections over a Tcp/Ip-based network architecture are an important and ubiquitous class of applications whose complexity demands for automatic verification tools to guarantee the communication protocol's correctness. A secure protocol demands a safe transportation of messages, and, hence, most often relies on an underlying layer of Tcp whereas the interprocess communication is implemented with the help of the Berkeley Sockets Api (or "Sockets" for short). Standard examples for these kind of distributed programs are Internet clients and servers, as well as peer-to-peer and Grid computing applications. Classical verification questions are, for example, safety, boundedness, and deadlock freeness [START_REF] Holzmann | Design and Validation of Computer Protocols[END_REF]. Special attention has to be paid to partial verification or verification with respect to a given protocol specification, as the communicating programs are developed apart and independently, viz. the gargantuan number of Ftp clients and servers which -in practice -should work flawlessly together.

The Berkeley Sockets Api [BSD83] became the de facto standard for applications that communicate via Internet sockets, and most present-day operating systems contain an implementation of this Api (e.g., WinSock on the Windows platform, or as part of the glibc on Gnu/Linux). Even though originally implemented in and for C, almost all modern socket Apis in other programming languages follow its interface structure. In general, Sockets supports a wide variety of different protocol families. In this short report, we will restrict our discussion to the transmission control protocol (Tcp).

For example, Internet servers focus reliability and safety, which requires complex control structures and additional code that assures the proper behavior in (almost) all execution contexts (including also rather unlikely conditions). The automatic verification of legacy code cannot rely on building formal abstract models by hand from the source code as this would be a tedious task regarding the shear size and complexity of a typical server program. Hence, verification requires a technique for model extraction. An obvious demand for the formal model derived from code is the retransfer of the results of formal verification on this model to the original program. This depends on proving the underlying translation to be "semantically equivalent", e.g., a (bi-)simulation, or an over-/under-approximation with respect to the property to verify.

An additional problem with Sockets is the missing formal semantics: the behavior of Api calls is fixed -at least to our knowledge -only by informal, natural language documents like [START_REF] Stevens | UNIX Network Programming Vol 1: Networking APIs -The Sockets Networking API[END_REF] as well as by its implementations on different platforms which differ significantly (see [START_REF] Stevens | UNIX Network Programming Vol 1: Networking APIs -The Sockets Networking API[END_REF] for details). Consequently, justifying a model extraction method would additionally demand a formally complete and correct rigorous semantics for Sockets.

Our Contribution

We present a semi-formalization of distributed programs whose communication is implemented via calls to the Tcp part of Sockets (under certain additional background restrictions). We propose queueing concurrent processes (Qcp) as formal model to extract the basic features of distributed programs. Qcp consists of local automata models (finite automata, counter automata, pushdown automata, etc.) that communicate via reliable, a priori unbounded, point-topoint fifo channels. We conclude by a discussion why these kind of fifo channels are semantically appropriate albeit our background restrictions.

Related Work

A Sockets semantics based on bounded fifo channels and thereupon the application of the Spin model checker for verification of Sockets based applications was presented in [START_REF] De La Cámara | Model Checking Software with Well-Defined APIs: the Socket Case[END_REF]. This publication proposes a formal semantics for Sockets, before it shows the translation to Promela. This approach presents only the Sockets Api calls symbolically, whereas to surrounding code is simulated by Spin's feature to inline C code directly (which poses a problem regarding the symbolic properties one can verify against).

The previous discussion originated from a more general approach to utilize Spin for the verification of event driven distributive reactive systems [START_REF] Holzmann | An automated verification method for distributed systems software based on model extraction[END_REF], for example, to verify the alternating bit protocol.

A model for (unicast) Udp Sockets based, distributed programs that includes the handling of Icmp error messages was presented in [START_REF] Wansbrough | Timing udp: Mechanized semantics for sockets, threads, and failures[END_REF]; the latter also introduces a formal semantic model of Sockets, and relies on the Hol theorem prover for programs written in a subset of OCaml. A general comparison of different angles to attack Sockets' semantic vagueness is presented in [BFN + 05].

TCP

The transmission control protocol (Tcp) [START_REF]Transmission Control Protocol[END_REF] is the original, and nowadays omnipresent transport layer protocol of the Internet protocol suite Tcp/Ip [START_REF] Stevens | TCP/IP Illustrated[END_REF]. Tcp is connection oriented, (per default) full-duplex, stateful (i.e., a connection is closed, half-open, open, half-closed, closed), and assures the reliable transmission of information. A connection binds two different Tcp-sockets which both are given by an Ip-number (32 bit unsigned) and a Tcp-port number (16 bit unsigned). The operating system assigns sockets to running processes dynamically such that at each time each socket is bound to no more than one process. We will call the two processes linked by a connection peers.

Let a message be the atomic unit of transferred data, e.g., a letter over a finite alphabet. Note that Tcp does not transfer messages but (finite) streams of packages; Tcp collects certain smaller message to one package (i.e., Tcp's atomic unit of transmission) or divides larger messages into smaller ones depending on the byte-encoding of messages. Nevertheless, Tcp assures that a sequence of messages sent by one of the two peers will be received in the same order and without transmission error by the other. Hence, an application based on Tcp does not need to assure the integrity of the sent data itself (in contrast to Udp based programs which also need to handle Icmp error messages).

An integral part of Tcp is the sliding window protocol that determines the maximal number of packages currently in transit. Again, this is negotiated when a connection is established; the maximal size of data currently in transit is 2 16 -1 (in bytes) in the standard case or 2 30 -1 when considering Tcp window scaling [RFC1323] (which is enabled per default in most modern operating systems). Note that the latter amounts to 1GB of data currently on its way on the network, and that this 1GB can be only one continuous message or a gargantuan number of one bit messages. Nevertheless, the actual window size is dynamically adapted by the protocol itself to current network conditions (which depend on all participating nodes and routers in the network). Consequently, we need consider alternative models for this non-deterministic behavior: one can either overapproximate the window size by the maximal number of messages in transit at the same moment, or assume the window to be of "unbounded" size. We prefer the latter as it includes non-deterministically all possible window sizes, even if we possibly deal with window sizes that are in practice impossible (with respect to [RFC1323]).

Besides these standard behavior, Tcp includes numerous advanced features which need to be introduced here, as server programs tend to take any advantage possible to gain a better performance and higher reliability. Two important features are the direct access to its input and output buffer as well as out-of-band data. Each peer assigned to a socket has an input and an output buffer, these are bounded (fifo) buffers whereas the size is fixed when establishing the connection (there is a maximal size as an operating system variable); nevertheless, each peer can deliberately change unsent data in the output buffer (which is rarely done), or can peek ahead in the input buffer. All the messages that are currently transferred by the network can be seen as being stored in an unbounded fifo buffer which results in Figure 2. Out-of-band data transmission allows to transfer a signal from one peer to the other "quickly" and independent of all the other data currently in transfer. Most Tcp implementations do not establish an extra connection but tag Tcp messages by an "urgent" flag while sending, such that it will be delivered immediately to the receiving peer and not enter the input buffer. With respect to a Tcp-based application, "urgent" messages can be seen as an additional buffer of size 1 in each direction that can be read asynchronously; hence, an out-of-band signal as demanded by the Socket Api.

Berkeley Sockets

As with different implementations of Tcp, there are different "interpretations" of Sockets. To avoid confusion, we will restrict ourselves to Sockets for the Internet protocol suite and therein Tcp. Further, we assume Sockets to work in blocking mode, i.e., that sending or receiving messages are atomic actions; this is the "standard" behavior available in all Sockets implementations. Note that Sockets' underlying programming paradigm makes a difference between clients and servers even if this seems strange for nowadays peer-to-peer applications. presents their practical usage in a simple server program and their interplay as sequence diagram.

Distributed Programs

Servers in the wild heavily rely on advanced features of Sockets and Tcp (like out-of-band data), multi-threading techniques that allow to fork a sub-thread (or even another process) that takes over the current Tcp-connection, preforking/-threading to avoid forking for every incoming connection, as well as asynchronous synchronization with the operating system (e.g., for reading/writing a file).

To simplify our presentation, we assume that peers are given by monolithic programs (single thread processes) with a formal (operational) semantics for all non-Sockets parts of the code. Further, we ignore the physical location of a program, as it is located by the sockets it uses. Since we regard Sockets for interprocess communication only, we can rule out self-loops, i.e., programs that directly communicate to itself. As before, we assume Socket calls to be blocking and leave aside out-of-band data. W.l.o.g., we assume the messages exchanged on connections to be over a finite alphabet. Note that the underlying Tcp assures that messages exchanged by Sockets Api calls are handled fifo and without loss or transportation error.

Let a socket be a pair of Ip-number and Tcp-port, i.e., two unsigned numbers of 32 and 16 bits each (for Internet Protocol version 4). A socket is local to a program if the program binds this socket (explicitly by bind or implicitly by connect).

Definition 4.1. A distributed program is a tuple DP = P, sock with P a set of monolithic (local) programs. The injective function sock maps a program in P to a subset of pairs of sockets (ς 1 , ς 2 ) such that ς 1 is a local socket with respect to this program.

Note that sock maps a program to all its outgoing/incoming connections which are given as socket pairs. This may require a full unfolding of the program. As connections are per default full-duplex there is no distinction between sockets that are used to either send or receive only.

Nevertheless, there are some artifacts introduced by the translation from (unformalized) Sockets to DP. The mapping sock between processes and sockets is static, hence, cannot express the dynamic (re-)usage of sockets possible with Tcp. Nevertheless, we can assume that our translation includes this by bookkeeping different connections between the same sockets in time.

Further, we assume that each program in P has -a priori -an operational semantics with respect to all commands not in Sockets. We assert that this semantics is given as labeled transition system (Lts) wherein we treat Sockets actions as nop. This allows to use well-known techniques of model extraction, e.g., tools based on predicate abstraction or path-slicing like FeaVer [START_REF] Holzmann | Automating software feature verification[END_REF], abC [START_REF] Dams | Abstracting c with abc[END_REF], Bandera [CDH + 00], or JavaPathFinder[VHB + 03].

Queueing Concurrent Processes

A communication architecture T (or architecture for short) is a pair P, Ch with a finite non-empty set P of processes and a finite set of point-to-point channels Ch ⊆ (P × P) \ id P .

Definition 5.1. A system of queueing concurrent processes (Qcp) over a given architecture T = P, Ch is a tuple A = (S p ) p∈P , M, (Σ p ) p∈P , (∆ p ) p∈P , (s 0 p ) p∈P with M a finite message alphabet. For each process p ∈ P, the tuple S p , Σ p , ∆ p , s 0 p describes a (local) transition system on the states S p over the actions Σ p = Σ loc p • ∪Σ com p which are either local, i.e., in Σ loc p , or communication actions in Σ com p = {p!q(m) | (p, q) ∈ Ch and m ∈ M } ∪ {p?q(m) | (q, p) ∈ Ch and m ∈ M }. Local transitions are given by the rules in ∆ p ⊆ S p × Σ p × S p , and the initial state of process p is s 0 p . As usual, p!q(m) denotes the send of message m from process p to process q, whereas q?p(m) denotes the matching receive on process q.

Note also that the S p need not necessarily be finite. If all S p are finite, we will call A a finite Qcp. The local transition systems given by S p , Σ p , ∆ p , s 0 p could be, for example, finite automata, counter automata (including Petri nets), or pushdown automata. As usual, we define the semantics of A as labeled infinitestate transition system: Definition 5.2. A Qcp A represents an LTS A = C, Σ, →, c 0 with configurations C = S × (M * ) Ch and the initial configuration c 0 = s 0 , (ε, . . . , ε) , i.e., all channels are initially empty. We write a configuration as c = s, w where s = (s p ) p∈P is the global state and w = (w p,q ) (p,q)∈Ch are the channel contents. Further, for any p ∈ P and a ∈ Σ, s, w a -→ s ′ , w ′ is a transition in C ×Σ ×C if (s p , a, s ′ p ) ∈ ∆ p and the following holds: (i) s q = s ′ q for all q = p, (ii) if a ∈ Σ loc p then w = w ′ , (iii) if a ∈ Σ com p with a = p!q(m) then w ′ p,q = w p,q m and w ′ s,t = w s,t for (s, t) ∈ Ch\{(p, q)}, (iv) if a ∈ Σ com p with a = p?q(m) then w q,p = mw ′ q,p and w ′ s,t = w s,t for (s, t) ∈ Ch\{(q, p)}.

Note that the rules regarding Σ com force a fifo semantics on the channels.

Formal Matching

We translate a given a distributed program DP = P, sock to a Qcp A = (S p ) p∈P , M, (Σ p ) p∈P , (∆ p ) p∈P , (s 0 p ) p∈P over an architecture T = P, Ch as follows:

each program in P is mapped one-to-one to a process in P -(p, p ′ ) ∈ Ch iff there exist two sockets ς, ς ′ such that (ς, ς ′ ) ∈ sock (p) and (ς ′ , ς) ∈ sock (p ′ ). -the local transition system S p , Σ p , ∆ p , s 0 p is an "adequate" semantic model for the program mapped to process p (when treating all actions in Σ com as local nop) -M is the finite alphabet of messages exchanged in DP a write action of a message m on a connection (ς, ς ′ ) is mapped to p!q(m) with (ς, ς ′ ) ∈ sock (p) and (ς ′ , ς) ∈ sock (q) -analogously, the matching reception of message m is mapped to q?p(m) Note that each connection in DP is mapped to a pair of channels with different directions in Ch. Hence, Qcp models of DP are inevitably cyclic.

As discussed in Section 2, reliable and unbounded fifo channels seem a natural choice to model connections in distributed programs. Reliability is guaranteed by Tcp and the assumption of unbounded channels avoids any occupation with the dynamic change of sliding window sizes.

Conclusions

The previous short report shows a possible way to use a fifo semantics for Berkeley Sockets based distributed applications. This further allows to use Qcp as abstract model and verification methods based thereupon.

For future implementations, a more detailed semantic discussion of DP and its mapping to Qcp is unavoidable. Further, one should try to reduce the implicit and explicit assumptions and restrictions included by our modeling and to extend the model to include the dynamic behavior of Tcp as well as specialties like outof-bound data.

Fig. 1 .

 1 Fig. 1. Message Buffer Representation for Tcp

Fig. 2 .

 2 Fig.2. Socket Examples from[START_REF] Stevens | UNIX Network Programming Vol 1: Networking APIs -The Sockets Networking API[END_REF]

Table 1 .

 1 Basic Sockets Api Calls

	command	(natural language) semantics
	socket	create a (local) socket of a type, e.g., a Tcp socket
	bind	bind local socket to Ip-address and Tcp port
	listen	set underlying socket to listen mode (server)
	connect	connect to remote socket (client, binding local socket implicit)
	accept	accepts an incoming connection (server)
	read, write read, write from/to socket
	close	remove socket

Sockets includes different types of Api calls for different classes of tasks: (i) establish and maintain a connection, (ii) send and receive messages, (iii) auxiliary methods to adapt to the local machine (e.g., converting endianness of Ip addresses). Table

1

gives a natural language semantics of these calls; Figure

2


Faraz Zaidi
email: faraz.zaidi@labri.fr

Arnaud Sallaberry
email: arnaud.sallaberry@labri.fr

Guy Melanc
email: guy.melancon@labri.fr

Revealing Hidden Community Structures and Identifying Bridges in Complex Networks: An Application to Analyzing Contents of Web Pages for Browsing

The emergence of scale free and small world properties in real world complex networks has stimulated lots of activity in the field of network analysis. An example of such a network comes from the field of Content Analysis (CA) and Text Mining where the goal is to analyze the contents of a set of web pages. The Network can be represented by the words appearing in the web pages as nodes and the edges representing a relation between two words if they appear in a document together. In this paper we present a CA system that helps users analyze these networks representing the textual contents of a set of web pages visually. Major contributions include a methodology to cluster complex networks based on duplication of nodes and identification of bridges i.e. words that might be of user interest but have a low frequency in the document corpus. We have tested this system with a number of data sets and users have found it very useful for the exploration of data. One of the case studies is presented in detail which is based on browsing a collection of web pages on Wikipedia 1 .

Introduction

Information Analysis (IA) or more precisely Content Analysis (CA) is an active area of research where the goal is to explore and analyze contents of a set of documents in order to discover patterns and hidden knowledge [START_REF] Thai | Ivea: An information visualization tool for personalized exploratory document collection analysis[END_REF]. Weare provides a good overview of the challenges presented to the CA research community by the World Wide Web [START_REF] Weare | Content analysis of the world wide web: Opportunities and challenges[END_REF]. Document Content Visualization Systems can be used as a tool for CA where the goal is to represent textual contents of a set of documents in a visual form so as to facilitate the process of mining and discovering patterns in a collection of documents [START_REF] Neuendorf | The Content Analysis Guidebook[END_REF] [START_REF] Grobelnik | Visualization of news articles[END_REF].

A typical application of CA in the domain of web is the analysis of the set of web pages browsed by a user in 1. http://en.wikipedia.org/wiki/Main Page order to find required information. While browsing a web page having external links; it is imperative for the users to browse each and every external link if further information is required. This task is not only time consuming but makes it difficult for the users to relate contents of web pages to each other. Moreover apart from going over a single web page, most of the time, users tend to collect a set of web pages rather than a single web page to obtain information [START_REF] Wu | Finding more useful information faster from web search results[END_REF]. In case of browsing, it means that a user would explore the links in the selected pages further to extract more information.

As an example consider browsing the web page 'CAC 40' on the Wikipedia encyclopedia. CAC 40 is a benchmark french stock market index which represents a capitalizationweighted measure of the 40 most significant values among the 100 highest market caps on Euronext Paris2 . There are many external links on this page and users searching for more details would use these external links to look for further information. Usually they will go through the web pages one at a time to find more information which makes it difficult to relate what they have already found as information.

Ideally the users want a system that collects pages referred in the initial web page and display their contents in a manner that groups the pages together based on the content. This would give the user an idea about the sub-topics that revolve around the major topic. For example, a quick look on the CAC 40 Wikipedia page would suggest the other related indices like 'CAC Next 20', 'CAC Mid 100' and 'CAC Small 90' as possible topics related to 'CAC 40'. All these indices represent the highest equities on Euronext Paris where CAC Small being the lowest of these all.

Moreover the users would like to see how these subtopics are related to each other. Words appearing in more than one document can play a role of bridges between these groups thus creating a link between words from two different groups. Nodes organized into circles in Fig. 1 cor- Clearly, the figure shows that documents roughly organize into three different subgroups of topics, labeled as "French companies", "CAC 40" and "CAC Small 90". In other words, Fig. 1 shows the "community structure" of web pages [START_REF] Girvan | Community structure in social and biological networks[END_REF] [START_REF] Auber | Multiscale visualization of small world networks[END_REF]. Additionally, a few nodes have been isolated and bridge these subgroups, further indicating topics that link the different subgroups. The bridging nodes thus sit out of the community structure (the structural hole as Burt names it [START_REF] Burt | Brokerage and Closure[END_REF]) and act as broker between communities.

Our starting point is thus the network of links between words extracted from web pages. As we shall see in the coming sections( 3), the plain network we obtain after the extraction process is actually quite complex and its structure forbids to use it as a graphical representation as such. The problem we address in this paper is to reveal hidden community structures in complex networks. Our approach also allows us to identify the bridges within these networks. The uncovered structure can then be used to build a graphical representation of the whole network to help visualize and interactively explore these relationships.

We represent the contents of the web pages through a graph or a network, where the nodes represent the words appearing in web pages and the edges showing that two words appear together at least once on a web page. Clustering and Visualization of a network constructed this way is a challenging problem because having a closer look at the network properties, we find that these networks have the properties of small world [START_REF] Milgram | The small world problem[END_REF] and scale free [START_REF] Barabasi | Emergence of scaling in random networks[END_REF] structures.

A small world network can be defined by two structural parameters: the average path length [START_REF] Milgram | The small world problem[END_REF] and the clustering coefficient [START_REF] Watts | Collective dynamics of 'smallworld' networks[END_REF] of nodes. The path length refers to the minimum number of edges traversed to go from a node A to node B. The average path length is the average calculated for all pair of nodes in a network. The clustering coefficient of a node is defined as the ratio between the total number of connections among the neighbors of that node to the total number of possible connections between the neighbors. A high clustering coefficient means that the neighborhood shares lots of connections among themselves and thus form a community. A scale free network is a network in which the connectivity of nodes follow a scale-free power-law distribution [START_REF] Barabasi | Emergence of scaling in random networks[END_REF]. This means that there are a few nodes that have a very high number of connections(degree) and lots of nodes are connected to a few nodes. The degree distribution of the network taken as an example is shown in figure 2 where the long tail like structure represents the nodes with high number of connections.

The most common networks having these properties of both scale free networks and small world networks are the Internet Movie Database and the Coauthoring Network [START_REF] Guillaume | Bipartite graphs as models of complex networks[END_REF]. For the rest of the paper, we use the term complex network to refer to a network which has both small world and scale free properties. A Cooccurrence network is another example of a complex network. This network is built when one considers a book or queries to a search engine, one can construct a co-occurrence graph of words if they appear in the same sentence or on the same page [START_REF] Ferrer I Cancho | The small world of human language[END_REF]. This is the graph that we construct considering the web pages browsed by a user while exploring for information (see section 3 for details).

We know that due to the scale free property, it is difficult to cluster a network or visualize communities within the network structure [START_REF] Ignacio Alvarez-Hamelin | k-core decomposition: a tool for the visualization of large scale networks[END_REF]. This is due to the fact that a few nodes have a very high degree and they create links between the underlying community structure hiding the communities. Figure 3 shows the co-occurrence network obtained by browsing pages on the Wikipedia encyclopedia starting from the CAC 40 page (see section 3 for details). We have used a graph drawing algorithm proposed by Frick [START_REF] Frick | A fast adaptive layout algorithm for undirected graphs[END_REF] implemented in Tulip software 3 . This is force directed algorithm which is well suited to our problem as it puts the nodes that are densely connected to each other closer hence making it easier to locate the community structures. But from the figure it is quite evident that in the presence of very high degree nodes it is very hard to identify different communities visually.

The proposed system addresses two main problems in the analysis of complex networks. First is revealing the community structures hidden in the network through simplification of the graph and clustering. As an example we consider the co-occurrence graph of words extracted from a set of web pages. In the discussed example of CAC 40 is the major The second is identification of words that are interesting from a user perspective to study the relationship between clusters but have a low frequency in the entire document corpus. These words can help us to uncover hidden information and discover relationships that are not apparent in the original network or difficult to locate. For example a company linking web pages from CAC Next 20 and CAC 40 might be a good candidate of a company that has interests in equities from CAC Next 20 and CAC 40. This company name should be represented separately as a bridge that the user can find easily without having to go through the two web pages and deduce this relationship.

The major contributions of the proposed system are: a methodology to cluster complex networks based on duplication of nodes, a method to focus on Bridges that are interesting from a user perspective, discover hidden (or not so obvious) relationships between subtopics based on these Bridges. We use Micro/Macro graph layout algorithms [START_REF] Baur | Multi-circular layout of micro/macro graphs[END_REF] to visualize the final network which helps us to develop an overall picture of the distribution of the contents of the collected set of web pages.

The rest of the paper is organized as follows: In Section 2 we present the related work. We describe the data set used as an example in section 3 and the proposed system in section 4. Section 5 discusses the results that we obtained by the application of our framework on the sample data set. Section 6 contains the conclusion and future research prospects, advancements and ameliorations possible to the current system.

Related Work

Document Content Visualization has been studied in details by various researchers and different visualization systems have been proposed such as [START_REF] Grobelnik | Visualization of news articles[END_REF] [START_REF] Fortuna | Visualization of text document corpus[END_REF]. Most of these systems are useful to identify the key words in a document collection. They use the classical techniques to calculate the relationships between documents like the tf-idf score [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF] which makes it difficult to focus on low frequency words that appear in only a few documents.

Web search results visualization which is different from web browsing visualization is also an active area of research where most of the research has been directed towards two objectives. One is, towards showing the connection between the user query and the resulting web pages [START_REF] Nguyen | A novel visualization model for web search results[END_REF] and two, effective organization and clustering of search results [START_REF] Bonnel | Effective organization and visualization of web search results[END_REF]. None of these systems perform content analysis as their primary task is to help users find web pages relevant to their query. Some of these systems perform clustering based on the content of the web pages [START_REF] Zeng | Learning to cluster web search results[END_REF] but none of these focus on showing the bridges that create links between these documents.

Clustering and Visualization of a network or graph having small world and scale free properties at the same time, to the best of our knowledge, has not attracted much attention in the clustering domain. Boutin et al. [START_REF] Boutin | Focus-based filtering + clustering technique for power-law networks with small world phenomenon[END_REF] tried to address this issue by introducing a filtering method based on userfocus. This technique extracts a tree-like graph so that the resulting structure can be drawn using any force directed algorithm leaving the final drawing easily readable. One of the drawbacks of this system is that the user has to choose an initial entry point to filter the graph. The system we propose require no such information. Moreover since edges are removed to simplify the structure of the network, important information can be lost. We preserve the original network without removing any edges or nodes thus no information loss occurs and the user is free to navigate in the entire network all the time.

Girvan et al. [START_REF] Girvan | Community structure in social and biological networks[END_REF] proposed a clustering algorithm for complex networks based on the betweenness centrality. This algorithms performs well but produces a hierarchical clustering which is not well suited to browsing problem addressed in this paper. Moreover it does not cater the problem of reducing the inter-cluster edges thus making it difficult for visualization.

Methods have been proposed to cluster and visualize scale Free networks based on filtering [START_REF] Päivinen | Clustering with a minimum spanning tree of scale-free-like structure[END_REF] [19] of nodes or edges but some loss of information occurs at the same time. For example [START_REF] Ignacio Alvarez-Hamelin | k-core decomposition: a tool for the visualization of large scale networks[END_REF] [START_REF] Jia | On the visualization of social and other scale-free networks[END_REF] propose a recursive pruning method called K-core which is a method to simplify large scale free networks for visualization. It progressively allows the detection of central nodes in the network but the grouping is solely based on the topology and does not reflect the similarity of the nodes. [START_REF] Päivinen | Clustering with a minimum spanning tree of scale-free-like structure[END_REF] proposed a method based on the on Minimum Spanning tree(MST) , where the goal is to construct a MST of the network thus reducing the network from a graph to a tree. This essentially requires deletion of edges and loss of information does occur.

Efficient algorithms to cluster and visualize small world networks have been proposed like [START_REF] Auber | Multiscale visualization of small world networks[END_REF] [START_REF] Van Ham | Interactive visualization of small world graphs[END_REF]. These systems perform well if the topology of the network follows small world properties but fail to perform in the presence of scale free properties. This is due to the fact that in a scale free network, a few nodes dominate the entire networks connections and makes it difficult to identify the communities.

Collection and Preprocessing of Data

The data set that we have used for experimentation is the collection of key words found in the Meta tag of a set of web pages. These web pages were collected starting from the page CAC 40 on Wikipedia 4 . All the pages in the 'See Also' section were further explored and the process was repeated for links up to depth 3. A total of 50 web pages were collected this way. The choice of selecting 50 pages was influenced by the study [START_REF]iprospect's search engine user attitudes[END_REF] which shows that users will try a new search after browsing at most 30 web pages in case of searching a web page on the Internet. The total number of words collected after the removal of stop words (like 'for', 'the' etc.) was 412.

The entire data set can be represented by 3 tuples. One for the Words (words), second for the documents (document title, hyper link) and the third representing relationship between the documents and the words, Relationship(Document title, words).

From this data set, two different graphs can be constructed. A graph of Web page-Word and a Word-Word graph. In a Web page-Word graph, the nodes represent the web pages and the words where an edge between a web page and a word represents that the word appears in that web page. This graph by construction forms a bi-partite graph where there are no edges between words and similarly there are no edges between the web pages. We use this graph to find the words that appear in many web pages as the degree of a word represents the number of web pages it appears in.

The other graph is the word-word graph which we eventually use for visual analysis of the network. The nodes represent the words and an edge between two words represent that they appear together in at least one web page. This final graph contains 412 nodes and 5817 edges. The graph is shown in Fig. 3. An important observation about this graph is that the words that appear in a single web page would be connected to each other thus forming a clique. Looking carefully at Fig. 3, the set of nodes that form a group and are densely connected to each other most probably belong to the same web page.

Framework of Proposed System

The inspiration to the proposed system comes from the fact that if we are somehow able to reduce the complex graph (a graph with both scale free and small world properties) to a small world graph, clustering and visualization of a small world graph is much easier especially if the resulting graph has communities with high intra community edges and low inter community edges [START_REF] Auber | Multiscale visualization of small world networks[END_REF].

To reduce the complex graph to a small world graph without scale free property we duplicate nodes that have a very high degree thus leaving us with only a small world network. In our case, duplicating the high degree nodes means that the words that are present in a majority of documents are duplicated such that they are assigned a new identity in each and every document they appear. Thus they are treated as words that appear only in a single document. This is done so in order to reduce the inter-cluster edges which in turn, results in a more readable visualization of the network. Thus revealing the community structure visually. Then we use the Betweenness Centrality introduced in [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] (see also [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF] for implementation) to identify the nodes that lie between communities of words representing the small world structure. These are the words that are present in a few documents only and play the role of bridges between web pages, i.e. they link different web pages. After identifying these words, we remove them temporarily further simplifying the entire network to reveal disconnected or loosely connected communities. A clustering algorithm can be applied to clusterize this network.

Once the clusters are found, the words that were initially duplicated might found themselves in the same cluster. We remove the duplicated nodes within clusters so as to keep a single copy of the duplicated nodes. Then we reintroduce the nodes having high betweenness centrality that were removed temporarily and we identify them as Bridges.

Finally the network of clusters and Bridges is drawn using a graph drawing algorithm. We associate a different color to identify the nodes that are duplicated in the network so as to show users the nodes that are present in other clusters as well. Thus we have nodes that have two different colors (see Fig. 7(a)), representing nodes that appear only once or are duplicated. A simple interaction by clicking a duplicated node is introduced to trace the presence of a duplicated node in the entire network by associating a third color (see Fig. 7(b)). The following sections discuss our framework in detail. In order to find the words to be duplicated, we use the bi-partite graph of words and documents as described in section 3. Once we have the Web page-Word graph, we need to identify the words that are present in many documents. The degree of the nodes in this graph represents the number of documents a word appears in. Fig. 6 shows the frequency distribution of the words and the web pages. The x-axis represents the number of documents and the y-axis represents the frequency of words. For example the point 'a' in the Fig. 6 means that there are just a little over 30 words that appear in exactly three web pages.

Since the idea is to duplicate words that appear in many documents, we need to find the proper definition of what many document means for this network. Looking at Fig. 6 we calculate the slope of every two consecutive points. At point b the slope becomes equal to zero. This gives us a heuristic which suggests that as the slope becomes zero or close to zero (values of -1 or -2) this point can be considered as the cutoff point. In the given example, it turns out to be 6, meaning that all the words that appear in 6 or more documents must be duplicated. Although this heuristic provides a good starting point for the system, the user is free to manually choose a value for the degree a part from which the nodes would be duplicated. Lower the value chosen, higher would be the number of words being duplicated and the eventual word-word graph would become more disconnected.

An example of a word that might be duplicated is the word 'France' since CAC 40 is an index for french stock exchange, it is quite obvious to find this word in many documents. This step introduces new nodes in the word-word graph but keeps the number of edges exactly the same. Thus the graph gets simplified as shown in Fig. 5(a) and 5(b).

Iterative removal of Nodes with high Betweenness Centrality

Once we have the word-word graph with duplicate nodes, we calculate the betweenness centrality of the nodes which is a metric proposed by Freeman [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF]. It calculates the relative importance of nodes within a network by calculating the shortest paths between pairs of nodes. Nodes that occur on many shortest paths between other nodes have higher betweenness than those that do not. This metric is a good representation of the nodes that play the role of connecting different communities and thus helps us in identifying the bridges.

Girvan et al. [START_REF] Girvan | Community structure in social and biological networks[END_REF] have used a clustering algorithm which is based on a modified form of this metric. They calculate edge betweenness based on the same principal where they find edges that are central to a network. Then they iteratively remove the most central edge in the network and recalculate the edge betweenness until no more edges are left.

Since our goal is to find the bridges we apply the same method on nodes to identify the bridges. We calculate the betweenness centrality of the nodes, remove the node with the highest betweenness centrality and repeat this process a certain number of times. Girvan repeated the process until there were no edges left as the goal was to produce a hierarchical clustering. We use a heuristic to determine the number of iterations which is based on the total number of documents used for extraction of words and the number of bridges we want to see between groups of documents. For the given example we choose 15 as it would give us a bridge for nearly every three documents.

N umber of Iterations = N umber of Documents/3

(1) Where represents the ceiling function. The user is free to choose any value depending on the requirements, higher the number of iterations and higher would be the number of bridges and smaller would be the size of clusters. Fig. 5(c) represents the graph after the removal of nodes with high betweenness centrality.

Finding Communities through Clustering

A clustering algorithm is required to find clusters in this processed graph. Most of the clustering algorithms require some parameters as input such as number of clusters to be found, initial centroids, a threshold etc [START_REF] Berkhin | Survey of clustering data mining techniques[END_REF] [18] [START_REF] Yoo | A comprehensive comparison study of document clustering for a biomedical digital library medline[END_REF]. Since we want to avoid bothering the user with the requirement of this additional information, we prefer an algorithm that does not require any information from the user. Strength clustering proposed by Auber et al. [START_REF] Auber | Multiscale visualization of small world networks[END_REF] is a good choice as it requires no such parameter. It is well suited to our problem as it was particularly designed to find communities in small world graphs.

Once the clusters are found, each and every cluster is scanned for nodes that were duplicated and found themselves in the same cluster. We remove this node duplication within a cluster and keep a single instance of a duplicated node within a cluster.

Reintroducing Nodes with High Betweenness Centrality and Identification of Bridges

The next step after clustering of the nodes is to reintroduce the nodes that were earlier removed due to high betweenness centrality. These nodes are considered to be the Bridges as they are responsible for connecting different clusters. Keeping in view that the words that were present in many web pages were duplicated and thus their degree was reduced, the nodes having high centrality in this final network are words that appear in a few web pages only. These words are important from the user perspective as they link web pages and might play an important role to understand the relationship between webpages.

Visualization of Clusters and Bridges

The final graph is visualized using a variation of the Micro/Macro graph layout algorithms [START_REF] Baur | Multi-circular layout of micro/macro graphs[END_REF]. Providing a detailed account of the layout algorithm we designed is out of the scope of this paper. Roughly speaking, once communities have been identified they are treated as metanodes and fed into a force-directed layout, as to benefit from their aesthetics and readability [START_REF] Ioannis | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF] [START_REF] Wagner | Drawing Graphs, Methods and Models[END_REF]. The GEM algorithm [START_REF] Frick | A fast adaptive layout algorithm for undirected graphs[END_REF] has been adapted as to take node size into account in order to reflect the size of a cluster (number of words it contains).

To draw the nodes representing words within a cluster we use a simple placement strategy. They are placed uniformly on the circumference of the circle surrounding the cluster. The ordering of nodes must however be decided in order to minimize the number of edge crossings it might introduce in the final drawing. Two different colors are associated to the nodes within a cluster. (Light green and dark green as shown in Fig. 7.) The light green color represents the nodes that are duplicated throughout the network. An important interaction is clicking on a duplicated node, which highlights all of its instances in the entire network as shown in Fig. 7(b) using a different color (Pink) and size. This is to help locate the duplicated instances of a node in the network.

Results and Discussion

Figure 7 shows a small part isolated from Fig. 5(d). Fig. 7(a) shows the three clusters represented by circular structures having many small nodes and the bridges which are labeled 'A novo', 'AXA', 'Accor' and 'number'. The first three represent french companies and the bridge 'number' Looking at the clustering, The first cluster, which contains the CAC 40 and the Euronext Paris, it is obvious that these two pages find themselves in the same cluster as they both represent the Paris Stock Exchange. 'AXA' and 'A Novo' are two companies where AXA is listed in the CAC 40 and A Novo is listed in CAC Small 90. Finding CAC Small 90 with Investment Management makes sense as AXA is a french company interested in investments and targets companies in the CAC Small 90 as a possible investment opportunity where A novo is an example of a possible future investment. Similarly the relation between List of french companies and CAC 40 through Accor suggests that Accor is a french company listed in CAC 40.

All this analysis is a direct result of the visual repre-sentation of the network. Clusters group things that have similarity based on the content and Bridges are responsible for creating relationships between these clusters giving an overall understanding of the data set.

Conclusions and Future Work

In this paper we have presented a system to visualize and explore complex networks revealing clusters and detecting bridges in a set of web pages. The system was tested with several examples considering the web pages browsed by users. The in-house informal tests with different users indicate that the system was found to be very useful to develop and overall understanding of the collection of web pages. The identification of the subtopics revolving around the primary search topic was a direct result of the clustering. The identification of the words that play the role of bridges between these different subtopics was also found to be very useful.

The system was tested with small data sets as the web browsing on a single topic does not require to evaluate hundreds of web pages at the same time. Similarly the size of documents was not very huge as web pages usually have a very limited size as compared to books, newspapers etc. As part of the future work, we would like to test the system to visualize web search results as compared to browsing. We would also like to ameliorate the system to incorporate the exploration of complex networks of large sizes such as the Internet Movie Database. We also plan to introduce more interactions to facilitate the user navigation like deleting nodes, dragging nodes from one cluster to the other etc.

Figure 1 .

 1 Figure 1. Web Pages and Bridges

Figure 2 .

 2 Figure 2. Plot of the node degree distribution : degrees appears on the x-axis and the frequencies associated on the y-axis.

Figure 3 .

 3 Figure 3. Co-occurrence Network of Words: Pages Browsed from CAC 40 Wikipedia web page

  4. http://en.wikipedia.org/wiki/List of french companies

Figure 4 .

 4 Figure 4. Proposed Framework

Figure 5 .

 5 Figure 5. (a) Word-Word Graph constructed from browsing CAC 40 and related web pages (b) Graph after node duplication (c) Graph after removing bridges (d) Graph with Clusters and Bridges using proposed visualization

Figure 6 .

 6 Figure 6. Number of Web pages on the x-axis and Number of Words on the y-axis

Figure 7 .

 7 Figure 7. (a) A small part isolated from Fig. 5(d) showing Titles of Webpages clustered together and Bridges(b) Duplicated nodes highlighted after selection

http://en.wikipedia.org/wiki/CAC 40

http://www.tulip-software.org/

Acknowledgment

This project was partly funded through the ANR project RNTL FIVE 06 TLOG 12. The project aims to develop visual interfaces to exploit effectively the information collected as a result of text mining of web pages and introduce modes of interaction to help analysts monitor and extract information. We would like to thank the members of the organization Pikko 5 , Mr. Emmanuel Pellegrin who helped us analyze and interpret the data and Mr. Guillaume Aveline who helped us to collect the data.