Jason J Jung
email: j2jung@intelligent.pe.kr

Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Towards semantic social networks

HAL is

using the knowledge structure used by individuals in order to infer some of their social relationships, and taking advantage of this inferred social structure in order to help people sharing their knowledge.

For that purpose, we introduce a structure made of three superposed networks that are assumed to be strongly linked:

Social network relating people on the basis of common interest; Ontology network relating ontologies on the basis of explicit import relationships or implicit similarity; Concept network relating concepts on the basis of explicit ontological relationships or implicit similarity.

We call this stack of interlinked networks a semantic social network.

The top-down links between these networks are obvious: people use ontologies that defines or refer to concepts. The less obvious aspect that is illustrated here is bottomup inference of relationships from one network to another. These relationships can be inferred by analyzing the structure of knowledge.

Once the structure of knowledge allows to infer "intellectual" relationships between people, it is possible to use it for helping people managing their knowledge. For instance, finding that similar people use similar ontologies or the same ontology makes them candidates to be standardized. In addition, when starting some collaboration between partners in order to merge their knowledge or to define one common ontology, it is better to start from the ontology used by considering social features such as centrality and authority.

The remainder of the paper is organized as follows. Sect. 2 provides a description of a target application which uses network analysis in order to help people sharing ontology annotated resources. Sect. 3 provides the basic knowledge in social network analysis. As the main contribution, Sect. 4 and 5 explain the three-layered semantic social network structure. Sect. 4 considers each layer, the kind of relationships it expresses and the tools that can be used for manipulating these networks. Sect. 5 investigates the relationships between these layers and the opportunity this provides to lift network structure from one layer to another. Sect. 6 presents an experiment we have conducted. Finally, in Section 7, this work is compared with previous studies related to social networks on semantic web.

Emerging collaboration in peer to peer networks

We apply semantic social networks in the context of peer-to-peer (P2P) sharing of annotations in which individuals can use ontologies for annotating resources (in our case, photographs). Because, these individuals can have different needs and different standpoints, they are not constrained to use the same ontology (contrary to BibSter [START_REF] Broekstra | Bibster -a semantics-based bibliographic peer-to-peer system[END_REF], for instance). They can take advantage of standard ontologies on the web (like FOAF or EXIF), but they can extend these ontologies to their needs.

However, when people want to query other peers, for benefiting from better annotation or from other pictures, the network of heterogeneous ontologies must be dealt with. This ontology mismatch is solved by offering an alignment infrastructure to the peers that allows them to find some alignments between their ontologies and to process queries through mediators [START_REF] Euzenat | Alignment infrastructure for ontology mediation and other applications[END_REF].

Current work on ontology matching consists of either automatically matching two ontologies without regard to its context or environment, or of interactively helping some knowledge engineer to match two ontologies. Our goal is to take into account the social networking context in order to improve the alignment results and, in turn, the social networking expertise.

In this context, semantic social network analysis has two purposes:

helping people to find other peers with similar interests, and helping peers to find the best company for starting designing consensus ontologies.

For the first purpose, there are two options. On the one hand, the peers can use social network analysis (SNA) to find in their explicit personal network of peers with some the same interests. Such people would certainly use ontologies that are not totally remote and trying to match these ontologies promise to be easier and more rewarding. On the other hand, if one peer has no relation with known peers sharing the same interest, but is looking for some pictures, it will be more convenient that he looks for peers having similar ontologies. The peers can use metrics on the ontology network in order to find ontologies which are close to theirs. The underlying assumption is that these peers will have similar interest to theirs even if they are not explicitly recorded as connected. Moreover, if the metric is compatible with some matching algorithm, the matching will be easier to perform. So, in this situation, the social network is used for satisfying the need of some user (finding interesting annotated resources) and this action will contribute strengthening the social network by exhibiting new links between peers. As a simple example, Fig. 1 illustrates the potential connection between unknown users by ontology alignment in a semantic social network.

Another contribution of SNA to this application is to identify the central (authoritative) ontologies at the ontology level such that aligning with these ontologies allows to be connected with the maximum number of peers (and thus retrieve the maximum number of answers).

Matching algorithms can take advantage of SNA in order to help find the closest ontologies with regards to the connectivity of users and to identify which users are more prone to the use of a pivotal ontology.

Beside matching ontologies in an ad-hoc manner, there is time when peers can imagine benefiting from putting their experience together and building some consensus ontologies. To that extent, they can also use SNA in order to identify the community (cohesive subgroups on the social level), the best peer for proposing consensus (centrality on the social network), or the ontologies which could be the seed for this collaboration process (centrality on the ontology layer). Of course, when both coincide (i.e., when the central individuals use a central ontology), the chances of success are higher.

Network analysis

Network analysis is based on the analysis of the relationships within a population. We here consider networks with several different relations between individuals. So, a network is characterized as a set of objects (or nodes) and a set of relations.

Definition 1 (Network). A network N, E 1 , . . . E n is made of a set N of nodes and n sets of object pairs E i ⊆ N × N the set of relations between these nodes.

We will below freely use the relations as functions

(E i (n) = {n ′ ∈ N | n, n ′ ∈ E i }).
As usual, a path p between node e and e ′ in the graph of E i is a sequence of edges e 0 , e 1 , e 1 , e 2 , . . . , e k-1 , e k from E i in which e 0 = e and e k = e ′ . The length of a path is its number of edges (here k), sp i (e, e ′ ) is the set of shortest paths between e and e ′ and the shortest path distance spd i (e, e ′ ) between two nodes e and e ′ is the length of the shortest paths between them, when it exists. By convention, spd(e, e) = 0. Thus, spd(Arun, Sebastien) in Fig. 1 is three via Jason and JeromeE.

Social network analysis [START_REF] Wasserman | Social network analysis: methods and applications[END_REF] has considered various measures on the networks between people (note that these measures apply only if the network is connected)3 :

Closeness The inverse of average length of the shortest path between a node e and any other node in the network:

Closeness i (e) = |N -1| e ′ ∈N spd i (e, e ′ ) (1)
Betweenness [START_REF] Freeman | Centrality in social networks: Conceptual clarification[END_REF] The proportion of shortest paths between two nodes which contains a particular node (this measures the power of this node):

Betweenness i (e) = e ′ ,e ′′ ∈N |{p ∈ sp i (e ′ , e), p ′ ∈ sp i (e, e ′′ )|p • p ′ ∈ sp i (e ′ , e ′′ )}| |sp i (e ′ , e ′′ )|
(2) Hub and authority There are different but interrelated patterns of power: Authorities that are referred to by many and hubs that refers to many. The highest authorities are those which are referred to by the highest hubs and the highest hubs that those which refers to the highest authorities. Kleinberg [START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF] proposes an iterative algorithm to measure authority and hub degree of each node in interlinked environment. Given initial authority and hub degrees of 1, the degrees are iteratively computed by

Hub i t+1 (e) = e ′ : e,e ′ ∈E i Auth i t (e ′ ) and Auth i t+1 (e) = e ′ : e ′ ,e ∈E i Hub i t (e ′ ) (3)
Similarly to betweenness, the hub weight indicates the structural position of the corresponding user. It is a measure of the influence that people have over the spread of information through the network.

Our purpose being the identification of individual that are prone to collaborate with each others, we would like to find these clusters of individuals in the network. There are no standard method for extracting so-called cohesive subgroups in social network analysis. Many different methods are proposed based on graph-theoretic terms (e.g., cliques [START_REF] Wasserman | Social network analysis: methods and applications[END_REF]) or clustering methods (e.g., [START_REF] Fortunato | Method to find community structures based on information centrality[END_REF]).

Definition 2 (Distance network)

. A distance network N , E 1 , . . . , E n is made of a set N of nodes and n sets of distance functions E i : N × N -→ [0 1

] defining the distance between nodes (so satisfying symmetry, positiveness, minimality, and triangular inequality).

Distance values can also be seen a weights or costs. It is clear that any network is a distance network which attributes either 0 or 1 as a distance. The definitions of SNA mentioned above can be adapted to distance networks if each time the cardinality of a set of edges if used, it is replaced by the sum of its distances. The distance of a path is obtained by summing the distances of its edges. One extension that must be made is to use the distance between nodes to reduce their influence to others in the computation of authority and hub degrees:

Hub i t+1 (e) = e ′ ∈N Auth i t (e ′ ) E i (e, e ′ )
and

Auth i t+1 (e) = e ′ ∈N Hub i t (e ′ ) E i (e ′ , e) (4)
4 Three-layered architecture for semantic social networks

In order to uncover the links between people from those that can be found from their knowledge, we propose the three-layered architecture for constructing the semantic social network. As shown in Figure 1, it consists of i) a social network (S), ii) an ontology network (O), and iii) a concept network (C). The characteristics of each layer and the relationships between layers are described below.

Social layer

In the social layer (S), nodes are representing people, and relations are the connections between peoples. A social network S is a directed graph N S , E knows S , where N S is a set of person and E knows S ⊆ N S × N S the set of relations between these persons. In most current applications, the relation used by SNA is the knows relation that can be found in FOAF. From the social network in Fig. 1, the authoritative and hub weights of three users are shown in Table 1. Obviously, the highest hub weight is assigned to Jason because he is an important and unavoidable role of bridging between the rest of users.

Ontology layer

The ontology network O is a network

N O , E i O , in which N O is a set of ontologies and E i O ⊆ N O × N O
the relationships between these ontologies. There can be two main kinds of relations at this stage: import when some ontology explicitly import another ontology; refer when some ontology uses some concept defined in another ontology.

The objective relationship from the S to the O is through the explicit usage of an ontology by a user which can be expressed by a relation:

U se ⊆ N S × N O .
We can easily interpret the hubs as being the ontologies that combine a large number of other ontologies. These would be an interesting starting point for any newcomer willing to annotate a similar set of objects as his friend. Likewise, authorities will be ontologies that are extended and imported by many different actors (i.e., de facto standard ontologies).

There is a difference between ontology networks and social networks though: while in social networks it is normal to be connected to several authorities, an ontology will only import one ontology on some topic. It would thus be useful to recognize those hubs that connects authorities on the same topics, these "ontologies" are likely to be the expression of an alignment between the two authorities.

Concept layer

In the concept layer (C), nodes are concepts, and links are the numerous kinds of links that can be found in ontologies. The concept network C is a network N C , E i C , in which N C is a set of entity of an ontology (classes, properties, individuals) and E i C ⊆ N C × N C the relationships between these entities. These relationships are far more numerous than in the other layers and depends on the kind of entity considered. If we restrict our attention to classes, the : subClass linking a class to its subclasses; superClass (=subClass -1 ) linking a class to its super classes; sibbling linking a class to its siblings; disjoint linking a class to the classes it is explicitly disjoint with; property (=domain -1 ) linking a class to its properties;

-1 linking a class to the properties that refer to it.

The objective relationship from the O to the C is through the definition of concept in an ontology which can be expressed by a relation: Def ines ⊆ N O × N C . However, this notion of definition is not easy to catch: it could be based on either the assertion of a constraint on some ontology entity or the namespace in which entity belongs. We will consider the namespace in the following.

We are here further away from social networking. As noted in [START_REF] Alani | Ontology ranking based on the analysis of concept structures[END_REF], the notions of hub and authority cannot be understood in the same way for all the relations expressed in C.

Inferring relationships

This three-level semantic social network does not bring in itself new improvement for our P2P sharing application. In order to provide new insight in the possible collaborations it is necessary to analyze these networks and to propagate information from one layer to another. We explain how, starting from the lower concept layer, it is possible to enrich the upper ontology and social layers with new relations from which SNA helps finding relevant peers.

Similarity on the concept layer

Beside the numerous relationships that can be found by construction of the concept layer, new relationships can be inferred between the entities. One particular relationship that will be interesting here is similarity. In order, to find relationship between concepts from different ontologies, identifying the entities denoting the same concept is a very important feature. As a matter of fact, most of the matching algorithms use some similarity measure or distance in order to match entities.

Similarity on the concept layer can be obtained by various means [START_REF] Shvaiko | A survey of schema-based matching approaches[END_REF]. Some distances can be established from the local features of entities. For instance, the name of entities can be the basis for matching them. Many techniques have been developed for comparing strings, based on their structures (like edit distance), their morphology (through lemmatization), their entry in lexicons (using WordNet). Another kind of similarity can be established based on set of shared instances like in [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF].

Some other distances, more in the spirit of network analysis, can be defined from the structure of the network. For instance, [START_REF] Euzenat | Similarity-based ontology alignment in OWL-Lite[END_REF], defines possible similarities (e.g., Sim C , Sim R , Sim A ) between classes, relationships, attributes, and instances. Given a pair of classes from two different ontologies, the similarity measure Sim C is assigned in [0, 1]. The similarity (Sim C ) between c and c ′ is defined as

Sim C (c, c ′ ) = E∈N (C) π C E M Sim Y (E(c), E(c ′ )) (5)
where N (C) ⊆ {E 1 . . . E n } is the set of all relationships in which classes participate (for instance, subclass, instances, or attributes). The weights π C E are normalized (i.e., E∈N (C) π C E = 1). If we consider class labels (L) and three relationships in N (C), which are superclass (E sup ), subclass (E sub ) and sibling class (E sib ), Equ. 5 is rewritten as:

Sim C (c, c ′ ) = π C L sim L (L(A i ), LF (B j )) + π C sup M Sim C (E sup (c), E sup (c ′ )) + π C sub M Sim C (E sub (c), E sub (c ′ )) + π C sib M Sim C (E sib (c), E sib (c ′ )) (6)
where the set function M Sim C computes the similarity of two entity collections. As a matter of fact, a distance between two set of classes can be established by finding a maximal matching maximizing the summed similarity between the classes:

M Sim C (S, S ′ ) = max c,c ′ ∈P airing(S,S ′ ) Sim C (c, c ′ ) max (|S|, |S ′ |) (7)
in which P airing provides a matching of the two set of classes. The OLA algorithm is an iterative algorithm that compute this similarity [START_REF] Euzenat | Similarity-based ontology alignment in OWL-Lite[END_REF]. This measure is normalized because, if Sim C is normalized, the divisor is always greater or equal to the dividend. A normalized similarity measure can be turned into a distance measure by taking its complement to 1 (

E dist C (x, y) = 1 -Sim C (x, y)). Such a distance introduces a new relation E dist C
in the concept network C. This relation indeed defines a distance network as introduced above.

From concept similarity to ontology similarity

Once such a distance has been introduced at the concept level, it can be used for computing a new distance at the ontology level. Again, a distance between two ontologies can be established by finding a maximal matching maximizing similarity between the elements of this ontology and computing a global measure which can be further normalized: Definition 3 (Ontology distance). Given a set of ontologies N O , a set of entities N C provided with a distance function

E dist C : N C × N C -→ [0 1] and a relation Def ines : N O × N C , the distance function E dist O : N O × N O -→ [0 1] is defined as: E dist O (o, o ′ ) = max( c,c ′ ∈P airing(Def ines(o),Def ines(o ′ )) E dist C (c, c ′ )) max(|Def ines(o)|, |Def ines(o ′ )|)
Of course, even with these heavy computations, ∀o ∈ N O , E dist O (o, o) = 0. This is the measure that is used in the OLA algorithm for deciding which alignment is available between two ontologies [START_REF] Euzenat | Similarity-based ontology alignment in OWL-Lite[END_REF]. However, other distances can be used such as the well known single, average and multiple linkage distances.

This ontology distance introduces a new relation on the ontology layer. This measure provides a good idea of the distances between ontologies. These distances, in turn, provide hints of the difficulty to find an alignment between ontologies. It can be used for choosing to match the closest ontologies with regard to this distance. This can help a newcomer in a community to choose the best contact point: the one with who ease of understanding will be maximized. This will be further developed in Section 5.4.

From concept similarity to alignment

It can however happen that people have similar but different ontologies. In order for them to exchange their annotations, they use alignments existing within the ontology network. Alignments, in turn, are the results of applying matching algorithms based on the correspondence between ontologies.

As a result, from concept similarity these algorithms will define a new relation E align at the ontology level.

o, o ′ ∈ E align iff M atch(o, o ′ ) = ∅
If one has a measure of the difficulty to use an alignment or of its quality, this network can also be turned into a distance network on which all these measures can be performed.

new relation in the ontology layer allows the agents to choose the ontology that they will align with first. Indeed, the ontologies with maximal hub centrality and closeness are those for which the benefit to align to will be the highest because they are aligned with more ontologies at the ontology level. In the P2P sharing application, choosing such an ontology will bring the maximum answers to queries. For example, in the concept layer of Fig. 1, two alignments between i) po Arun and po Jason and ii) po Sebastien and po Jason enable Arun and Sebastien to share information, even though they are not explicitly linked with each other. This is the occasion to note the difference between the relations in the same network: in the ontology network, the hub ontologies for the import relation are rather complete ontologies that cover many aspects of the domains, while hub ontologies for the E align relation are those which will offer access to more answers.

Of course, when an alignment exists between all the ontologies used by two peers, there is at least some chance that they can talk to each others. This can be further used in the social network.

From ontology similarity to people affinity

Once these measure on ontologies are obtained, this distance can be further used on the social layer. As we proposed it is possible to think that people using the same ontologies should be close to each other. We can consider measuring the affinity between people from the similarity between the ontology they use.

Definition 5 (Affinity). Given a set of people N S , a set of ontologies

N O provided with a distance E dist O : N O × N O -→ [0 1
] and a relation U ses : N S × N O , the affinity is the similarity measure defined as

E af f (p, p ′ ) = max o,o ′ ∈P airing(U se(p),U se(p ′ )) 1 -E dist O (o, o ′ ) max(|U se(p)|, |U se(p ′ )|) (8)
Since this measure is normalized, it can be again converted to a distance measure through complementation to 1.

Introducing the distance corresponding to affinity in the social network allows to compute the affinity relationships between people with regard to their knowledge structure. Bottom-up inference from C allows to find out the semantic relationships between users based on this space.

For completing the P2P application, the last step consists of identifying the subgroups of users, according to the various social characteristics, as follows:

1. The subgroup whose members are assigned very high semantic authoritative weight (or semantic hub weight) can be identified by comparing the weights computed with Equ. 4. These peers have the social power to control and select semantic information to distribute. 2. The subgroups of people with very similar personal ontologies can be obtained by computing the cohesive subgroup of the S network using affinity (E af f ). 3. The subgroup of people which are interested in the same topics extends the previous subgroups, depending on a particular topic. Their members can efficiently share information about that topic.

Experimental results

As a first evaluation of our framework, we want to differentiate social affinity E af f (p, p ′ ) from the previous measures for social features. Our experimentation scenario follows these steps (i) building personal ontologies during photo annotation, (ii) aligning these personal ontologies for measuring social affinity between people, and (iii) discovering the most powerful person for semantic interoperability.

For collecting data, we invited seven members of our team to select a set of photographs and annotate them by using a specific annotation tool (Picster4 ). Table 2 shows the specification of personal ontologies. From co-occurrence patterns between the annotated photos, Mika's social centrality C M [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF] can be formulated by

C M (U i ) = ∩ |U | k=1,k =i (R U k ,R U i ) R U i |U | -1 (9)
where |U | is the total number of people in the social network. The results are shown in Table 3. We found out that the number of annotated resources are barely related to the We computed this for all pairs of people on the social network, as shown in Table 3. The matrix for social affinity is symmetric. We found out that the number of ontologies are playing an important role in social affinity. JE has shown the highest centrality in the given social network, while JP annotated the most common resource with other people. This means that collaborations can be effectively be provided with JE. Meanwhile, E af f (JJ, JP) was relatively high (0.72). We found that they were using the same large ontology (i.e., SUMO). So the number of found correspondences where very high. To deal with this problem, we have to consider preprocessing personal ontologies. Another issue is the discovery of potential collaborators (or like-minded people) by comparing the social distances in Table 1. While the social distance between AS and SL is 3 on the social layer of Figure 1 (i.e., 1. once normalized), their social affinity is measured as 0.62 which is relatively high (the corresponding distance would be .38). We can expect that they can share common interests.

Related work

Many semantic systems on distributed environments like P2P networks have been introduced to efficiently share information and knowledge between heterogeneous sources. Some have studied the relevance of peers (or users) by analyzing topology and interactions like message passing. In [START_REF] Haase | Peer selection in peer-to-peer networks with semantic topologies[END_REF], for selecting the expert peers, semantic topology analysis is exploited. But they make assumptions that every peers have to use the same ontology for calculating semantic similarity. Practically, [START_REF] Valencia | Building semantic channels between heterogeneous agents with topological tools[END_REF] applies the similar idea to multi-agent architecture, and as an example of application, Jung has introduced a social communication framework for collaborative web browsing [START_REF] Jung | Collaborative web browsing based on semantic extraction of user interests with bookmarks[END_REF]. Meanwhile, Alani and colleagues introduced a system, called Ontocopi, for ontology-based network analysis (ONA) [START_REF] Alani | Identifying communities of practice through ontology network analysis[END_REF]. This system can identify the communities by using informal data.

More closely related to this work, Mika proposes a three-layered space which is composed of a social network and a knowledge network relying on concepts and instances [START_REF] Staab | Social networks applied[END_REF]. However, the knowledge network is simply based on sets for co-occurrence analysis, and in this networks, the super/sub-relationships are retrieved based on statistical overlapping. This approach does not deeply consider semantic relationships between concepts and ontologies, so it is hard to use the structure of knowledge for structuring the social network.

For measuring the relevance of ontologies, in [START_REF] Alani | Ontology ranking based on the analysis of concept structures[END_REF], the AKTiveRank system ranks the ontologies applying a number of classical metrics such as class match, centrality, density, and semantic similarity. In [START_REF] Hoser | Semantic network analysis of ontologies[END_REF], network analysis methods (in particular, Hermitian matrices-based eigensystem analysis) are used for analyzing ontologies as concept graphs in the same way social network are analyzed. This is used for contrasting the "style" of ontologies but not for social networking, though this last application could be investigated.

Concluding remarks and future work

We have focused on using the structure of knowledge used by people in order to extract meaningful relations at the social level. Moreover, the extraction of these new relations is used to further improve the collaborative sharing and exploitation of this knowledge.

We propose a three-layered architecture for constructing semantic social network, which is composed of a social layer, an ontology layer, and a concept layer. This space not only supports the relations within a layer, but also the propagation of relations between layers. We have provided the principles for extracting similarity between concepts and propagating this similarity to a distance and an alignment relation between ontologies. This distance relation can be used for discovering affinity in the social network. In return, users can take advantage of these newly established relations to find people closer to them on the basis of the structure of their knowledge. For that purpose, we have only used classical SNA measures (that we extended to distance networks).

The basic assumption of this work is that these newly discovered relations between people will facilitate mutual understanding as well as ontology matching and resource sharing. This remains to be demonstrated experimentally. To that extent we are developing and experimenting the presented P2P sharing system. We will make measure and generate alignment and ask users to rate and correct the provided alignments.

There remains important issues to be investigated: all these networks are not equal and their exploitation with classical SNA tools can be meaningless (in the same sense that considering the "loves" and "hates" relations as the same would lead to problems). It is thus important to characterize the various relations that were provided with regard to the measures that can be used on them. We also plan to extend this work by defining and extracting meaningful (and useful) clusters among people. We expect to apply this information to build social and semantic grid environment [START_REF] Jung | BlogGrid: Towards and efficient information pushing service on blogspace[END_REF]. Moreover, the cost of computing these networks can become important. We have not considered this issue here because most of the given measures are examples, but this can become an important factor if the networks and measures have to be computed on-line.

Fig. 1 .

 1 Fig. 1. A three-layered social semantic network

Definition 4 (

 4 Alignment relation). Given a set of ontologies N O , a set of entities N C provided with a relation E dist C : N C × N C , a matching algorithm M atch based on E dist C and a relation Def ines : N O × N C , the alignment relation E align is defined as:

Social Layer Concept Layer Ontology Layer

					Sebastien
			JeromeE
					know s
		kn ow s	k n o w s	Jason	Arun
	Antoine	knows			knows
		university
	travel.owl	foaf.rdf im p o rt		exif.rdf
	foaf:person	academia Sports e s im po rt sports.owl im p o rt company d e fi n e s d e f in es fin de Ski practise Companies
					Cricket
	e n g a g e Agency	Institutes	Alphine
	businessman
	researcher

Table 1 .

 1 Closeness, authoritative and hub weights in Fig.1

	Closeness	0.5	0.67	0.5	0.6	0.67	0.46	0.4
	Authoritative	0.21	0.45	0.37	0.69	0.243	0.236	0.13
	Hub	0.01	0.52	0.27	0.32	0.54	0.42	0.275

Weights Arun(AS) Antoine(AZ) F aisal(FAK) JeromeE(JE) Jason(JJ) JeromeP (JP) Sebastien(SL)

Table 2 .

 2 Specification of personal ontologies as test bed

		AS AZ FAK JE	JJ	JP SL
	Number of annotated photographs (R U ser )	47	47	37	49 47 30	25
	Number of used ontologies (O U ser )	3	5	2	6	1	1	2

Table 3 .

 3 Experimental results of a) closeness and centrality by co-occurrence patterns b) people affinity E af f and centrality in the semantic social network

	(a/b) AS	AZ	FAK	JE	JJ	JP	SL	C M C af f
	AS	-	0.98/0.65 0.62/0.33 0.94/0.73 1.00/0.26 0.60/0.32 0.23/0.62 0.73 0.49
	AZ 0.98	-	0.62/0.49 0.94/0.825 0.98/0.31 0.62/0.3 0.26/0.52 0.73 0.52
	FAK 0.78	0.78	-	0.70/0.57 0.78/0.28 0.54/0.22 0.30/0.32 0.65 0.37
	JE	0.90	0.90	0.53	-	0.90/0.46 0.57/0.49 0.16/0.75 0.66 0.64
	JJ	1.00	0.98	0.62	0.94	-	0.60/0.72 0.23/0.39 0.73 0.40
	JP	0.93	0.97	0.67	0.93	0.93	-	0.13/0.51 0.76 0.43
	SL 0.44	0.48	0.44	0.32	0.44	0.16	-	0.38 0.52
	social centrality. SL annotated the least number of resources, so that his centrality also
	lowest among people. But, even though JE's annotations were the largest one, JP has
	shown the most powerful centrality.
	We measured semantic affinity on the semantic social network (Eq. 8). For doing so,
	the ontology distances E dist O edit distance between class labels. For instance, E dist between personal ontologies are measured. We used string O between JE and AZ is shown in

Table 4 .

 4 Then, we can measure E af f (AZ, JE) =

	max( P	o,o ′ 1-E dist O max(5,6)	(o,o ′ ))	= 4.95 6 =

Table 4 .

 4 Ontology distance E dist

		O	between JE and AZ; Mark '-' means no alignments between
	two ontologies.
		JE foaf.owl JE Meteo.owl JE Picster.owl JE space.owl JE UrbanLand.owl JE World.owl
	az support-ontology.owl	0.03	-	-	0.17	-	-
	az hasSupplyLineOnt.owl	0.46	-	0.09	0.05	0.04	0.49
	az office.owl	0.47	-	0.04	0.05	0.06	0.04
	az people+petsB.owl	0.06	-	-	0.16	-	-
	az space-basic.owl	0.18	-	-	0.5	-	0.01
	0.82 where ontology distance between non aligned ontologies ('-') are regarded as 1.

These measures are often normalized (between 0 and 1) but we present their simplest form.

http://gforge.inria.fr/projects/elster


Loredana Laera

Ian Blacoe
email: blacoe@csc.liv.ac.uk

Valentina Tamma

Terry Payne

J « Erôme Euzenat
email: jerome.euzenat@inrialpes.fr

Trevor Bench-Capon

Argumentation over Ontology Correspondences in MAS

In order to support semantic interoperation in open environments, where agents can dynamically join or leave and no prior assumption can be made on the ontologies to align, the different agents involved need to agree on the semantics of the terms used during the interoperation. Reaching this agreement can only come through some sort of negotiation process. Indeed, agents will differ in the domain ontologies they commit to; and their perception of the world, and hence the choice of vocabulary used to represent concepts. We propose an approach for supporting the creation and exchange of different arguments, that support or reject possible correspondences. Each agent can decide, according to its preferences, whether to accept or refuse a candidate correspondence. The proposed framework considers arguments and propositions that are specific to the matching task and are based on the ontology semantics. This argumentation framework relies on a formal argument manipulation schema and on an encoding of the agents' preferences between particular kinds of arguments.

INTRODUCTION

Multi-Agent Systems have proved very valuable for solving problems spanning more than one organisation, and in domains where many factors may be dynamic, and thus cannot be readily considered and anticipated at design-time. Open and dynamic environments, such as the Web and its proposed extension, the Semantic Web [START_REF] Berners-Lee | The Semantic Web[END_REF], are by nature distributed and heterogeneous. In these environments ontologies [START_REF] Studer | Knowledge engineering, principles and methods[END_REF] are expected to complement agreed communication protocols in order to facilitate mutual understanding and interactive behaviour between such agents. Thus, agents may differ in the domain ontologies they commit to [START_REF] Gruber | A Translation Approach to Portable Ontology Specifications[END_REF]; and in theirperceptionoftheworld(andhencethechoiceofvocabulary used to represent concepts). Imposing a single, universally shared ontology on agents is not only impractical because it would result in assuming a standard communication vocabulary (and thus violate the dynamics of open environments); but it also does not take into account the conceptual requirements of agents that could appear in future. Therefore, if their ontologies are different, these need to be reconciled in order to support interaction. The reconciliation of heterogeneous ontologies in open environments, where no prior assumption can be made on the ontologies used, depends on the different agents' ability to find an agreement on the semantics of the terms used during the interoperation. The agreement usually takes the form of an alignment between the ontologies, that is a set of correspondences (or mappings) between the concepts, properties, and relationships in the agent ontologies; and on their use to interpret or translate messages exchanged. Reaching this agreement can only come through some sort of negotiation process [START_REF] Aberer | Emergent semantics principles and issues[END_REF]. The motivation for our work lies in open environments, where one agent wishes to communicate with another in order to request a service. The agents are aware of each other's existence, but have no knowledge about the services that the other may offer. This situation arises when the agents are able to utilise a registry service, such as the FIPA Directory Facilitator, but are not able to understand the services offered due to the fact that they utilise different ontologies. Therefore, the agents need to agree on an ontology alignment to determine whether the services offered match the requested ones. In order to generate a suitable alignment the agents are able to access a mapping repository, OMR, that stores possible mappings between ontology components. These mappings originate from independent mapping engines that employ differing algorithms to calculate potential correspondences between different ontologies. In this paper we present an approach that makes use of argumentation theory in order to dynamically reach an agreement over heterogeneous ontologies. The set of potential arguments are clearly identified and grounded on the underlying ontology language, and the types of correspondences supported by any such argument are clearly specified. We base our approach on [START_REF] Laera | Reaching agreements over ontology alignments[END_REF] and we tailor it to the specific needs of agent communication, and we evaluate our framework against existing tools for ontology mapping. The novel contribution of the approach presented here lies in the preferences that agents can express on the types of correspondences to use when aligning the ontologies. The argumentation framework allows the agents to reach an agreement on those correspondences that are mutually acceptable,b ecause they are determined by those mappings that cannot be refuted by other agents. This approach better reflects the characteristics of autonomy and rationality that are typical of agents [START_REF] Wooldridge | Intelligent agents: Theory and practice[END_REF]. A value-based argumentation framework [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] is used to express agents' preferences between the categories of arguments that are built on the types of correspondences.

MEANING-BASED ARGUMENTATION

Meaning-based Argumentation is a process that dynamically and automatically enables agents, with different terminologies and interests, to reach consensus on the terminology they use to interact -by arguing.T h i sg i v e st h e m the ability to understand each other enough to carry out their objectives, and in our specific context to request a service. The terminology of each agent is represented according to its own conceptualisation, which we assume is explicitly specified according to its own ontology. An ontology O can be defined as a tuple C, ≤C ,R,≤R,I , where C and R are two disjoint sets and their elements are called, respectively, concepts and properties. ≤C and ≤R are partial orders on C and R respectively and are called concept hierarchy and relation hierarchy. The elements of I may be instances of concepts in C and may be interconnected with other elements in I by a relation in R. Such elements are known as individuals. We assume that all agents' ontologes are encoded in the same language, the web standard, OWL 1 . In order to make ontologies interoperable, so that the terms in different ontologies are brought into correspondence, we need to provide mappings. These mappings can be provided by a variety of different matching algorithms, such as the ones participating to the Ontology Alignment Evaluation Initiative (OAEI) 2 . An alignment consists of a set of correspondences between the two ontologies. A correspondence (or a mapping) is described as a tuple: m = e, e ′ ,n,R , where e and e ′ are the entities (concepts, relations or individuals) between which a relation is asserted by the correspondence; n is a degree of confidence in that correspondence; and R is the relation (e.g., equivalence, more general, etc.) holding between e and e ′ asserted by the correspondence [START_REF] Shvaiko | A survey of schema-based matching approaches[END_REF]. A correspondence over which no agreement has yet been reached by the agents is called a candidate mapping. Moreover, we assume that for each correspondence m, the repository is able to provide a set of justifications G, that explain why it has generated the candidate mapping. Such information forms the basis which an agent can dynamically generate arguments and supply the reasons for their mapping choices. In addition, each agent has a (partial or total) pre-ordering of preferences over different types of ontology mismatches (Pref ), and a private threshold value ε which is compared to the degree of confidence associated with each mapping. These preferences are based on the motivations of the agent, and determine whether a mapping is accepted or rejected. Currently, only a few approaches for ontology alignment provide such justifications [START_REF] Shvaiko | Web explanations for semantic heterogeneity discovery[END_REF]. However, tools such as [START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF] combine different similarity metrics, and these measures can be used to build the required justifications. Moreover, for obvious efficiency reasons, the argumentation approach is applied only over the ontological terms the agents need to understand each other, rather than on the whole ontology.

THE ARGUMENTATION APPROACH

The argumentation framework for autonomous agents proposed in this section is based on Value-based Argument Frameworks (VAFs) [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF]. We start with the presentation of Dung's work [START_REF] Dung | On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-person Games[END_REF], upon which the VAFs rely.

Definition An Argumentation Framework (AF ) is a pair AF = AR, A , where AR is a set of arguments and A ⊂ AR×AR is the attack relationship for AF , and is comprised of ordered pairs of distinct arguments in AR.Ap a i r x, y is referred to as 'x attacks y', while a set of arguments S is said to attack an argument y if y is attacked by an argument in S.

An argumentation framework can be simply represented as a directed graph whose vertices are the arguments and whose edges correspond to the elements of A. In Dung's framework, attacks always succeed. This is reasonable when dealing with deductive arguments, but in many domains, including the one under consideration, arguments lack this coercive force: they provide reasons which may be more or less persuasive, and their persuasiveness may vary according to their audience. Therefore, we distinguish attacks from successful attacks, i.e., those which defeat the attacked argument. We use a Value-based Argumentation Framework, which prescribes different strengths to arguments on the basis of the values they promote and the ranking given to these values by the audience for the argument. This allows us to systematically relate strengths of arguments to their motivations, and to accommodate different audiences with different interests and preferences.

Definition A Value-Based Argumentation Framework (VAF)isdefinedas AR, A, V,η , where (AR, A)isanargumentation framework, V is a set of k values which represent the types of arguments and η : AR →V is a mapping that associates a value η(x) ∈V with each argument x ∈ AR.

In section 3.1, the set of values V is defined as the different types of ontology mismatch, which we use to define the categories of arguments and to assign to each argument one category.

Definition An audience for a VAF is a binary relation R⊆V×Vwhose (irreflexive) transitive closure, R * ,i s asymmetric, i.e. at most one of (v, v ′ ), (v ′ ,v)a r em e mbers of R * for any distinct v, v ′ ∈V .W e s a y t h a t vi is preferred to vj in the audience R, denoted vi ≻R vj,i f (vi,vj) ∈R * .L e t R be an audience, α is a specific audience (compatible with R)i fα is a total ordering of V and

∀ v, v ′ ∈V , (v, v ′ ) ∈ α ⇒ (v ′ ,v) ∈R * .
In this way, we take into account that different agents (represented by different audiences) can have different perspectives on the same candidate mapping. Given a set of arguments and counter arguments, it is necessary for the agents to consider which of them they should accept. Acceptability of an argument is defined in the following way: 3 Definition Let AR, A, V,η be a VAF and R an audience. For arguments x, y in AR, x is a successful attack on y with respect to the audience R if: (x, y) ∈Aand it is not the case that η(y) ≻R η(x). An argument x is acceptable to the subset S with respect to an audience R if: for every y ∈ AR that successfully attacks x with respect to R,t h e r ei ss o m e z ∈ S that successfully attacks y with respect to R. A subset S of AR is conflict-free with respect to the audience R if: for each (x, y) ∈ S × S,e i t h e r( x, y) ∈Aor η(y) ≻R η(x). A subset S of AR is admissible with respect to the audience R if: S is conflict free with respect to R and every x ∈ S is acceptable to S with respect to R.As u b s e tS is a preferred extension for the audience R if it is a maximal admissible set with respect to R.

The key notion here is the preferred extension which represents a consistent position within AF , which is defensible against all attacks and which cannot be further extended without becoming inconsistent or open to attack. In order to determine whether the dispute is resolvable, and if it is, to determine the preferred extension with respect to value orderings promoted by distinct audiences, [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] introduces the notion of objective and subjective acceptance as follows:

Definition Given a VAF, AR, A, V,η , an argument x ∈ AR is subjectively acceptable if and only if, x appears in the preferred extension for some specific audiences but not all. An argument x ∈ AR is objectively acceptable if and only if, x appears in the preferred extension for every specific audience. An argument which is neither objectively nor subjectively acceptable is said to be indefensible.

Arguments about mappings

In this paper we focus on arguments about mappings. We define these arguments as follows:

Definition An argument x ∈ AF is a triple x = G, m, σ
where m is a correspondence e, e ′ ,n,R ; G is the grounds justifying a prima facie belief that the correspondence does, or does not hold; and σ is one of {+, -} depending on whether the argument is that m does or does not hold.

A key issue is that the interaction between arguments is based on a notion of attack; an argument x is attacked by the assertion of its negation ¬x,n a m e l yt h ecounter-argument, defined as follows:

Definition An argument y ∈ AF rebuts an argument x ∈ AF if x and y are arguments for the same mapping but with different signs, e.g. if x and y are in the form x = G1,m,+ and y = G2,m,-, x counter-argues y and vice-versa.

Moreover, if an argument x supports an argument y, they form the argument (x → y) that attacks an argument ¬y and is attacked by argument ¬x. These arguments are clearly identified and grounded on the underlying ontology language OWL. Therefore, the grounds justifying correspondences can be extracted from the knowledge in ontologies. This knowledge includes both the extensional and intensional OWL ontology definitions. Our classification of the grounds justifying correspondences is the following: semantic (M ): the sets of models of two entities do or do not compare; internal structural (IS): two entities share more or less internal structure (e.g., the value range or cardinality of their attributes); external structural (ES): the set of relations, each of two entities have, with other entities do or do not compare; terminological (T ): the names of two entities share more or less lexical features;

extensional (E): the known extensions of two entities do or do not compare. These categories correspond to the type of categorizations underlying ontology matching algorithms [START_REF] Visser | Assessing Heterogeneity by Classifying Ontology Mismatches[END_REF]. In our framework, we use the types of arguments described above as types for the VAF;h e n c eV = {M, IS, ES, T, E}. Therefore, for example, an audience may specify that terminological arguments are preferred to semantic arguments, or vice versa. Note that this may vary according to the nature of the ontologies being aligned. Semantic arguments are given more weight in a fully axiomatised ontology, compared to that in a lightweight ontology where there is very little reliable semantic information on which to base such arguments. Table 1 presents a sample of reasons for the justification of candidate OWL ontology alignments. The table represents an (extensible) set of argument schemes, the instantiations of which include AR. Attacks between these arguments arise when we have arguments for the same mapping but with conflicting values of σ, thus yielding attacks that can be considered symmetric. Moreover, the relations in the mappings can also give rise to attacks: if relations are not deemed exclusive, an argument against inclusion is a fortiori an argument against equivalence (which is more general). For example, given a candidate mapping m = c, c ′ , , ≡ between two OWL ontologies O1 and O2, with concepts c and c ′ respectively, an argument for accepting the mapping m m a yb et h a tt h el a b e l so fc and c ′ are synonymous. An argument against may be that no mapping is defined for some of their sub-concepts.

Argument generation process

In this section we examine the way arguments are generated and the main characteristics of agent architecture used in order to exchange arguments on correspondences. Each agent Agi has access to its individual ontology: Definition An agent Agi is characterised by a 4-tuple Oi, VAFi,Pr e f i ,ε i where Oi is the OWL ontology; VAFi = ARi,Ai, V,ηi is the Valued-based Argumentation Framework of the agent Agi; Prefi is the private pre-ordering of preferences over V and εi is the private threshold value.

As e to fa g e n t sA = {Ag1,...,Agn} forms a multi-agent system (MAS ). The set of arguments shared by all agents are not necessarily disjoint, while the values V are common a n ds h a r e db ya l la g e n t s . As mentioned, the preferences and threshold selected by an agent depend on its context and situation. A major feature of this context is the agent's ontology, and its structural features, such as the depth of the subclass hierarchy and branching factor, ratio of properties to concepts, etc. The analysis of the structural components of the ontology is inline with the approach to ontology evaluation, demonstrated in [START_REF] Dellschaft | On how to perform a gold standard based evaluation of ontology learning[END_REF], and can be formalized in terms of feature metrics. An agent can then determine its preferences and threshold based on the characteristics of its ontology. For example, selecting a preference for terminological mapping if the ontology is lacking in structure, or preferring extensional mapping if its ontology is rich in instances. In our framework, the arguments and counter-arguments are generated by an agent using these preferences and thresholds. Specifically, we assume n agents, committing to different ontologies, and a mapping repository, OMR, storing the several sets of correspondences between the agent ontologies, generated by a variety of different mapping services. Different sets of correspondences can be generated by mapping services depending on the methods used and their configurations 4 . In order to enable the agents to come to agreement on a suitable alignment for the service requested, without requiring a complete alignment between the ontologies, the requesting agent specifies which of the components from its own ontology are involved in the service request, and only seeks to generate an alignment with the ontology of the other agent with regard to these entities.

Given an agent Agi = Oi,VAFi,Pref i ,εi , and a candidate mapping m ∈ OMR with a set of justifications G,t h e agent Agi first evaluates the acceptability of m. A mapping m is accepted by an agent Agi if there exist justifications G for m that correspond to the highest preference Pref i (with respect to the pre-ordering), assuming n is greater than its private threshold εi. Consequently, the agent generates a set of arguments x = G, m, + ,b yi n s t a n t i a t i n g the argumentation schema. In the other case, the agent Agi rejects the mapping m and it generates arguments against:

x = G, m, -(see algorithm 1 ). Figure 1 end for 9: end for tecture of our approach for achieving dynamic negotiation of ontology alignments between agents requesting and providing services. The pattern of communication between the requesting agent, providing agent and the mapping reposit o r yi ss h o w ni nt a b l e2 .

AGREED & AGREEABLE ALIGNMENTS

Although in VAFs there is always a unique non-empty preferred extension with respect to a specific audience, provided the AF does not contain any cycles in a single argument type [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF], an agent may have multiple preferred ex- 4 Note that the mapping repository does not store every possible mapping between entities, but applies a threshold to the submitted mappings in order to store only those plausibly supported by the ontological knowledge. The assumption of using mapping services does not imply any loss of generality, since these services are now becoming increasingly available. See: http://oaei.ontologymatching.org/ Agent1 wants a service X and knows which components of its own ontology O1 are involved in requesting X 2

Agent1 knows Agent2 exists, but nothing else. 3

Agent1 requests Agent2's ontology O2. 4

Agent1 sends Agent2 the terms from O1 involved in X. 5

Both agents get the candidate mappings from OMR. 6

Both agents exchange their arguments sets. 7

Both agents instantiate their argumentation frameworks. 8

Both agents then calculate their preferred extensions. 9

Both agents then determine the agreed alignment, by exchanging these preferred extensions. 10

Agent1 then sends its service request X to Agent2. 11

Agent2 compares X with its service descriptions -S21,S22, etc. using the agreed alignment, and sends any matching service descriptions to Agent1. 12 Agent1 examines these service descriptions using the alignment to confirm that they match the required service X. 13

If a matching service is confirmed, Agent1 sends the service request to Agent2. tensions either because no preference between two values in a cycle has been expressed, or because a cycle in a single value exists. The first may be eliminated by committing to a specific audience, but the second cannot be eliminated in this way. In our domain, where many attacks are symmetric, two cycles are frequent and in general an audience may have multiple preferred extensions. Thus, given a set of arguments justifying mappings organised into an argumentation framework, an agent is able to determine which mappings are acceptable by computing the preferred extensions with respect to its preferences. If there are multiple preferred extensions, the agent must commit to the arguments present in all preferred extensions, but has some freedom of choice with respect to those in some but not all of them. This partitions arguments into three sets: desired arguments,p r e s e n t in all preferred extensions, optional arguments,p r e s e n ti n some but not all, and rejected arguments, present in none.

If we have two agents belonging to different audiences, these sets may differ. Doutre et al. [START_REF] Doutre | Determining Preferences through Argumentation[END_REF] describe a means by which agents may negotiate a joint preferred extension on the basis of their partitioned arguments so as to maximise the number of desired arguments included, whilst identifying which optional arguments need to be included to support them. Based on the above considerations, we thus define an agreed alignment and an agreeable alignment as follows. An agreed alignment is the set of correspondences supported5 by those arguments which are in every preferred extension of every agent. An agreeable alignment extends the agreed alignment with those correspondences supported by arguments which are in some preferred extension of every agent. Whilst the mappings included in the agreed alignments can be considered valid and consensual for all agents, the agreeable alignments have a uncertain background, due to the different alternative positions that each agent can take. However, given our context of agent communication, we seek to accept as many candidate mappings as possible. We therefore take into consideration both set of alignments -agreed and agreeable.

Instantiating argumentation frameworks

In order to reach agent consensus about ontology alignments, first we have to build the argumentation frameworks and evaluate them to find which arguments are agreed and agreeble. There are four main steps in applying our argumentation approach: Each agent individually constructs an argumentation framework for each candidate mapping, by considering the repertoire of argument schemes available to it, and instantiating these schemes with respect to its interests. Each argument either supports or rejects the conclusion that the mapping is valid. Having established the set of arguments, the agent then determines the attacks between them by considering their mappings and signs, and the other factors discussed above. This step produces several VAFs for reasoning about the candidate correspondences. Given a MAS, each agent considers its individual frameworks with all the argument sets of all the other agents and then extends the attack relations by computing the attacks between the arguments present in its framework with the other arguments. Then, for each VAF, the agents determine which arguments are undefeated by attacks from other arguments. The algorithm in [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] can be employed for computing the preferred extensions of a VAF given a value ordering. The global view is considered by taking the union of these preferred extensions for each audience. Finally, each agent considers which arguments are in every preferred extension of every audience. The mappings that have only favourable arguments are included in the agreed alignments, and the mappings that have only arguments against are rejected. For mappings whose acceptability cannot be established, agents extend the search space to consider those arguments which are in some preferred extension of every audience. The mappings supported by those arguments are part of the set of agreeable alignments. The dialogue between agents can thus consist of the exchange of arguments sets, from which agents can individually compute acceptable mappings. If necessary and desirable, these can then be reconciled into a mutually acceptable position through a process of negotiation, as suggested in [START_REF] Doutre | Determining Preferences through Argumentation[END_REF] which defines a dialogue process for evaluating the status of arguments in a VAF, and shows how this process can be used to identify mutually acceptable arguments. In constructing a position, an ordering of values best able to satisfy the joint interests of the agents concerned is determined. However, such issues are the subject of ongoing research. The above technique considers sets of mappings and complete argumentation frameworks. If instead the problem is to determine the acceptability of a single mapping it may be more efficient to proceed by means of a dialectical exchange, in which a mapping is proposed, challenged and defended.

Argumentation protocol

In this section we briefly introduce an argumentation protocol which can be used to evaluate the acceptability of a single mapping. The idea behind the protocol is to allow n agents (n ≥ 2) to argue about the acceptability of a potential mapping, arriving at a joint solution that is based on their preferences and the information they exchange during argumentation. Formally, our argumentation protocol is a tuple Mapping, Agents, Acts, Replies, Move, Dialogue, Result such that: Mapping: is a candidate mapping m ∈ OMR, subject to evaluation between the agents. Agents: is the set of agents taking part in the dialogue, Ag1,...,Agn Acts: is the set of possible argumentation speech acts: Acts = {Support, Contest, W ithdraw} Replies:Acts → Acts is a mapping that associates to each speech act its possible replies: Replies(Support) = { Support, Contest,Withdraw } ; Replies(Contest) = { Support, Contest,Withdraw } ;R e p l i e s ( W i t h d r a w )=∅. Move: is a tuple Mi = Si,Hi,Movei , where Si ∈ Agents is the agent which makes the move; Hi ⊆ Agents is the set of agents to which the move is addressed and Movei = Acti(c) is the uttered move, with Acti(c) as the speech act applied to a content c. Dialogue: is a finite non-empty sequence of moves Dialogue ={M0, ••• ,Mp } Result: M apping →{agreed, agreeable, rejected} is a mapping which returns the result of the acceptability of the mapping m. Initially, each agent Agi evaluates the acceptability of the mapping m, and then generates a set of arguments {x + 1 = G1,m,+ ,...,x + r = Gr,m,+ } or counter-arguments {x - 1 = G1,m,-,...,x - r = Gr,m,-}. Each agent Agi sends support(m, {x + 1 ,...,x + r })orcontest(m, {x - 1 ,...,x - r })tothe other agents. If the agent does not have any arguments or counter-arguments to propose, then it can withdraw by W ithdraw(m) and the dialogue terminates. Each agent Agi checks whether it agrees with the set of mappings m1,...,mk used in the arguments that are exchanged. If they have arguments or counter-arguments to present, they start a new dialogue to evaluate each mapping in m1, ,mk. The dialogue terminates when each mapping involved in the initial dialogue on m has been evaluated or when an agent withdraws 6 . When the dialogue terminates, each agent builds the argument framework, and checks the acceptability of the mapping by computing its preferred extensions.

AN ILLUSTRATIVE EXAMPLE

We illustrate the ideas presented in this paper with the a i do fas i m p l ee x a m p l e ,w h e r ea g e n tAg1 interacts with another agent Ag2 to request a service. We assume that the only terms used for such a request are Paper Author and Research Topic. The first agent, Ag1, uses the EKWA ontology7 ; whereas the second agent, Ag2 uses the OpenConf Ontology8 . For space reasons, we only consider a subset of these ontologies, shown in Figure 2, where the first and second ontologies are represented by O1 and O2 respectively. Ag2 does not know if it is able to satisfy the request until the Note that the agents also argue about the mapping m5 since it is part in the argumentation. Assume now that Ag1 selects the audience R1, which prefers terminology to external structure, (T ≻R 1 ES). Ag2 selects the audience R2,w h i c h prefers external structure to terminology (ES ≻R 2 T ). The pre-ordering of preference Pref corresponds to each agent's audience. Moreover, all the above candidate mappings have a degree of confidence n that is above the threshold of each agent, and so this does not influence their acceptability. Agent Ag1 accepts all of the correspondences, whilst Ag2 accepts only the mapping m1 and rejects the mappings m2, m3 and m4.B o t ha g e n t sa c c e p tm5. The arguments and counter-arguments generated are shown in Table 3 overleaf, that shows each argument, labeled with an identifier Id,i t s type V, the attacks A that can be made on it by opposing arguments, and the agent that proposes the argument. Based upon these arguments and the attacks, each agent can construct the argumentation framework which brings the arguments together so that they can be evaluated, shown in Figure 3. The nodes represent arguments (labelled with their Id) with the respective type value V. The arcs represent the attacks A, and the direction of the arcs represents the direction of the attack. We have two arguments supporting the correspondence m1. 4. The arguments that are accepted by both audiences are {A, C, G, F, H, I}.T h u s t h e agreed alignment is m1, m3, m4 and m5, while the mapping m2 is rejected (since B is unacceptable to R2).

EVALUATION

In order to gauge the effectiveness of the proposed approach, we have evaluated it empirically. The experiments aim to measure how the argumentation affects the accuracy of the possible alignments generated from the mappings in the OMR. For this purpose, we use the OAEI benchmark test suite. This test set consists of one reference ontology for a bibliographic domain, to be compared with other ontologies. Most of these ontologies originate from the reference ontology by making arbitrary changes. The experiments involved only two agents, Ag1 and Ag2 -w i t hAg1 having the reference ontology in each test and Ag2 having the respective test ontology. Their threshold has been set to zero, and so will not influence the process. The evaluation sets we used are the following: simple tests: The reference ontology is compared with itself, with another irrelevant ontology or the same ontology restricted to OWL-Lite. Tests 101, 102, 103, 104. systematic tests: The reference ontology is compared with modified ones. These modifications involved discarding some features, such as names, comments, hierarchy, instances, re- We used standard information retrieval metrics to assess the results of our tests: Recal l, Precision and F-measure. Precision measures the ratio between the number of correct mappings and the number of all mappings found. Recal l measures the ratio between the number of correct mappings and the total number of correct mappings that should be found. F-measure combines the measures of precision and recall as single measure. In order to evaluate how the argumentation influences the matching accuracy, we calculated the F-measure before and after the argumentation. The preferences Pref1 and Pref2, chosen on the basis of the ontological information, for Ag1 and Ag2 are presented in Table 5.

The experimental results are shown in Figure 6.a. The pre- only allows the selection of those mappings that best suit the interests of each agent, but, in most cases, improves retrieval in terms of F-measure. We have also compared our argumentation approach with a number of other ontology alignment tools representative of the state-of-the-art. These tools10 are: Foam [START_REF] Ehrig | Foam -framework for ontology alignment and mapping; results of the ontology alignment initiative[END_REF], Falcon [START_REF] Jian | Falcon-AO: Aligning Ontologies with Falcon[END_REF] and OWL-Lite Alignment (OLA) [START_REF] Euzenat | Ontology alignment with ola[END_REF]. The experiments conducted on each tool are the same as those described above, and the results of this comparison can be seen in Figure 6.b. The results demonstrate that, in the majority of the test cases, our argumentation approach produces an information recall F-measure that is in a similar range to those produced by the other approaches.

Examination of the results in the different test groups shows that for the simple tests all the approaches produce comparable results, with, for example, test 102 showing a 0 Fmeasure because this test ontology has a non-overlapping domain and so no alignment would be expected. In the systematic tests the results for argumentation are only slightly below those for the other approaches, with two main exceptions. For tests 205 and 206 the argumentation produces a 0 F-measure because the information in the two ontologies causes the agents to select directly opposing preferences, which leads to an inability to reach agreement on many of the mappings. For tests 201 and 202, argumentation performs less well than the other approaches due to a lack of candidate mappings in the repository to argue over (because in these test ontologies the concept labels have been replaced by random strings). In the complex tests our approach can be seen to perform well in comparison to the other tools (out-performing OLA and performing similarly to Foam) which is largely due to the fact that the four test ontologies involved are real, independently engineered ontologies over the same domain, that provide richer ontological information than many of the other tests.

RELATED WORK

Few approaches have addressed the use of argumentation or negotiation between agents w.r.t. ontology alignments. An ontology mapping negotiation [START_REF] Silva | An Approach to Ontology Mapping Negotiation[END_REF] has been proposed to establish a consensus between different agents using the MAFRA alignment framework. It is based on the utility and meta-utility functions used by the agents to establish if a mapping is accepted, rejected or negotiated, but is highly dependent on the MAFRA framework and cannot be flexibly applied in other environments. van Diggelen et al. [START_REF] Van Diggelen | A decentralized approach for establishing a shared communication vocabulary[END_REF] present an approach for agents to agree on a common ontology in a decentralised way. Rather than being the goal of any one agent, the ontology mapping is a common goal for every agent in the system. Beun et al. [START_REF] Beun | Ontological feedback in multiagent systems[END_REF] present a computational framework for the detection of ontological discrepancies in multiagent systems by using feedback utterances. Bailin and Truszkowski [START_REF] Bailin | Ontology Negotiation: How Agents Can Really Get to Know Each Other[END_REF] present an ontology negotiation protocol that enables agents to exchange parts of their ontology, by a process of successive interpretations, clarifications, and explanations. The end result of this process is that each agent will converge on a single, shared ontology, whereas, in our context, agents keep their own ontologies. Many ontology alignment tools have been proposed in the area of the Semantic Web. QOM [START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF], and its extension Foam [START_REF] Ehrig | Foam -framework for ontology alignment and mapping; results of the ontology alignment initiative[END_REF], are based on heuristically calculated similarity of the individual ontology entities, and is distinguished by an emphasis on the efficiency of alignment. OLA [START_REF] Euzenat | Ontology alignment with ola[END_REF] is dedicated to the alignment of OWL-Lite ontologies, and aims to use all the available information (i.e. lexical, internal and external structure, extensional, and data-types) extracted from two given ontologies. Falcon [START_REF] Jian | Falcon-AO: Aligning Ontologies with Falcon[END_REF] is an automatic tool for aligning ontologies, which employs three distinct matchers in combination: a string-similarity matcher, a Vector Space Model of domain terms, and an RDF graph matcher. None of these approaches consider the preferences of agents seeking to align ontologies, however, each of them could be as a mapping engine in our architecture.

CONCLUSIONS

In this paper we have outlined a framework that provides a novel way for agents, with different ontologies, to agree upon an ontology alignment. This is achieved using an argumentation process in which candidate correspondences are accepted or rejected, based on the ontological knowledge and the agent's preferences. This will give agents the ability to understand each other enough to carry out their objectives, for example to request a service. We believe that this approach will facilitate reaching more sound and effective mutual understanding and communication in a multi-agentsystem. Currently, the preferences are limited to a few general types of ontology mismatch. In future, we will extend the preferences to suit more ontology alignment algorithms and also consider their combination. We are intending to demonstrate the effects of varying the preferences on the quality of the alignments reached, and evaluate the framework for more than two agents. Moreover, in future work we will investigate how to argue about the entire alignment, rather than only the individual candidate mappings. These arguments could occur when a global similarity measure between the whole ontologies is applied.

Algorithm 1

 1 depicts the archi-Generation of Arguments Require: a set of agents {Ag1,...,Agn}, an ontology alignment repository OMR , a set of candidate mappings mj Ensure: a set of arguments and counter-arguments xk 1: for all agent Agi = Oi,VAFi,Pref i ,εi do 2: for all mapping mj = ej,e ′ j ,nj,Rj do 3: if n ≥ ǫ and ∃G j ∈G such that Gj = Pref then 4: Generate arguments for m : xk = Gk,m,+ 5: else 6: Generate arguments against m : xk = Gk,m,-7: end if 8:

1

 1

  Figure 1: Architecture

Figure 2 :

 2 Figure 2: O1 and O2 ontologies ontologies are aligned. Thus, the agents access the mapping repository, OMR, that stores the following set of possible correspondences, originating from different mapping engines that may employ differing algorithms: m1= O1 : Paper Author, O2 : Author, 0.45, = ; 9 m2= O1 : Paper Author, O2 : Paper,0.54, = ; m3= O1 : Research T opic, O2 : T opics, 0.44, = ; m4= O1 : Research T opic, O2 : Domain Topic,0.44, = ; m5= O1 : Person,O2 : People,0.9, = ;Note that the agents also argue about the mapping m5 since it is part in the argumentation. Assume now that Ag1 selects the audience R1, which prefers terminology to external structure, (T ≻R 1 ES). Ag2 selects the audience R2,w h i c h prefers external structure to terminology (ES ≻R 2 T ). The pre-ordering of preference Pref corresponds to each agent's audience. Moreover, all the above candidate mappings have a degree of confidence n that is above the threshold of each agent, and so this does not influence their acceptability. Agent Ag1 accepts all of the correspondences, whilst Ag2 accepts only the mapping m1 and rejects the mappings m2, m3 and m4.B o t ha g e n t sa c c e p tm5. The arguments and counter-arguments generated are shown in Table3overleaf, that shows each argument, labeled with an identifier Id,i t s type V, the attacks A that can be made on it by opposing arguments, and the agent that proposes the argument. Based upon these arguments and the attacks, each agent can construct the argumentation framework which brings the arguments together so that they can be evaluated, shown in Figure3. The nodes represent arguments (labelled with their Id) with the respective type value V. The arcs represent the attacks A, and the direction of the arcs represents the direction of the attack. We have two arguments supporting the correspondence m1.

Figure 3 :

 3 Figure 3: Argumentation framework Argument A states that O1 : Paper Author and O2 : Author do have lexical similarity. Argument C supports the mapping m1 since their ancestors, O1 : Person and O2 : People, are mapped as established by the mapping m5.M o r e o v e r , we have two arguments against m2, and one for it: D is against the correspondence m2, since none of the superconcepts of O1 : Paper Author a r em a p p e dt oa n ys u p e rconcept of O2 : P aper; E is against the correspondence m2, since none of the sibling-concepts of O1 : P aper Author are mapped to any sibling-concepts of O2 : P aper;a n dC argues for m2, because O1 : Paper Author and O2 : Paper do have lexical similarity. The arguments D and E attack symmetrically the argument B. The arguments F and G justify the mapping m5, since, respectively, the labels of O1 : Person and O2 : People are synonymous and their subconcepts are mapped by m1 and m2. Clearly, argument G attacks the arguments D and E. Finally, the arguments H and I state that the concept O1 : Research T opic is mapped with O2 : Domain T opic and O2 : T opic since both have lexical similarity. The agent Ag2 does not have any counterarguments to rebut H and I. Given the two audiences, R1 and R2, the preferred extensions achieved are shown in Table4. The arguments that are accepted by both audiences are {A, C, G, F, H, I}.T h u s t h e agreed alignment is m1, m3, m4 and m5, while the mapping m2 is rejected (since B is unacceptable to R2).

Figure 4 :

 4 Figure 4: F-measure tests and comparisons argumentation F-measure represents the matching accuracy over all mappings present in the OMR, without considering the agents' preferences. The post-argumentation F-measure represents the matching accuracy achieved by the agents using our approach, based on the same initial set of candidate mappings. The results demonstrate that our approach not

Table 1 :

 1 Argument scheme for OWL ontological alignments ES(e),ES(e ′ ),n ′ , ≡ e and e ′ have mapped neighbours (e.g., super-entities, etc.) of e a r em a p p e di nt h o s eo fe ′ e, e ′ ,n,⊑ + ∃mi = ES(e),ES(e ′ ),n ′ , ≡ (some or all) neighbours (e.g., super-entities, etc.) of e are mapped in those of e ′ e, e ′ ,n,≡ + ∃mi = E(e),E(e ′ ),n ′ , ≡ (some or all) Instances of e and e ′ are mapped e, e ′ ,n,⊑ + ∃mi = E(e),E(e ′ ),n ′ , ≡ (some or all) Instances of e are mapped to those of e ′ e, e ′ ,n,≡ -∃mi = E(e),E(e ′ ),n ′ , ≡ No instances of e and e ′ are mapped e, e ′ ,n,≡ + label(e) ≈T label(e ′ ) Entities's labels share lexical features (e.g., synonyms, and lexical variants)

	Mapping	σ	Grounds	Comment
	e, e ′ ,n,≡	+	∃mi =

Table 2 :

 2 Communication between Agents

Table 4 :

 4 Preferred Extensions

	Preferred Extensions	Audience
	{I, H, B, C, G, A, F}, {I, H, B, G, C, E, A, F},	R1
	{I, D, H, B, C, G, E, A, F}, {I, H, D, B, G, C, A, F, G}
	{I, D, H, B, C, G, E, A, F}, {I, H, D, G, C, E, A, F}	R2

Table 3 :

 3 Arguments for and against the correspondences m1, m2, m3, m4, m5 The reference ontology is compared with four real-life ontologies for bibliographic references found on the web and left unchanged. Tests 301, 302, 303, 304.

	Id	Argument	A	V	Agent
	A	Label(Paper Author) ≈T Label(Author),m1, +		T	Ag1,Ag2
	B	Label(Paper Author) ≈T Label(Paper),m2, +	D,E	T	Ag1
	C	∃m = superclass(Paper Author), superclass(Author), 0.67, ≡, ,m1, +		ES	Ag1,Ag2
	D	∃m = superclass(Paper Author), superclass(Paper), 0, ≡, ,m2, -	B	ES	Ag2
	E	∃m = sibling(Paper Author), sibling(Paper), 0, ≡, ,m2, -	B	ES	Ag2
	F	Label(Person) ≈T Label(P eople),m5, +		T	Ag1,Ag2
	G	∃m = subclass(Person),subclass(P eople), ≡, ,m5, +	D,E	ES	Ag1,Ag2
	H	Label(Research Topic) ≈T Label(Domain T opic),m3, +		T	Ag1
	I	Label(Research T opic) ≈T Label(T opic),m4, +		T	Ag1
	lations, restrictions, etc. Tests 201, 202, 204, 205, 206, 221,
	222, 223, 224, 225, 228, 230.
	complex tests:

Table 5 :

 5 Ag1 and Ag2's preferences for each Test

	Te s t	Pref1	Pref2
	101,102,103,104,204,224,225,228,230	T ≻ ES	T ≻ ES
	201,202	T ≻ ES	ES ≻ IS ≻ T
	205,206,223	T ≻ ES	ES ≻ T
	221,301,302	T ≻ ES	T ≻ IS
	222,304	T ≻ ES	T ≻ IS ≻ ES
	303	T ≻ ES	T ≻ ES ≻ IS

http://www.w3.org/OWL/

http://oaei.ontologymatching.org/

Note that all these notions are now relative to some audience.

The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07)

A mapping m is supported by an argument x = G, m, + .

Termination of the dialogue is ensured by having a finite number of candidate mappings, plus a time-out to handle undecidable arguments.

http://nb.vse.cz/∼svabo/oaei2006/data/ekaw.owl

http://nb.vse.cz/∼svabo/oaei2006/data/OpenConf.owl

m1 states an equivalence correspondence with confidence 0.45 between the concept Paper Author in the ontology O1 and the concept Author in the ontology O2.

The tools selected were the best performers in OAEI'05.The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07)

Acknowledgements This work was partially supported by Knowledge Web (FP6-IST 2004-507482) and PIPS (FP6-IST 2004-507019).