Stéphane Klein
email: sklein@eit.uni-kl.de

Georg Frey
email: frey@eit.uni-kl.de

Jean-Jacques Lesage
email: lesage@lurpa.ens-cachan.fr

Lothar Litz
email: litz@eit.uni-kl.de

SUPPORTING THE CHANGEABILITY OF SIPN-BASED LOGIC CONTROL ALGORITHMS BY VERIFICATION AND VALIDATION

In this paper the advantages of verification and validation to support changes of an existing PLC program are shown. The controller is defined using Signal Interpreted Petri Nets (SIPN) and verification and validation are performed using symbolic model-checking. The main focus of this paper is to show the process and the benefits of verification and validation for the reliability of the control algorithm when specified changes are to make. This is clarified by the example of a heating tank controller throughout the text.

INTRODUCTION

In industrial applications, PLC programs are often modified to take into account changes of the plant or of the requirements. Using formal methods to develop control algorithms enhances their changeability. Formal methods like verification and validation (V&V), together with appropriate formal algorithm descriptions like SIPN prove the requirements to be fulfilled. This paper points out how V&V can be used to modify successfully an existing control algorithm. Indeed it will be shown that modifying a correct algorithm often leads to formal and functional requirements no longer to be fulfilled. Using V&V, the errors can be found and solved before the control algorithm is implemented on the PLC. This paper is organized as follows. In section 2, the SIPN concept is briefly presented and used to design a first control algorithm for a heating tank. Section 3 discusses verification, validation and the model-checking technique. They are applied on the former designed SIPN in section 4. In section 5 the informal specification is extended and the algorithm is redesigned. It is shown how to develop the new algorithm step by step and how to ensure the quality of the resulting algorithm by verification and validation. Finally, section 6 concludes the paper. with the sets P of places, T of transitions, F of arcs and an initial binary marking M 0 like in ordinary C/E Petri net. To become SIPN, the extensions are: -Transitions are associated to a set C of firing conditions as Boolean functions of the input variables I. -Places are associated with a mapping A of actions defining a subset of output signals O. Marked places define a subset of output signals -A Signal Algebra Ω defines how to handle the output subsets of all binary marked places. For a more formal definition of SIPN, see [START_REF] Frey | Design and formal Analysis of Petri Net based Logic Control Algorithms[END_REF].

2.2

Dynamic behavior The dynamic Behavior of an SIPN is given by the firing process defined by four rules, see also Figure 1: 1. A transition is enabled, if all its pre-places are marked and firing ensures binary marking of all its post-places. 2. A transition fires immediately, if it is enabled and its firing condition is fulfilled. 3. All transitions that can fire and are not in conflict with other transitions fire simultaneously. 4. The firing process is iterated until a stable marking is reached (i.e. until no transition can fire anymore). Since firing of a transition is supposed to take no time, iterative firing is interpreted as simultaneous, too. For that reason, no changes of input signals may occur during the firing process.

After a new stable marking is reached, the output signals are computed according to the marking and the signal algebra.

Read input signals

Compute firable transitions

Fire transitions AND Set new marking

Compute output signals

Stability check

Non stable marking

Stable marking

Example

As an example for controller design with SIPN, a heating tank is used. A description of the tank is given in Figure 2 and the signals are defined in The informal specification is the description of the client's requirements in natural language. These are: After pressing the start button the tank is filled. The full tank is heated until the desired temperature is reached.

Then the heated tank is emptied. During the whole process the contents are stirred.

2.4

Design of the control algorithm Based on the informal specification, the control algorithm is designed using SIPN. This algorithm is given in Figure 3. Starting form the initial place P1, transition T1 can fire if the tank is empty (!i1), not full (!i2) and the start button (i4) is pressed. After this transition has fired, the stirring motor is set ON (o3 = 1) in place P2 and the tank is being filled (o1 = 1) in place P3. Once the tank is full and the temperature of its contents is beyond the desired limit (i3 = 1), transition T2 fires and the tank is emptied (o2 = 1) in place P5. If the temperature of the full tank is below the limit, the contents are heated (o4 = 1) in place P4 before the tank is emptied in P5. When the tank is empty, transition T5 fires and the initial state where al the actions are set to 0 is reached again.

P1 ・Stand by (0, 0, 0, 0) P2 Stirring (-, -, 1, -) P3 ・Filling (1, 0, -, 0) P4 ・Heating (0, 0, -, 1) P5 ・Emptying (0, 1, -, 0) T1 ・Start i4 & !i1 & !i2 T2 Temp. OK i2 & i3 T3 -Temp. low i2 & !i3 T5 -Tank is empty !i1 & !i2 & !i4 T4 -Temp. OK i2 & i3

VERIFICATION AND VALIDATION

3.1 Definition Verification and Validation are often confused. Therefore, let us remind the definitions given by Boehm [START_REF] Boehm | Guidelines for Verifying and Validating Software Requirements and Design Specifications[END_REF]:

"Verification: am I building the product right ?" "Validation: am I building the right product ?" Hence, according to [START_REF] Roussel | Validation and Verification of grafcets using finite state machine[END_REF], the verification is the proof that the internal semantics of a model is correct without regard to the modeled system whereas the validation determines if the model agrees with the designer's intention. In [START_REF] Frey | Design and formal Analysis of Petri Net based Logic Control Algorithms[END_REF], four properties for the formal correctness of an algorithm are defined. Besides completeness they ensure the deterministic behavior of the control algorithm, which can be defined in an informal way as follows:

Every control algorithm must have deterministically defined dynamics and I/O-behavior. If it had not, its behavior in a given situation would depend on implementation aspects. In detail, this means that in every state of the control-ler the reaction on possible input signals is defined and a non-contradictory value for each output signal is specified.

Properties like these (verification part) are widely accepted as mandatory and can be found in many works on formal methods in control. They can be automatically formulated for every designed SIPN. Properties to express that the designed SIPN fulfills the customer's needs are problem-dependent (validation part). Hence, there is no way to formulate them automatically. They must be generated anew for every problem. Nevertheless, with symbolic model-checking [START_REF] Bérard | Systems and Software Verification, Model-Checking Techniques and Tools[END_REF] the same method can be used to perform V&V.

3.2

Model-checking Model-Checking is a technique in which a finite state model of the system is built and the expected properties of the system are checked on this model [START_REF] Lampérière-Couffin | Formal Validation of PLC programs: a Survey[END_REF]. The system is modeled as a finite state machine, whose evolution is given in an algorithm and the properties are expressed in a temporal logic. A search procedure (exhaustive state space search) is then used to check whether the expected properties hold on the finite state transition system or not. Figure 4 shows the tasks that have to be done within the modelchecking procedure. In this work, the symbolic model-checker SMV [START_REF] Mc Millan | The SMV system for SMV version 2.5.4[END_REF] is used to perform V&V.

3.3

Temporal logic formulae The properties that are to be checked have to be written in temporal logic (TL) [START_REF] Bérard | Systems and Software Verification, Model-Checking Techniques and Tools[END_REF]. This is a special logic tailored for statements and reasoning which involve the notion of order in time. In TL, the parameter t (time) is not explicitly present in the formulae. TL offers concepts immediately ready for use. Its operators mimic linguistic constructions (the adverbs "always", "until", the tenses of verbs, etc.) with the result that natural language and their TL formalization are fairly close. The SMV model-checker uses Computation Tree Logic (CTL), which is together with PLTL (Propositional Linear Temporal Logic) the most used TL in modelchecking tools. An application of V&V on SIPN using model-checking with CTL formulae is described in [START_REF] Weng | Model checking: towards generating a correct specification for logic controllers[END_REF].

V&V PROCESS BY EXAMPLE

4.1 Specification To apply V&V on the controller designed in sub-section 2.4, formal properties have to be derived by formalization of all the informal specifications given in sub-sections 2.3 and 3.1. The specification in 2.3 was also used to formalize the control algorithm by SIPN. It may seem to be redundant having two different formalization steps. But two formalizations performed by different methods (SIPN and TL) considerably enhance the reliability. For it is very improbable to make the same mistake twice following the completely different attempts of SIPN and TL. To be used in V&V with model-checking, the SIPN has to be translated into SMV input code. This translation considers the structure and the evolution of the SIPN, as well. To reproduce the evolution algorithm of an SIPN (Figure 1), a variable eoc (End of Cycle) [START_REF] Canet | Towards the automatic verification of PLC programs written in Instruction List[END_REF] is introduced. It is set to 1 as soon as a stable marking is reached. No more transition can fire in that case without changing of the input values. Hence this variable when remaining false all the time detects infinite loops in the control algorithm, called unstable marking. During V&V eoc is used to check properties involving output signals since these are only set in stable markings. For more details see [START_REF] Klein | Designing fault-tolerant controllers using SIPN and model-checking[END_REF].

4.2

Verification Verification has to make sure hat the designed SIPN behaves in a deterministic way yielding the properties: 1. The algorithm always produces stable markings whatever happens in the future. In TL, this is

AG EF eoc 2.
The output signals are correctly defined, meaning that in every stable marking an output signal oi is set either to 0 or to 1 (XOR).

AG ! (eoc & ((set_oi & reset_oi) | (!set_oi & !reset_oi)))

3. There are no transition conflicts. When there is a choice between several ways to mark or unmark a place, only one of them must be possible:

AG ! (T2 & T3)
These properties ensure that the designed SIPN has a deterministic behavior. Some further properties about the behavior of the SIPN can be added. These are: 4. The algorithm is reversible, i.e. the initial marking can always be reached again:

AG EF m0

5. The SIPN is live, i.e. every part of the controller can be executed again and again:

AG ((EF T1) | (EF T2) | (EF T3) | (EF T4) | (EF T5))

6. The algorithm is deadlock free. This means that the algorithm never gets stuck without any way to evolve:

AG EF (T1 | T2 | T3 | T4 | T5)
Using SMV to perform verification, the six properties were all verified on the given SIPN.

4.3

Validation The validation has to check whether the designed control algorithm fulfills the functional specifications given in 2.3 in an informal way. Formalization means translating them into temporal logic formulae. Let us consider two properties: Property 1: The contents of the tank remain stirred during the whole process. First "during the whole process" has to be defined. In this case, it means during the phases where the tank is filled, heated and emptied. Therefore, we can express this property as follows: When the tank is being filled, heated or emptied, the stirring motor has to be turned on. In TL, the following formula results:

AG ((o1 | o2 | o4) -> o3)
Property 2: When the start button is pressed in the initial state the tank must be filled. Here the "initial state" has to be interpreted in a more technical sense. The tank has also to be empty at the beginning of the cycle. Furthermore, outputs are only computed after a stable marking has been reached. Hence the property can only be checked on stable markings. This results in:

AG (m0 & !i1 & !i2 & i4 & eoc -> AX o1)
After the translation of the SIPN, the validation is performed using SMV and does not show any errors. As the SIPN has been verified and validated, it can now be implemented on a PLC.

CHANGEABILITY AND V&V

5.1

General problem Any changes of the SIPN, e.g. adding places and transitions modify its behavior. Therefore it has to be ensured anew that the modified SIPN is still formally correct and that it fulfills the new set of requirements. Normally, this results in cycles of SIPN changes with a new verification and validation steps until the results all become true.

5.2

Extended specification To discuss the changeability, the specification given so far is changed by adding hardware and a new requirement. A Stop button (i5) is implemented and the informal specification is extended as follows: After pressing the stop button, the chemical process has to be stopped. To start again, the start button has to be pressed. The tank is then emptied before a new cycle can begin.

SIPN Redesign with V&V SIPN Version 2

To take this new requirement into account, the original SIPN of section 2.4 is modified, see Figure 5. A place has been inserted in which the filling, the heating and the emptying can be stopped. Thus the chemical process is supposed to be stopped.

Before the functional requirements are checked, the SIPN must be declared as formally correct. Like the former designed SIPN, this one has to fulfill the standard expectations formulated in section 4.1. Performing verification on this SIPN does not reveal any errors. After extending the expectations, new properties have been added. That means that the redesigned control algorithm has to fulfill the properties given in section 4.3 as well as the following one: Property 3: When the stop button is pressed then the process is stopped. That means that in all the stable markings reached after pressing the stop button, the actuators must be set to 0. In TL it can expressed as: Performing validation with the newly defined algorithm tells us that the old properties are fulfilled but that the new one is not. Table 3 shows a sequence leading to a state where the property does not hold.

AG (i5 & eoc -> AX (!o1 & !o2 & !o3 & !o4) P1 -Stand by (0, 0, 0, 0) P2 Stirring (-, -, 1, -) P3 -Filling (1, 0, -, 0) P4 -Heating (0, 0, -, 1) P5 -Emptying (0, 1, -, 0) P6 -Stop (0, 0, -, 0) T1 -Start i4 & !i1 & !i2 T2 Temp. OK i2 & i3 & !i5 T3 -Temp. low i2 & !i3 & !i5 T5 -Tankis empty !i1 & !i2 & !i4 & ~i5 T6 -Stop i5 T4 -Temp. OK i2 & i3 & !i5 T7 -Stop i5 T8 -Stop i5 T9 -Start i4 & !i5
In state 4, i5 and eoc hold but in the next stable state (state 5), o3 still has value 1. When stop is pressed while place P3 is active, the filling is stopped but the stirring still remains. Indeed there is no stop transition leading from P2 to a place where o3 is reset. In this interpretation the chemical process is supposed to be stopped when filling, heating and emptying are stopped. During the formalization of the corresponding TL formula, The process has to be stopped has been interpreted differently, "all actions are stopped".

SIPN Version 3

After redefining the requirement more precisely, the second way (all actions stopped) is chosen. Hence the SIPN has to be modified again. In Figure 6, a transition T10 leading from P2 to P6 has been added.

Before looking at functional properties the formal ones have to be checked again. As a result of verification, SMV shows a conflict between transitions T6 and T10 as illustrated in the counter-example given in Table 4. When P2 and P3 are marked and the stop button is pressed, we can not decide whether T6 or T10 fires. The designed algorithm is not deterministic. This clearly is a design error.

0 P2 0 0 1 1 1 P3 0 0 1 1 0 P4 0 0 0 0 0 P5 0 0 0 0 0 P6 0 0 0 0 1 o1 0 0 1 0 0 o2 0 0 0 0 0 o3 0 0 1 1 1 o4 0 0 0 0 0 i1 0 0 0 0 0 i2 0 0 0 0 0 i3 0 0 0 0 0 i4 0 1 1 1 0 i5 0 1 1 1 0 T1 0 1 0 0 0 T2 0 0 0 0 0 T3 0 0 0 0 0 T4 0 0 0 0 0 T5 0 0 0 0 0 T6 0 0 1 0 0 T7 0 0 0 0 0 T8 0 0 0 0 0 T9 0 0 0 0 0 eoc 0 0 0 1 1 P1 ・Stand by (0, 0, 0, 0) P2 Stirring (-, -, 1, -) P3 ・Filling (1, 0, -, 0) P4 ・Heating (0, 0, -, 1) P5 ・Emptying (0, 1, -, 0) P6 ・Stop (0, 0, 0, 0) T1 ・Start i4 & !i1 & !i2 T2 Temp. OK i2 & i3 & !i5 T3 -Temp. low i2 & !i3 & !i5 T5 -Tank is empty !i1 & !i2 & !i4 & ~i5 T6 -Stop i5 T4 -Temp. OK i2 & i3 & !i5 T7 -Stop i5 T8 -Stop i5 T10 -Stop i5 T9 -Start i4 & !i5
2 3 P1 1 1 0 P2 0 0 1 P3 0 0 1 P4 0 0 0 P5 0 0 0 P6 0 0 0 i1 0 0 0 i2 0 0 0 i3 0 0 0 i4 0 1 1 i5 0 1 1 T1 0 1 0 T2 0 0 0 T3 0 0 0 T4 0 0 0 T5 0 0 0 T6 0 0 1 T7 0 0 0 T8 0 0 0 T9 0 0 0 T10 0 0 1 eoc 1 0 0

SIPN Version 4

As a solution, a new place P7 where the stirring motor is set to 0 is added, see Figure 7. Again this SIPN has to be verified before we can perform validation. Now, SMV tells us that the SIPN has a deadlock.

P1 ・Stand by (0, 0, 0, 0) Examining the counter-example in Table 5, we see that after stop button has been pressed and the cycle started again, place P5 is marked and the tank is emptied. After P5 has been reached (state 6), only one transition (T8) is enabled.

P2 Stirring (-, -, 1, -) P3 ・Filling (1, 0, -, 0) P4 ・Heating (0, 0, -, 1) P5 ・Emptying (0, 1, -, 0) P6 ・Stop (0, 0, -, 0) P7 ・Stop (-, -, 0, -) T1 ・Start i4 & !i1 & !i2 T2 Temp. OK i2 & i3 & !i5 T3 -Temp. low i2 & !i3 & !i5 T5 -Tank is empty !i1 & !i2 & !i4 & ~i5 T6 -Stop i5 T4 -Temp. OK i2 & i3 & !i5 T7 -Stop i5 T8 -Stop i5 T10 -Stop i5 T9 -Start i4 & !i5
When this transition has fired, only P6 is marked. Since P7 is no more marked, transition T10 is not enabled and the algorithm gets stuck.

SIPN Version 5

Analyzing the SIPN, a second way to quit P5 would be firing T5. Unfortunately T5 can not be enabled if place P2 is not marked. Thus starting the cycle again should produce a token in P2. This is done by an arc from T9 to P2 in the new algorithm, see Figure 8. Performing V&V on Version 5 does show no more errors. Thus this SIPN will be implemented on the PLC.

P1 ・Stand by (0, 0, 0, 0) P2 Stirring (-, -, 1, -) P3 ・Filling (1, 0, -, 0) P4 ・Heating (0, 0, -, 1) P5 ・Emptying (0, 1, -, 0) P6 ・Stop (0, 0, -, 0) P7 ・Stop (-, -, 0, -) T1 ・Start i4 & !i1 & !i2 T2 Temp. OK i2 & i3 & !i5 T3 -Temp. low i2 & !i3 & !i5

CONCLUSION

In this paper the heating tank example is used to show the advantages of formal verification and validation for a control algorithm after changing the informal specification.

Starting from a verified and validated SIPN, the initial specification is extended by some hardware and the corresponding behavioral specification. Often, these changes seem to be quite easy. Nevertheless, before the modified algorithm is implemented on a PLC, several cycles of algorithm redesign with verification and validation are necessary.

The chosen example emphasizes the fact that each modification of a formerly correct SIPN may involve errors. An error may cause either formal and functional requirements or one of them not to be fulfilled. Before the functional properties of an algorithm are checked, it should be made sure that it is formally correct, i.e. it behaves in a deterministic way. Verification and validation of the modified SIPN are pursued until the model checker proves all the properties to be true. An important aspect of the formal method described here is related to the redundancy in the two formal specifications of SIPN and Temporal Logic. This redundancy can reveal different kinds of errors, e.g. those due to different interpretations of the requirements or due to a contradictory or incomplete informal specification. As a conclusion, there are no "small" changes in the redesign of an algorithm.

  Nets (SIPN) are an extension of Condition/Event Petri nets and allow the handling of binary I/O-signals in a well-defined way. They are well suited to design control algorithms for discrete event systems resulting in languages standardized in IEC 61131-3. SIPNs are defined as a 9-tupel SIPN=(P,T,F,M 0 ,I,O,C,A,Ω)

Figure 1 .

 1 Figure 1. Evolution algorithm of an SIPN.

Figure 3 .

 3 Figure 3. Control algorithm of the heating tank (Version 1)

Figure 4 .

 4 Figure 4. Model-checking process.

Figure 5 .

 5 Figure 5. SIPN with extended specification (Version 2)

Figure 6 .

 6 Figure 6. Modified SIPN (Version 3)

Figure 7 .

 7 Figure 7. Modified SIPN (Version 4)

T5Figure 8 .

 8 Figure 8. New design of the SIPN (Version 5)

Table

Valve 1 Valve 2 Valve 3 US 1

  1 and Table 2.

		UV	US 1
		1.1
			M
	Product In		US 1
			LIS+
			02
	US 1	UV 1.3
	Vapor Heating		01 TIS+	US 1
			LIS+ 01	US 1
			UV 1.2	US 1
			Product Out
	Figure 2. Description of the heating tank

Table 1 .

 1 Table of input signals

	Name	Description
	i1	Lower level sensor
	i2	Upper level sensor
	i3	Temperature sensor
	i4	Start button
	Table 2. Table of output signals
	Name	Description
	o1	Valve 1 (filling)
	o2	Valve 2 (emptying)
	o3	Stirring motor
	o4	Valve 3 (Heating)

Table 3 .

 3 Counter-example for property 3

	State	1	2	3	4	5
	P1	1	1	0	0

Table 4 .

 4 Counter-example for the conflict between T6 and T10

	State	1


Claire François

Jean-Charles Lamirel
email: lamirel@loria.fr

Shadi Al Shehabi
email: alshahab@loria.fr

Shadi Al

Claire Francois
email: claire.francois@inist.fr

A L Shadi

Shehabi

Combining Advanced Visualization and Automatized Reasoning for Webometrics : A Test Study

Keywords: multiple viewpoint data analysis, clustering, mapping, webometrics

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The use of links between academic websites to create an informal mode of scholarly communication is a promising new field of investigation. Hence, thanks to qualitative analyses of links [START_REF] Wilkinson | Motivations for academic website interlinking: evidence for the Web as a novel source of information on informal scholarly communication[END_REF], the metrics based upon link counts can be seen to be measuring an agglomeration of connections related to scholarly activities in a wide variety of ways. However, thanks to others analyses [START_REF] Chu | Taxonomy of inlinked Web entities: What does it imply for webometrics resaech ?[END_REF], the evaluative link studies should not only consider link counts but also reasons for linking to ensure the validity of such research. Moreover, the linking behaviour has been highlighted as dependant of the studied domain. As an example, [START_REF] Wilkinson | Motivations for academic website interlinking: evidence for the Web as a novel source of information on informal scholarly communication[END_REF] found that the mathematics and computer sciences domains are more interlinked than other scientific domains. Several recent works have gone one step further, by demonstrating that a precise analysis of linking behaviour depends on the capability of taking into account several complementary factors, like discipline and geographic factors (Thelwall 2002). Nevertheless, performing such a kind of analysis at a large scale prohibits the use of a manual mode, as it has been proposed up to now.

Graph theoretic methods [START_REF] Bjöneborn | Toward a basic Framework for Webometrics[END_REF], Thelwall et al. 2005) or standard neural methods (Decker 2001) have been commonly used for automatically investigating link structures on the Web. Their main defect is that they do not represent a reliable support for performing an accurate analysis based on multiple factors.

The paradigm of multiple viewpoint data analysis (MVDA) [START_REF] Lamirel | Application d'une approche symbolico-connexionniste pour la conception d'un système documentaire hautement interactif[END_REF]) represents a promising basis to solve the problem of automatic analysis of linking behaviour. Hence, it can be fruitfully exploited to highlight relationships between data coming from different types of source. It can also be used to perform cross-analysis between data belonging to the same dataset, using different description criteria. In the domain of Webometrics, MVDA has been already successfully used to establish the research policy and the industrial relationships of a well-known institution by automatically crossing content and outlinks analyses performed on the same reference set of webpages extracted from the institution website [START_REF] Lamirel | New classification quality estimators for analysis of documentary information: application to patent analysis and web mapping[END_REF]). The role of the present study is to go one step further. It represents a first attempt of identification of the linking behaviour in a scientific domain through the analysis of the communication of the related academic institutions on the web using a MVDA approach based on clustering and mapping method. The domain that has been chosen for this study is the domain of Computer Science in Germany.

Section 2 of the paper proposes an overall presentation of the approach. Section 3 describes the preparation of the dataset merging data about European universities and research institutes websites collected in the framework of the IST-EISCTES project. Section 4 presents the results of link behaviour analyses performed on the test dataset by the use of the MultiSOM approach: both global and local linking behaviour analyses are considered. Section 5. Conclusions are finally presented.

The MultiSOM model

The basic principle of the self-organizing maps (SOM) is that our knowledge organization at higher levels is created during learning by algorithms that promote self-organization in a spatial order [START_REF] Hinton | Connectionist Learning Procedures[END_REF][START_REF] Kaski | WEBSOM-self organizing maps of document collections[END_REF][START_REF] Kohonen | The Self-Organizing Map[END_REF]). Thus, the architecture form of the SOM network is based on the understanding that the representation of data features might assume the form of a self-organizing feature map that is geometrically organized as a grid or lattice. The SOM algorithm takes thus a set of N-dimensional data as input and maps them onto nodes of a two-dimensional grid, resulting in an orderly feature map [START_REF] Kohonen | The Self-Organizing Map[END_REF]). The communication between self-organizing maps has been firstly introduced in the context information retrieval for analyzing the relevance user's queries regarding the documentary database contents [START_REF] Lamirel | Application d'une approche symbolico-connexionniste pour la conception d'un système documentaire hautement interactif[END_REF]). The resulting model, so called MultiSOM, represents both a major amelioration of the basic Kohonen SOM model and the first operational implementation of the multiple viewpoint data analysis (MVDA) paradigm. The viewpoint building principle consists in separating the description space of the data into different subspaces corresponding to different criteria of analysis. The set of V all possible viewpoints issued from the description space D of a dataset can be defined as:

V = {v 1 , v 2 , …, v n }, v i  P(D)
where each v i represents a viewpoint and P(D) represents the set of the parts of the description space of the data D.

Three main remarks follow the above definition: (1) the viewpoint subsets issued from V may overlap one to another; (2) the union of the different viewpoints can be viewed as the overall description space of the data; (3) the most suitable basis an for homogeneous management of the viewpoints is a vectorial description space. As an example, an image can be simultaneously described using 3 different viewpoints represented by: (1) a key-term vector; (2) color histogram vector; (3) a feature vector.

The principle of the MultiSOM model is to be constituted by several SOM maps that have been generated from the same data. Each map is itself issued from a specific viewpoint. The relation between maps is established through the use of one main communication mechanism. The inter-map communication mechanism enables to highlight semantic relationships between different topics (i.e. clusters) belonging to different viewpoints related to the same data. In MultiSOM, this communication is based on the use of the data that have been projected onto each map as intermediary nodes or activity transmitters between maps (see Figure 1). Source signal: direct user activation or query matching activation

[1] [2] [3] Source Map Target Map
The inter-map communication is established by standard Bayesian inference network propagation algorithm which is used to compute the posterior probabilities of target map's node T k which inherited of the activity (evidence Q) transmitted by its associated data nodes. This computation can be carried out efficiently because of the specific Bayesian inference network topology that can be associated to the MultiSOM model. Hence, it is possible to compute the probability P(act m |T k ,Q) for an activity of modality act m on a target map node T k which is inherited from activities generated on the source map. This computation is achieved as follows (Al Shehabi & Lamirel. 2004):

     k k m T d d T act d d k m S d Sim S d Sim Q T act P ) , ( ) , ( ) , (
, such that S d is the source node to which the data d has been associated, Sim(d, S d ) is the cosine correlation measure between the description vector of the data d and the one of its source node S d and dact m ,T k if it has been activated with the modality act m from the source map.

After each map building, the main characteristics of the nodes, that represent the clusters resulting from the topographical clustering process, have to be highlighted to the analyst in order to provide him an overview (i.e. a global summary) of the analysis results. This task is difficult because the description vectors of the obtained clusters consist in complex weighted combination of indexes extracted from the data. A first set of methods for solving this problem is presented in [START_REF] Lamirel | Adaptative browsing for information discovery in an iconographic context[END_REF] and [START_REF] Polanco | Using Artificial Neural Networks for Mapping of Science and technology: A Multi self-organizing maps Approach[END_REF]. It consists of cluster labelling and map zoning methods, dividing a map into homogeneous information areas. Figures 3 and4 of section 4 illustrate the overall results of these methods.

Data preparation

The data used in our experiment are information about laboratory websites of the European Universities have been collected in the EICSTES project (http://www.eicstes.org/). These data are more extensively described by [START_REF] Arroyo | Description of Web data in D3.1[END_REF]. They have originally the form of multiple tables issued from a preliminary basic structural analysis of the websites. Thus, a first phase of our data preparation consists in obtaining an overall description of each website by merging all the individual description tables into a global description table. After this first merging, the global description of a website includes theURL, the name of the organization and department, the number of pages, the number of outgoing links, the number of repeated outgoing links, the Geographic situation : country and town code, country and town name, the Domain: code, label and related domain codes, the Inlinks: list of incoming links with their URLs and the number of links coming from these URLs, the Outlinks: list of outgoing links with their URLs and the number of links going to these URLs. The investigated data set covers the websites of the research laboratories in the 15 countries of the European Union before March 2004. The domain categorization of the websites is based on the UNESCO classification. The UNESCO code is a classification that is used to allocate a scientific domain to a website starting from its content. As the original data is too general, we have firstly decided to focus our study on a specific thematic domain. The 1203 UNESCO code that deals in a global way with computer science is used for websites selection. In a second step, we have chosen to focus on German research laboratories' websites as reference websites for our study. The kernel set of 438 websites is selected in this way. Hence, the study will more precisely focus on the relationships existing between German universities relatively to a European context. The Outlinks initially represented the overall set of links emitted by the websites of the kernel set. For the purpose of our study, we have restricted this set to the subset of links emitted in the direction of a website belonging to the investigated data set, that is, the websites of the research institutes in the 15 countries of the European Union. In a complementary way, the Inlinks are calculated starting from the set of websites of the research institutes in the 15 countries of the European Union.

Viewpoints definition

Starting from the websites characteristics, viewpoints are defined that describe their distribution in various thematic sub-domains (1), their geographical repartition (2), and their network of Outlinks (3) and Inlinks [START_REF] Bjöneborn | Toward a basic Framework for Webometrics[END_REF].

Each viewpoint is represented in the form of a matrix including websites codes in its rows and the description criteria associated to the viewpoint in its columns. Thus, the table 1

Data analysis 4.1. Clustering and mapping using SOM

A map is computed for each viewpoint. In order to define the optimum size of that map, different square maps starting from 9 nodes (3*3) to 400 nodes (20*20) are calculated using the SOM basic clustering application "SOM_PACK" (SOM papers). The choice of the best map is based on an optimisation algorithm using specific quality criteria (recall, precision and F-measure) derived both from information retrieval and symbolic learning. This approach is more extensively described in Lamirel et al. (2004b). Hence, in the case of the Towns and Sub-domains viewpoints, clusters are quite homogeneous and distinct one to another. This distribution is carried out easily insofar as each website is indexed by a low number of weakly overlapping properties. As soon as each website presents a relatively significant number of incoming and outgoing links, overlaps are thus potentially much more significant, this implies relatively moderate quality values for the Outlinks and Inlinks viewpoints, even after the optimisation process. These preliminary results will be taken into account in the remaining part of our study.

Description of the maps

For the viewpoint (1), the map clusters gather websites sharing their geographic location. For the viewpoint (2), the map clusters gather websites sharing their overall research profile (i.e. combination of Unesco codes). For the viewpoint (3), the map clusters gather websites sharing their Outlinks: they are described by the targets of the links. The viewpoint (4) is the equivalent of (3) using the Inlinks: the maps clusters are described by the targets of the links.

The easiness of interpretation of a map not only depends on the map quality (see section 4.1) but also on complementary factors, like the granularity of description. Two typical cases of maps are described hereafter. The Sub-domains map (figure 2): it is a relatively small map (81 clusters) with relatively large information areas. The map clusters have generic headings and some of them contain a large number of websites. For example, five clusters (among a total of 81) gather 227 websites (among a total of 438). A more accurate indexation would have allowed a better distribution of the websites in clusters of more homogeneous size, and consequently, a more precise map content interpretation. Case 2: The Outlinks map (figure 3): each website has many Outlinks leading to high granularity of websites Outlinks descriptions, and thus, to potentially more interesting map configuration. Thus, the Outlinks map has information areas of relatively homogeneous and small size. Such a map configuration highlights a homogeneous website outlinking behaviourConsistency measure between the different viewpoints

Consistency measure between the different viewpoints

The propagation consistency measure is presented in Al [START_REF] Shehabi | Multi-Topographic Neural Network Communication and Generalization for Multi-Viewpoint Analysis[END_REF]. It evaluates the activity focalization generated by a source map S on a target map T. It is a non necessary symmetrical measure. The propagation coherency (PC) is given by:

      k k S k k i i D T act P S PC ; 1 ) ( 1 where ) 1 ( . 2 1       k k i i j j i k T T T T D k k
and S represents the peculiar set of nodes extracted from the source map of S, which verifies:

  act S S S S S k k k     ,



T k is the set of the activated nodes in the target map through the activation of the source node S k  

) ( k i i k S PRG T T T T k k   
Each node in the SOM grid is represented its coordinate position ) , (

k k k i i i b a T 
In a practical way, the propagation consistency takes into account the focalization of the activity generated by the clusters of the source map on a target map (figure 4). A strong focalization of all the clusters of a source map on a target map will lead to a high consistency.

Figure 4: Focalization of the activity propagation

A high consistency measured from a source map to a target map means that the clusters of the target map can be well explained by the clusters of the source map. Please remember that consistency is a non symmetrical measure. Thus, if the reverse consistency, measured from the target map to the source map, is also high, this can lead to consider that the two maps are similar. On the contrary, if the reverse consistency is low, there is no evidence concerning any converse explanation provided by the target map on the source map.

Table 3 presents the consistencies values existing between the various viewpoints. The results being asymmetrical, the table must be read lines towards column as shown by the arrow. The values lie between 0 and 1 out of the diagonal, while the unity value can be observed in the diagonal, a map being perfectly self-consistent.

Behaviour of linking according to the research sub-domains

The highest value of consistency is Sub-domains towards Outlinks (0.554). This can be interpreted as an indicator of coherence of outlinking behaviour of the laboratories belonging to common research sub-domains. The consistency value of Sub-domains towards Inlinks is significantly high (0.416), while weaker than the former value. This indicates a good identification of the research sub-domains of the laboratories, although they don't have the control of the links they receive.

In a reverse way, the consistency value of Outlinks towards Sub-domains is particularly low (0.095), as well as the consistency value of Inlinks towards Sub-domains (0.055). These values indicate that the global linking behaviour of the research laboratories largely overcome their research sub-domains.

Geographical distribution of research sub-domains

The value of consistency of Sub-domains towards Towns (0.216) is moderately high, indicating certain coherence in geographical distribution of the research sub-domains: research sub-domains tend to gather in specific cities. Conversely, the value of consistency of Towns towards Sub-domains is low (0.096), indicating that various research sub-domains coexist in the German cities.

Overall comparison of inlinking and outlinking behaviours

Table 3 shows that the values of consistency of Outlinks towards all viewpoints are higher than those of Inlinks. This indicates that the clusters of the Outlinks map are more coherent than those of the Inlinks map. We can generalize this observation by proposing the assumption that the outlinking behaviour of a research laboratory is more coherent than its received referencing. Nevertheless, this observation should be taken with care, as soon as Inlinks and Outlinks maps quality are moderate.

The former discussion highlights that the analysis of the consistency in multi-viewpoints context of the MultiSOM approach represent a sound basis to get an overall view of the linking behaviour in a large scale context. More focused strategies based on the same approach are presented hereafter. As it will be shown, they can be used for illustrating local phenomenon related to linking behaviour.

Local analysis using the inter-map communication mechanism

The MultiSOM inter-map communication mechanism can be used in an interactive mode to highlight specific relationships between clusters of different maps. For this purpose, an activity is assigned to a cluster, or to an information area, of a source map. Then, the mechanism of propagation of the activity to all the other maps (target maps) is applied (figure 1). Finally, the focalization profile of the target maps is analyzed (figure 4). Said profile indicates a more or less great coherence between activated cluster, or area, of the source map and the activated clusters of the target maps. We present hereafter two examples of application of such a mechanism for performing local analysis of link behaviour. The first example is an analysis of the link behaviour of the research laboratories localised in a town. For that analysis, we have chosen the biggest town cluster considering the number of associated websites, i.e. the Munich town cluster. The second example is a study of the link behaviour of the laboratories sharing the same research sub-domain. In order to observe a potential focalization, we have chosen a sub-domain which is not too general, like Computer Sciences or Computer Technology. Thus, we have focused the study on the Mathematics sub-domain.

Example of Munich

The figure 5 illustrates the overall strategy that has been used for realizing the Munich study. In a first step, a source activity is set on the Munich information area of the Town map and the resulting activation spreading on the Outlinks map is analysed. In a second step, the overall zone of the Outlinks map on which the activity has focalized at the first step is reused as an activity source, and the backward activity spreading on the Town map is analyzed.

Towns map

Outlinks map Towns map

Step 1

Step 2

Towns map

Outlinks map

Towns map

Step 1

Step 2

Step 1: the propagation of the activity starting from the Munich information area and going towards the Outlink map concentrates around an information area, which gathers 3 clusters whose profile is dominated by the URL http://www.tu-muenchen.de/ (figure 5). The activated clusters located around this information area have the following dominant URLs in their profile: http://www.uni-passau.de/ http://www.informatik.uni-ulm.de/ http://www.fh-offenburg.de/ http://ls10-www.cs.uni-dortmund.de/ The above mentioned URLs correspond to main websites cited by the websites of Munich laboratories. They thus summarize the outlinking behaviour of these latter laboratories. This led us to conclude to a relatively local outlinking behaviour of the Munich laboratories, i.e. referecing towns mostly located in the South of Germany (Passau, Ulm, Offenburg).

Step 2: the "http://www.tu-muenchen.de/" information area of the Outlinks map gathers websites having this URL as the dominant URL in their profile. An activity propagation starting from this information area is launched towards the Towns map. Its role is to highlight the geographical spreading of the laboratories sharing their outlinking profile with the dominant outlinking profile of the Munich laboratories. This activity propagation results in activated clusters all over the Towns map (Munich, Bonn, Tuebigen, Dresden, and Loebau-Zittau). This led us to conclude that: even if the linking behaviour of Munich is relatively local (see step 1), Munich's type of outlinking is not to Munich and/or to its direct surrounding. Thus, it enables us to reject the "closed world" outlinking hypothesis concerning Munich.

Example of Mathematics

The figure 6 illustrates the overall strategy that has been used for realizing the Mathematics study. This strategy is similar to the one that has been used for the Munich study. In a first step, a source activity is set on the Mathematics information area of the Sub-domains map and the resulting activation spreading on the Outlinks map is analysed. In a second step, the overall zone of the Outlinks map on which the activity has focalized at the first step is reused as an activity source, and the backward activity spreading on the Sub-domains map is analyzed. Step 2

Step 1: the propagation of the activity starting from the Mathematics information area towards the Outlink map highly focuses around an information area, which gathers 3 clusters whose profile is dominated by the URLs: http://www.uni-kassel.de/, http://www.uni-frankfurt.de/, http://www.uni-leipzig.de/. These URLs correspond to main websites cited by the websites of the Mathematics information area. They thus summarize the outlinking behaviour of these latter websites. As the activity is focalized on the target map, it also means that this outlinking behaviour is specifically coherent. This local observation is compliant with the high value of the overall consistency of Subdomains relatively to Outlinks (0,554) presented in table 3.

Step 2: an activity propagation starting from the clusters whose dominant URLs have been highlighted at step 1 (http://www.uni-kassel.de/, http://www.uni-frankfurt.de/, http://www.unileipzig.de/) is launched towards the Sub-domains map. Its role is to highlight the thematic spreading of the laboratories sharing their outlinking profile with the dominant outlinking profiles of the Mathematics domain. This activity propagation results in activated clusters all over the Sub-domains map (Mathematics, Artificial intelligence, Databases, Programmation theory, Automatic system of production, Informatics -Information processing, Information systems, design and components, Computer technology, Computer sciences). This local observation is compliant with very low value of the overall consistency of Outlinks relatively to Subdomains (0,095) presented in table 3. This led us to conclude that: even if the linking behaviour of the Mathematics is highly coherent (see step 1), Mathematics's type of outlinking is not specific to this research domain.

The former discussion highlights that the local focalization analysis can be successfully used for illustrating local phenomenon related to linking behaviour. In a complementary way, they could also be used for highlighting local phenomenon whose behaviour significantly differs from the global behaviour measured by the consistency analysis. This mechanism would then be a precious one for highlighting exceptions.

Conclusion

This paper presents a first attempt for performing a precise and automatic identification of the linking behaviour in a scientific domain through the analysis of the communication of the related academic institutions on the web. Our approach is based on the paradigm of multiple viewpoint data analysis (MVDA). This paradigm has been exploited to carry out a complete analysis of a website dataset through the use of multiple kinds of website descriptions: geographical localisation, research topics, and networks of links between websites. Our dataset covers 438 websites of German Computer Science research laboratories. Both local and global link behaviour analyses have been carried out using the MultiSOM approach. MultiSOM is a clustering and mapping approach aiming at gathering data into homogeneous subsets projected on two dimensional maps. It is associated with an original mechanism of communication between maps associated to different viewpoints. This mechanism has been used in an automatic mode in order to highlight general information related to the link behaviour. A local link behaviour analysis has been achieved by focusing on data subsets associated map clusters and by using the interactive form of that mechanism.

Several preliminary results concerning the linking behaviour of the German research laboratories have been obtained. One first result is the thematic consistence of both the outlinking and the inlinking behaviour. A similar phenomenon has been observed to a less extent concerning geographic consistence of the research sub-domains. A general assumption has also been made by the observation of maps consistency. It is related to the fact that the outlinking behaviour of a research laboratory is more coherent than its received referencing. We must note that other experiments related to datasets issued from different countries must be done to validate these results.

Moreover, a regional outlinking policy has been highlighted focusing the analysis on a specific German city although this experiment must be completed to generalize this observation to all the cities of the dataset.

A local analysis of websites subsets associated either to a city or to a sub-domain provides the analyst with a clear overview on neighbourhood of the elements of a sub-network.

The main strength of our approach is to dynamically combine multiple kinds of data descriptions for performing automatized link analyses. Nevertheless, some potential correspondences regarding the behaviour of this approach must be more in deeply investigated: as an example, the relation between the consistencies values between the map and the local analysis using these different maps. This knowledge will certainly help us to validate important hypotheses. For that purpose, we plan to achieve methodological experiments on different dataset in the near future.

Figure 1 :

 1 Figure 1: Inter-map communication principle

Figure 2 :

 2 Figure 2: The Sub-domains map Figure 3: The Outlinks map

Figure 5 :

 5 Figure 5: Inter-map communication mechanism starting from the Munich cluster Step 1: communication from Towns map towards Outlinks map, Step 2: communication from Outlinks map towards Towns map.

Figure 6 :

 6 Figure 6: Inter-map communication mechanism starting from the Mathematicsinformation area

Table 1 :

 1 highlights that the kernel set is indexed by 96 towns (German cities), 93 thematic sub-domains (Unesco codes), 2079 Outlinks and 2839 Inlinks, respectively. Looking to these values, a first general remark can be made: German research laboratories are significantly more cited (2839 Inlinks) than they cite (2079 Outlinks). The matrices listed in table 1 represent the direct entry data of the clustering MultiSOM application. Matrix size for each viewpoint

	Viewpoints	Matrix size
	Towns (1)	438 * 96
	Thematic sub-domains (2)	438 * 93
	Outlinks (3)	386 * 2079
	Inlinks (4)	388* 2839

Table 2

 2 As defined in[START_REF] Lamirel | New classification quality estimators for analysis of documentary information: application to patent analysis and web mapping[END_REF], the quality values range between 0 and 1, 1 representing the best possible value in all cases.

presents the final results of the whole map construction process, the optimum number of clusters and the quality values (recall, precision and F-measure) for each viewpoint.

Table 2 :

 2 Optimum number of clusters for each viewpoint

	Viewpoints	Number of clusters Recall Precision F_measure
	Towns (1)	256	1,00	0,90	0,95
	Thematic sub-domains (2)	81	0,74	0,72	0,73
	Outlinks (3)	144	0,49	0,49	0,49
	Inlinks (4)	289	0,58	0,51	0,54

Table 2

 2 highlights very high quality values for Towns and Sub-domains viewpoints, and conversely, quite low quality values for the Outlinks and Inlinks viewpoints.

Table 3 :

 3 Consistency values between the maps of the different viewpoints

		Towns	Sub-domains	Outlinks	Inlinks
	Towns	1	0.096	0.250	0.270
	Sub-domains	0.216	1	0.554	0.416
	Outlinks	0.117	0.095	1	0.270
	Inlinks	0.080	0.055	0.130	1