Basak Alper
email: basakalper@gmail.com

Benjamin Bach
email: benjamin.bach@inria.fr

Nathalie Henry Riche

Tobias Isenberg
email: tobias.isenberg@inria.fr

Jean-Daniel Fekete
email: jean-daniel.fekete@inria.fr

Weighted Graph Comparison Techniques for Brain Connectivity Analysis

Keywords: Graph comparison, brain connectivity analysis, brain connectivity visualization. ACM Classification H.5.m. Information Interfaces and Presentation (e. g. HCI): Miscellaneous

The analysis of brain connectivity is a vast field in neuroscience with a frequent use of visual representations and an increasing need for visual analysis tools. Based on an in-depth literature review and interviews with neuroscientists, we explore high-level brain connectivity analysis tasks that need to be supported by dedicated visual analysis tools. A significant example of such a task is the comparison of different connectivity data in the form of weighted graphs. Several approaches have been suggested for graph comparison within information visualization, but the comparison of weighted graphs has not been addressed. We explored the design space of applicable visual representations and present augmented adjacency matrix and node-link visualizations. To assess which representation best support weighted graph comparison tasks, we performed a controlled experiment. Our findings suggest that matrices support these tasks well, outperforming node-link diagrams. These results have significant implications for the design of brain connectivity analysis tools that require weighted graph comparisons. They can also inform the design of visual analysis tools in other domains, e.g. comparison of weighted social networks or biological pathways.

INTRODUCTION

Understanding brain connectivity can shed light on the brain's cognitive functioning that occurs via the connections and interaction between neurons. The term brain connectivity refers to different aspects of brain organization including anatomical connectivity consisting of axonal fibers across cortical regions, and functional connectivity defined as the observed statistical correlations between regions of interest (ROIs)-units of neu- ral groupings or anatomically segregated brain regions [START_REF] Horwitz | The Elusive Concept of Brain Connectivity[END_REF]. Although, the processes for acquiring the two types of connectivity data differ, they can both be expressed as weighted graphs in which nodes represent ROIs and edges can encode the strength of their correlation (functional) or the density of fibers connecting them (anatomical).

Recent research in neuroscience successfully began to analyze the connectivity data using graph theoretical methods [START_REF] Ginestet | Statistical Parametric Network Analysis of Functional Connectivity Dynamics during a Working Memory Task[END_REF] and statistics [START_REF] Zalesky | Network-Based Statistic: Identifying Differences in Brain Networks[END_REF]. However, visualization systems can provide significant insights for the discovery of unforeseen structural correlation patterns, in particular across several datasets. For example, comparing patterns of functional connectivity and anatomical connectivity pre-and post-removal of parts of brain tissue may help neuroscientists to understand how the brain rewires itself to restore its function. Although statistical and graph theoretical methods are available for such analysis, visualization systems featuring connectivity comparison tools can provide significant insights for the discovery of unanticipated correlation patterns. Visual graph comparison, thus, can be an essential tool for comprehensive brain connectivity analysis.

To build effective interfaces for brain connectivity analysis, we identify common visual analysis tasks that neuroscientists carry out in brain connectivity analysis based on interviews with neuroscientists and an in-depth review of the domain literature. By doing so, we provide a link from domain-specific problems in neuroscience to more generic problems in HCI and visualization. Based on this task identification, we also establish that weighted graph comparisons can benefit a group of higher-level tasks in visual brain connectivity analysis. We explored alternative visual encodings that facilitate the comparison of edge weights across two graphs in a superimposed view, both in node-link diagrams and adjacency matrices.

Finally, we report on a controlled experiment comparing two of these representations (Fig. 1) for their ability to encode connection weights of two graphs. Results of the study led us to implications for the design of brain connectivity visualization tools. While weighted graphs are present in a plethora of domains: computer networks, social networks, biological pathways networks, air traffic networks, commercial trade networks; very few tools currently exist to represent and compare them. As we used generic comparison tasks during the study, our results can also inform the design of general weighted graph comparison tools.

HIGH-LEVEL BRAIN CONNECTIVITY ANALYSIS TASKS

Neuroscientists investigate brain connectivity to answer questions such as how brain connectivity changes throughout development, with aging, or with physical injury, what kind of connectivity patterns are required for a particular functionality, and how these connectivity patterns show variances across individuals and across certain anomaly conditions. Some of the subtasks carried out during these explorations can be supported by visualizations. Through a literature survey and a series of one-hour long interviews with seven neuroscientists, we identified a list of major tasks in brain connectivity analysis where visualizations are already in use or can be used to aid and enhance the analysis:

1. Identify network structures that are responsible for a specific cognitive function: Neuroscientists examine how our brain carries out specific cognitive functions, identify the regions responsible or involved, and study their interaction with each other while executing these functions [START_REF] Vidal | Long-Distance Amplitude Correlations in the High Gamma Band Reveal Segregation and Integration within the Reading Network[END_REF]. However, significant individual variations exist. These variations require the comparison of connectivity data of large subject groups to be able to identify common network structures.

2.

Identify effects of anatomical structure on functional connectivity: Understanding the effect of anatomical structure on the formation of functional relations is a key challenge in neuroscience [START_REF] Bullmore | Complex Brain Networks: Graph Theoretical Analysis of Structural and Functional Systems[END_REF][START_REF] Honey | Network Structure of Cerebral Cortex Shapes Functional Connectivity on Multiple Time Scales[END_REF][START_REF] Honey | Predicting Human Resting-State Functional Connectivity from Structural Connectivity[END_REF]. For this purpose, scientists look for correlated patterns across anatomical and functional connectivity, requiring the simultaneous exploration of the two connectivity data to reveal complex mappings between.

3. Identify alterations in brain connectivity: Brain connectivity of an individual changes over time-through development and with aging [START_REF] Dosenbach | Prediction of Individual Brain Maturity Using fMRI[END_REF]. Another instance of alteration in brain connectivity is the development of re-routings that restore functionality typically after a local injury [START_REF] Cao | Alteration of Cortical Functional Connectivity as a Result of Traumatic Brain Injury Revealed by Graph Theory, ICA, and sLORETA Analyses of EEG Signals[END_REF]. In addition, changes in white matter fiber connectivity following behavioral training of a complex skill have also been reported [START_REF] Scholz | Training Induces Changes in White-Matter Architecture[END_REF]. In order to understand the temporal evolution of these changes, scientists need to compare connectivity data gathered at different instances in time.

4.

Identify the existence or the loss of patterns in brain connectivity that are associated with anomalous conditions:

Neuroscientists have already shown that certain cognitive anomalies are associated with the loss of specific connectivity patterns [START_REF] Bassett | Hierarchical Organization of Human Cortical Networks in Health and Schizophrenia[END_REF][START_REF] Sanz-Arigita | Loss of 'Small-World' Networks in Alzheimer's Disease: Graph Analysis of fMRI Resting-State Functional Connectivity[END_REF]. For instance in Alzheimer's disease, it is observed that functional connectivity does not exhibit small-world properties as much as a healthy brain [START_REF] Sanz-Arigita | Loss of 'Small-World' Networks in Alzheimer's Disease: Graph Analysis of fMRI Resting-State Functional Connectivity[END_REF].

Identifying such differences in connectivity patterns is essential for the diagnosis and treatment of these anomalies, which can be done by comparing the connectivity of the anomalous brains to healthy ones.

Identify deviation of an individual's connectivity from a population mean:

The aforementioned tasks often utilize an 'average' brain-the term 'average' encompassing connectivities that are common to all individuals. The average brain, in turn, can be used to characterize an individual's brain by studying the deviation of it from the average brain.

6. Effective brain parcellation and multimodal connectivity analysis: Identifying brain structures that act as a unit is an important problem. Automatic parcellation algorithms, based on statistical likelihood of synchronized activation, are employed to identify these units. A variety of statistical techniques along with multiple data sources exist each yielding different parcellations. For example, an automatic parcellation based only on functional connectivity data can be refined by taking into account fiber connectivity [START_REF] Li | Visual Analytics of Brain Networks[END_REF], or anatomy-based parcellation can be validated by functional connectivity relationships between the regions [START_REF] Beckmann | Connectivity-Based Parcellation of Human Cingulate Cortex and Its Relation to Functional Specialization[END_REF]. Thus, different parcellation outcomes are needed to be compared to verify the robustness of a technique [START_REF] Worsley | Comparing Functional Connectivity via Thresholding Correlations and Singular Value Decomposition[END_REF].

Identify effects of local injury:

In clinical applications it is important to predict the effect of a local injury. A localized damage of anatomical structure can have multiple implications on functional connectivity due to the loss of indirect as well as direct connections. Similarly, in image-guided neurosurgery [START_REF] Archip | Non-Rigid Alignment of Pre-Operative MRI, fMRI, and DT-MRI with Intra-Operative MRI for Enhanced Visualization and Navigation in Image-Guided Neurosurgery[END_REF], identifying optimal surgical paths that minimize damage induced by intervention is also important. In order to be able to make these decisions, neurologists look at brain connectivity data in a spatial context and observe which anatomical and functional connections are associated with which specific brain locations.

This summary shows that a large number of neuroscientific problems can be facilitated with weighted graph comparison tools. Apart from the last task, for which connectivity data has to be presented in its spatial context (inside the brain volume), all other tasks can be conducted with non-spatial representations such as 2D node-link diagrams and adjacency matrices. Although it is essential for brain connectivity analysis to communicate spatial context of the data to ease the interpretation, non-spatial representations can prove more effective for communicating changes in complex connectivity data, as they relax a set of strong constraints on the visual representations (such as preserving the exact shape of connections in three dimensions). Hence, tools supporting brain connectivity analysis have to offer multiple visual representations-each of which are optimal for specific set of tasks. In this paper our focus is on connectivity comparison tasks which, at an abstract level, can be expressed as comparison of two weighted graphs.

RELATED WORK

Work relating to our own can be found in three domains: the study of brain connectivity in neuroscience, the use of visualizations within this domain, and research on graph comparison and weighted graph visualizations in information visualization. We review each of these areas below.

Brain Connectivity

Functional connectivity data is derived from functional magnetic resonance imaging (fMRI). Based on the blood oxygen consumption level, fMRI images show active regions of the brain at a given instance. Neuroscientists apply a variety of statistical and computational methods over collections of fMRI images to characterize global structures in the coordinated neural activity [START_REF] Rajapakse | Learning Effective Brain Connectivity with Dynamic Bayesian Networks[END_REF][START_REF] Seth | A MATLAB Toolbox for Granger Causal Connectivity Analysis[END_REF]. Functional connectivity, therefore, can be seen as a relatedness among specific region of interests (ROIs) in the brain which are highly correlated functionally. Thus, functional connectivity among ROIs can be represented as a fully connected, weighted relatedness graph.

White matter fibertracts, the so called anatomical connectivity structures, are derived through applying tractography algorithms to diffusion tensor imaging (DTI) data which represents anisotropic diffusion of water through bundles of neural axons. The resulting fibertracts (representing axon bundles) are often clustered based on their trajectory similarities and regions that they connect to [START_REF] Jianu | Exploring 3D DTI Fiber Tracts with Linked 2D Representations[END_REF]. It is possible to define a fiber connectivity measure between all ROI pairs depending on the fibertract density between them [START_REF] Hagmann | Mapping the Structural Core of Human Cerebral Cortex[END_REF]. Hence, similar to functional connectivity, anatomical connectivity between regions of the brain can be expressed as a weighted graph.

Use of Visualizations in Brain Connectivity Analysis

Defined as a correlation matrix between specific locations within the brain volume (ROIs), functional connectivity data is often visualized as 3D node-link diagrams: ROIs are shown as nodes and weighted edges denote the pairwise strength of these node relationships (e. g., Fig. 2(a)). Although the edges below a certain strength threshold can be hidden, the resulting images are still cluttered and suffer from the known side effects of 3D rendering such as occlusion [START_REF] Dosenbach | Prediction of Individual Brain Maturity Using fMRI[END_REF][START_REF] Gerhard | The Connectome Viewer Toolkit: An Open Source Framework to Manage, Analyze, and Visualize Connectomes[END_REF]. To facilitate comparison, two connectivity datasets can be overlaid within the 3D brain [START_REF] Worsley | Comparing Functional Connectivity via Thresholding Correlations and Singular Value Decomposition[END_REF], with edge colors denoting correlation and anti-correlation between the end points. However, the clutter and complexity of the visual encoding in these spatial/volumetric representations makes it difficult to perform accurate weighted edge comparison tasks.

An alternative approach is to show the connectivity data as a 2D node-link diagram whose layout is calculated by multidimensional scaling or force-directed algorithms [START_REF] Achard | Low-Frequency, Small-World Human Brain Functional Network with Highly Connected Association Cortical Hubs[END_REF] (e. g., Fig. 2(c)). These layouts remedy some of the clutter problems by eliminating overlaps and reducing number of long edges. They are thus adopted especially among those scientists who practice graph-theoretical analysis of brain connectivity. The spatial context of the data, however, is still crucial for an effective interpretation of the data by neuroscientists who are trained to reason with respect to spatial brain regions. Hence, node-link diagrams are often accompanied with a separate spatial rendering of the node positions, with nodes on the two representations being matched by region color and label [START_REF] Nelson | A Parcellation Scheme for Human Left Lateral Parietal Cortex[END_REF].

To preserve the spatial character of the data to some extent, many 2D connectivity node-link diagrams adopt a biological layout where node positions are projections on 2D planes defined by two of the standard anatomical axes (e. g., ventrodorsal, anteroposterior, left-right; e. g., Fig. 2(b)) [START_REF] Achard | Low-Frequency, Small-World Human Brain Functional Network with Highly Connected Association Cortical Hubs[END_REF]. These layouts communicate spatial properties of the data coarsely, helping scientists orient themselves in the graph, while en- abling the use of color for encoding other information such as change across two states [START_REF] Bassett | Hierarchical Organization of Human Cortical Networks in Health and Schizophrenia[END_REF][START_REF] Richiardi | Decoding Brain States from fMRI Connectivity Graphs[END_REF].

(a) (b) (c) (d) (e) (f)
Matrices of functional connectivity as an alternative representation are also popular [START_REF] Achard | Low-Frequency, Small-World Human Brain Functional Network with Highly Connected Association Cortical Hubs[END_REF][START_REF] Gerhard | The Connectome Viewer Toolkit: An Open Source Framework to Manage, Analyze, and Visualize Connectomes[END_REF][START_REF] Sanz-Arigita | Loss of 'Small-World' Networks in Alzheimer's Disease: Graph Analysis of fMRI Resting-State Functional Connectivity[END_REF] and are occasionally used in the form of small multiples to illustrate trends across different connectivity datasets [START_REF] Bassett | Conserved and Variable Architecture of Human White Matter Vonnectivity[END_REF][START_REF] Ginestet | Statistical Parametric Network Analysis of Functional Connectivity Dynamics during a Working Memory Task[END_REF][START_REF] Kramer | Emergence of Persistent Networks in Long-Term Intracranial EEG Recordings[END_REF]. To support direct comparisons, correlation coefficients from multiple scan states can be shown within nested quadrants of a matrix cell [START_REF] Thomason | Resting-State fMRI Can Reliably Map Neural Networks in Children[END_REF]. However, this design makes it hard to focus on a single scan state.

Representing physical entities, fibertracts that constitute anatomical connectivity are more frequently visualized within the 3D brain volume [START_REF] Gerhard | The Connectome Viewer Toolkit: An Open Source Framework to Manage, Analyze, and Visualize Connectomes[END_REF] (e. g., Fig. 2(d)). Research in fiber connectivity visualization focuses on their similarity clustering, bundling, and selection in 3D space [START_REF] Moberts | Evaluation of Fiber Clustering Methods for Diffusion Tensor Imaging[END_REF][START_REF] Sherbondy | Exploring Connectivity of the Brain's White Matter with Dynamic Queries[END_REF] as well as on illustrative depiction [START_REF] Everts | Depth-Dependent Halos: Illustrative Rendering of Dense Line Data[END_REF]. While non-spatial representations for fiber similarity and clustering are also used [START_REF] Jianu | Exploring 3D DTI Fiber Tracts with Linked 2D Representations[END_REF], neuroscientists reported difficulties with interpreting these representations. Related to our work, anatomical connectivity can be reduced to a fiber density graph among ROIs and vi-sualized as a 3D spatial node-link diagram combined with a matrix representation [START_REF] Hagmann | Mapping the Structural Core of Human Cerebral Cortex[END_REF] (e. g., Fig. 2

(e)-(f)).

So far, the coordinated visualizations of structural and functional connectivity has received little attention, and existing visualizations focus on spatial representations rather than supporting abstract graph comparison tasks. Several tools (e. g., ConnectomeViewer [START_REF] Gerhard | The Connectome Viewer Toolkit: An Open Source Framework to Manage, Analyze, and Visualize Connectomes[END_REF][START_REF] Li | Visual Analytics of Brain Networks[END_REF]) support visual brain connectivity analysis using spatial 3D node-link and matrix representations for functional connectivity and volumetric fibertract representations for anatomical connectivity. Although it is crucial to communicate the spatial context in brain connectivity analysis for several tasks, 2D non-spatial representations with flexible layouts are more suitable to communicate differences/changes in the connectivity data in an explicit way. To the best of our knowledge, none of the existing brain connectivity tools supports such a visual connectivity comparison.

Weighted Graph Visualization and Comparison

A weighted graph is visualized either as a node-link diagram or an adjacency matrix. In node-link diagrams, weight is either mapped to the length of an edge with inverse proportions [START_REF] Collberg | A System for Graph-Based Visualization of the Evolution of Software[END_REF] or is encoded in the thickness and/or color of an edge [START_REF] Epskamp | qgraph: Network Visualizations of Relationships in Psychometric Data[END_REF]. In matrix visualizations, the weight of a connection is mapped either to the color of the corresponding cell or to the size of a glyph inside the cell [START_REF] Van Ham | Honeycomb: Visual Analysis of Large Scale Social Networks[END_REF]. Among these representations, people most commonly encode weight as edge thickness in node-link diagrams. However, to the best of our knowledge, there is no study on alternative visual encodings of edge weight for graphs nor their comparison.

Comparison of weighted graphs is an open research question. However, various comparison techniques are proposed for unweighted graphs in a number of domains for problems related to characterization of metabolic pathways [START_REF] Brandes | Visual Understanding of Metabolic Pathways Across Organisms Using Layout in Two and a Half Dimensions[END_REF][START_REF] Schreiber | Comparison of Metabolic Pathways using Constraint Graph Drawing[END_REF], business process models [START_REF] Andrews | Visual Graph Comparison[END_REF] and software evolution [START_REF] Collberg | A System for Graph-Based Visualization of the Evolution of Software[END_REF].

We can categorize techniques for comparing unweighted graphs as follows: (i) juxtaposed views where two graphs are presented side-by-side and often complemented with interactive techniques that highlight the matches between the two [START_REF] Andrews | Visual Graph Comparison[END_REF], (ii) superimposed or overlaid views where a single layout is used for both graphs while differing edges and nodes are color coded [START_REF] Andrews | Visual Graph Comparison[END_REF][START_REF] Erten | GraphAEL: Graph Animations with Evolving Layouts[END_REF][START_REF] Hascoët | Interactive Graph Matching and Visual Comparison of Graphs and Clustered Graphs[END_REF], and (iii) animated views where positions of nodes are interpolated between the two graphs, while added or removed elements are faded in or out respectively [START_REF] Diehl | Graphs, they are Changing: Dynamic Graph Drawing for a Sequence of Graphs[END_REF][START_REF] Erten | GraphAEL: Graph Animations with Evolving Layouts[END_REF]. A more detailed categorization of these techniques was presented by Gleicher et al. [START_REF] Gleicher | Visual Comparison for Information Visualization[END_REF], who also emphasize the continuing necessity of comparison tools in visualization.

Similar techniques exist for depicting dynamic graphs to communicate changes during a graph's evolution. Work in this area focuses on the preservation of a viewer's mental map by restricting layout changes across time steps. This approach facilitates the detection of temporal patterns in both animated and multiple juxtaposed views [START_REF] Archambault | Small Multiples, and the Effect of Mental Map Preservation in Dynamic Graphs[END_REF][START_REF] Diehl | Preserving the Mental Map using Foresighted Layout[END_REF]. Although important, these methods do not easily extend to brain connectivity data where mental map preservation involves spatial aspects of the data, hence requires a deterministic biological layout.

Nevertheless, weighted graph comparison-a crucial component in brain connectivity analysis-has yet to be addressed.

VISUALIZATION DESIGN RATIONALE

In the following we discuss our choices for visually coupled presentation of two graphs and visual encodings adopted in node-link and matrix visualizations.

Visually Coupled Graph Representations

Comparing two weighted graphs requires communicating absence or presence of connections, as well as their absolute weights in both graphs. As mentioned above, three alternative representations exist for presenting two graphs: side-by-side (juxtaposed), overlaid (superimposed), and animated views. While smooth animations are effective for observing trends over multiple states, they do not provide information about two graphs in a single image. Additionally, smooth animations may increase the time requirement as the viewer may need to watch the animation repeatedly when multiple elements from both graphs need to be compared. Therefore, we only considered side-by-side and overlaid representations.

From informal feedback on our initial implementations, sideby-side views proved to be much slower and error-prone compared to the overlaid views-likely due to the fact that the distance to be covered even for simple comparison tasks is much higher in the side-by-side view compared to the overlaid views (element lookup). The difference increases tremendously as the graphs get larger. Moreover, side-by-side views necessitate about double the screen space compared to the overlaid or animated views.

The last alternative, overlaid views has the potential drawback of visual clutter due to added visual elements. However, for the data sizes and densities we consider in this work, we found overlaid representations to be better suited for the effective execution of the comparison tasks. We thus decided to base our visualizations on overlaid views.

Edge Weight Visual Encoding in Node-Link Diagrams

The design space for the visualization of weighted graphs is, in fact, limited to the use of color (intensity or hue) or size on edges in node-link diagrams or glyphs inside the cells in matrix visualizations. However, these mappings do not suffice when edge weights from two graphs need to be shown in an overlaid view. Although it is most common to use edge thickness in node-link diagrams for encoding weight, this approach increases the space requirements especially when edges from two graphs need to be shown. Moreover, when node-link diagrams represent dense graphs, it is important to keep edge thickness at a minimum.

We examined two other options for overlaid edge weight encoding. First, we considered two constant width parallel edges with two different color scales-each encoding the edge weight from one graph (Fig. 3(b)). As the alternative, we considered stacking a dashed edge on a normal edge, enabling viewers to see the line underneath the dashed line (Fig. 3(a)).

We tried both alternatives with our datasets and found continuous parallel lines to be more legible, especially for dense graphs. Dashed lines caused much change of color through the entire visualization, making the overview seem cluttered and edges of one graph difficult to isolate.

Edge Weight Visual Encoding in Matrices

Matrix representations which eliminate occlusion problems that degrade node-link diagrams facilitate the encoding of additional information in cells more effectively [START_REF] Elmqvist | Interactive Large-Scale Graph Visualization[END_REF]. Our initial approach for encoding the weight within a matrix cell was to use scaled glyphs such as concentric circles (Fig. 3(c)). Here the radius of the inner circle is mapped to the union weight and change from one graph to the other is mapped to the outer circle radius, while decrease and increase is differentiated by color. We did not pursue this approach further because of the difficulty of identifying a single connectivity state. Besides, when the difference is minimal, the borders produced between inner and outer circles became illegible within the limited cell space.

Next, we examined color-coded bar charts shown within the cell to show the absolute weight from each graph (Fig. 3(d)).

We eliminated this approach due to the horizontal line patterns it produced and also complicated focusing on weights from one graph at a time. We investigated alternative ways of dividing matrix cells into two regions and using a separate color scheme for each region to encode weight from the corresponding graph. We tried vertical, horizontal, and diagonal divisions (Fig. 3(e)) but they all produced patterns interfering with the cell boundaries of the matrix.

Finally, we adopted an inner and outer squares division (Fig. 3(a)) where the edge weight from each graph is mapped to the color density of the corresponding region. We considered this approach useful since it did not obscure the matrix' grid structure. It also allowed us to use brightness alone to encode weight since it was possible to differentiate graphs based on the spatial encoding (inner vs. outer)-freeing up hue to encode other data attributes. As a natural outcome of this encoding, the amount of change is mapped to the contrast between inner and outer regions of a cell, easily enabling viewers to differentiate regions with high and low change.

CONTROLLED STUDY

In this study we investigate the effectiveness (accuracy, task completion time) of the described node-link diagrams and ma-trices (Fig. 4) when comparing two graphs (G 1 , G 2 ) with different edge weights. Our goal is to assess how both techniques scale with changing graph sizes and edge densities across different comparison tasks, to inform designs that would utilize both representations. Representative tasks for the study were derived from common tasks in analyzing differences in brain connectivity, as previously described.

Techniques

We used the visual encodings described in the previous section for overlaying two graphs in node-link and matrix visualizations. In all techniques, the entire information is shown in one full-screen window without a need to zoom or pan. This design eliminates any confounds due to navigation issues rather than reading of the visual representation to complete the task. Since one of our tasks required identifying a specific region, we reordered rows and columns of the matrix to ensure that nodes were placed in the same regions in both the matrix view and the node-link diagram. To provide users with stable representations across all tasks, we used this ordering for all trials. The tradeoff of this ordering is, however, that it did not ensure a close placement of items that need to be compared during other tasks, as other reordering algorithms could have.

Node-Link Diagram-Overlaid (NL):

A single node-link diagram shows edge weights in both graphs using two parallel edges. Connections that are present in G 1 are encoded in green colored edges, while connections that are present in G 2 are encoded with the red colored edges (Fig. 5(b)). Thus, a single green edge represents an edge that was only present in G 1 , while a single red edge represents an edge that was only present in G 2 . The absolute edge weight is encoded using brightness as in the matrix condition, and we ensured that values for the same edge weight had the same brightness. To ensure the generalizability of our results, we eliminated the fixed biological layout alternative and only used a force-directed layout. We made this choice because fixed layouts produce less optimal arrangements with re- spect to edge crossings and visual clutter, thus are likely to decrease the performance of node-link diagrams.

Tasks

Based on our task analysis in this paper's second section, we identified three generic comparison tasks that are required for successfully executing high-level brain connectivity comparisons. These tasks require users to assess changes in edge weights at different level of details: from a single element to the overview of a large portion of the data. Below we describe each task and the optimal strategy for achieving it.

Assess weight change of a node's connections (Trend):

Given one highlighted node, does the overall edge weight to all of its neighbors decrease or increase from G 1 to G 2 ? Participants completed this task in three steps: (1) they needed to identify all connections to the highlighted node, (2) they needed to assess the change in weight for each connection, and (3) they needed to estimate the aggregated change for all these connections. To avoid confounds in the study, we made sure all trials exhibited a clear increase or decrease trend. To prevent participants from selecting one option at random, we offered an additional "I don't know" option and instructed them to select it if their confidence was low. We excluded these trials from the analysis.

Assess connectivity of common neighbors (Connectivity):

Given two highlighted nodes, how many of their common neighbors in G 1 are still common neighbors in G 2 ? Participants completed this task in two steps: (1) they needed to find common neighbors, meaning the nodes that are connected to both of the highlighted nodes and (2), among them, they needed to count how many are present in both graphs. Participants selected an option from 0 to 6.

Identify the region with most changes (Region): Identify the region showing the most variation between G 2 and G 1 ? For this task we provided users with simple interaction tools to view regions. In the node-link case, we divided the diagram into a 4 × 4 grid and assigned each node to the region it fell into. As participants moved their mouse pointer on the diagram, the corresponding region boundary appeared in light blue and nodes of the region became highlighted (Fig. 5(a)). In the matrix condition, we used the same 16 regions, ordering the nodes linearly according to the regions they belonged to. As participants moved their mouse pointer on the matrix, the region boundaries were highlighted (Fig. 5(b)).

Participants completed this task by browsing each region successively, estimating the region with highest edge weight variation. To avoid confounds in the study, we ensured that all trials presented a region with discernably higher variation than the rest. Participants clicked on a region of their choice.

Data

We used synthetic data in order to ensure generalizability of the results, and to be able to control data size and density. We generated four types of uniform networks with either 40 (Small) or 80 (Large) number of nodes, and with either 5% (Sparse) or 10% (Dense) edge density. For each data type, we created four isomorphic networks per trial which were used across all tasks. We created five additional datasets for training with a Small, Sparse metric. The edge weights were assigned arbitrarily to each of the generated graphs, ranging from 0 to 1 in increments of 0.2. We created comparison graphs by copying the original weighted graphs and then randomly perturbing the edge weights of 70% of the edges in order to ensure edge weights that remain constant across the graphs.

Participants and Setting

11 participants (1 female) participated in the study with a mean age of 30.2 years. All participants had normal or correctedto-normal vision, without color deficiency. Participants were graduate students or researchers, familiar with graphs. The experiment was conducted in a quiet room during the day. The study computer was a 2.4 GHz Dual-Core HP Z800 workstation equipped with a 30 inch screen with a 2500 × 1600 pixel resolution. The visualization area was restricted to window of 1500 × 1350 pixels. Participants interacted with a mouse and keyboard to complete the tasks.

Experimental Procedure

We used a within-subject, full-factorial design: 2 Techniques × 3 Tasks × 2 Sizes × 2 Densities. We repeated each condition four times. We counter-balanced the techniques (M, NL) using a Latin square. Tasks appeared always in a fixed order of increasing complexity (Trend, Connectivity, and Region). Datasets also appeared in a fixed order from simple (Small and Sparse) to more complex (Large and Dense). For each trial, we measured accuracy and task completion time.

Before the controlled experiment, we instructed participants about the visualizations as well as the weight encoding used in each, making sure none of them had any vision problems. We asked them to complete trials as accurate and as fast as possible. Before each new technique and task, five training trials were provided. Participants completed the first two following the explanations of the instructor. They answered the remaining trials on their own unless they had further questions. Trials were not timed during the training. After training trials, participants completed the 16 timed trials (2 Size × 2 Density × 4 Repeat) required for each condition (technique × task). For all conditions, we collected a total of 96 trials per participant (excluding training).

To keep the experiment within a reasonable time, we limited the time per trial to 30 seconds (measured as a feasible value in a pilot study) and notified participants before the experiment. After 20 seconds, the screen flashed and a time counter appeared below the visualization for the remaining 10 seconds.

To provide their answer, participants pressed the space bar to view the dialog box with the answers. After this point, the timer stopped and the visualization disappeared. Participants were instructed to take breaks if needed when no visualization was shown on the display. None of the participants took a noticable break nor reported any fatigue.

Hypotheses

Our hypotheses for the experiment were the following:

• H1-For the Trend task, we expected Matrix to outperform (accuracy and completion time) Node-Link for high-density datasets. We expected that occlusion problems in Node-Link would get severe in Dense cases, causing more errors. We also believed that the spatial encoding used in Matrix would prove easier to remember than the color encoding used in Node-Link, leading to faster answers.

• H2-For the Connectivity task, we expected Matrix not to outperform Node-Link because we believed participants might need to compare two distant columns or rows in Matrix, whereas the force-directed layout in Node-Link ensures that connected nodes are in closer proximity.

• H3-For the Region task, we expected Matrix to outperform Node-Link (accuracy and completion time). In Matrix, all connections of nodes in one region are contained within the region boundary. However, in Node-Link, participants had to consider links that are drawn across region boundaries, leading to more errors and slower answers.

• H4-Overall, we expected Node-Link to decrease in performance (accuracy and completion time) for Dense datasets, as edge density causes many edge crossings, decreasing the legibility of this representation.

Results

We used a repeated-measure analysis of variance (RM-ANOVA) to analyze the collected accuracy and time performance data. We performed the RM-ANOVA on the logarithm of the task times to normalize the skewed distribution, as is standard practice with reaction time data. The analysis of the time performance is reported for correct answers only.

Accuracy. The accuracy results are summarized in Table 1 and Fig. 6(a). We found a significant effect of accuracy for Technique (F (1,10) = 55.32, p < .0001) with a large effect size (η 2 p = .85). Overall, Matrix is about 20% more accurate than Node-Link. The RM-ANOVA also revealed a significant effect of Task (F (2,20) = 28.67, p < .0001) with large effect size (η 2 p = .74), and a significant effect of the interaction Task × Technique (F (2,20) = 4.34, p < .05) with a large effect size (η p = .30). Pairwise comparisons revealed that Matrix is more accurate than Node-Link for all three tasks. We also found a significant effect of Size (F (1,10) = 18.69, p < .01) with a large effect size (η 2 p = .65) and Density (F (1,10) = 61.00, p < .0001) with a large effect size (η 2 p = .86). As expected, accuracy decreases for Large or Dense networks. The interaction Technique × Size (F (1,10) = 6.5, p < .05) is significant with a large effect size (η 2 p = .39). Node-Link is affected by Size, losing about 25% accuracy in large datasets compared to small ones. In contrast, Matrix has less than 1% loss in accuracy. Pairwise comparisons indicate that Matrix significantly outperforms Node-Link for large networks across all three tasks. The results indicate that both Techniques are affected by Density, Matrix losing about 10% accuracy, Node-Link about 20%. Pairwise comparisons indicate that Matrix significantly outperforms Node-Link both for Sparse and Dense networks across all three tasks. Completion Time. We analyzed the completion time for correct answers only, using a mixed linear model capable of handling missing data cases. We excluded about 10% incorrect trials for Matrix and 30% for Node-Link (out of 528 total trials per technique).

The completion time results are summarized in Table 2 and Fig. 6(b). We found a significant effect of time for Technique (F (1,10) = 28.40, p < .0001). Overall, Matrix is 15% faster than Node-Link. We also found a significant effect of Task (F (2,20) = 183.25, p < .0001) and Technique × Task (F (2,20) = 3.82, p < .05). Pairwise comparisons reveal that Matrix is faster than Node-Link for Connectivity and Region tasks.

We also found a significant effect of Size (F (1,10) = 139.19, p < .0001) and Density (F (1,10) = 30.94, p < .0001). As expected, User Preference. Users rated their preference on a 5-point scale from -2 (strong preference for Node-Link) to +2 (strong preference for Matrix). We analyzed these ratings using a z-test. Results reported in Table 3 reveals that there is a significant difference in user preference between Techniques. Users preferred Matrix overall (p < .0001). In fact, 7 out of 11 participants ranked Matrix as the most effective representation (maximum rating of 2). Z-test also showed that the user preference was significantly different for the Connectivity (p < .0001) and the Region tasks (p < .0001). For these tasks, Matrix was preferred to Node-Link.

DISCUSSION

The results of our controlled experiment indicate that matrix representations are more effective than node-link diagrams for encoding edge weights and performing comparison tasks.

While we expected that it would be the case for the Trend (H1) and Region (H3) tasks in the Dense datasets, we were surprised to find significant differences in accuracy across all tasks for both sparse and dense networks.

We also did not expect a significant performance difference across techniques for Connectivity (H2). While we did not find any significant difference in completion time for correct answers, the results indicated that matrix outperformed nodelink in accuracy, contradicting (H2).

Although we originally thought that comparison in matrices may be error-prone since the rows or columns to be compared may be far away, we in fact observed that the linear arrangement of the matrix allowed people to inspect each of the candidate neighbors successively. In contrast, despite common neighbors being placed closer together in space in the node-link diagram, performance suffered from the less systematic manner to count them, leading to a decrease in accuracy.

We did not expect the strong performance decrease of nodelink diagrams for large networks, in addition to dense ones (H4). We believe that this happened because, although we used a fixed edge density, the total number of edges increases quadratically with a linear increase in number of nodes. The total number of links shown in large sparse datasets, thus, is much higher than small sparse datasets. To offer a similar visual complexity in small and large graphs, we could envision to control the edge density per display area unit.

Implications for design

The findings of the study indicate that, for edge weight comparisons, node-link representations are more error-prone and less readable than matrices. However, node-link diagrams offer a flexible layout that can be adjusted to reflect spatial characteristics of the data much more effectively than the linear matrix orderings allow. Therefore, while scientists should adopt matrix representations to ensure better accuracy when performing comparison tasks, efforts have to be made to augment these visualizations with spatial context or couple them with appropriate spatial representations.

A second point to consider relates to the datasets' density.

While we tested graphs with connection densities of 5% and 10%, brain connectivity data is, in fact, a fully connected graph with a wide range of weight values; it becomes spare after thresholding: removing edges with weight under a specified threshold. One classical criteria for thresholding is to limit the density of the graph to be readable using a node-link representation. For certain tasks, it may be preferable to analyze the entire connectivity information to spot patterns in weak connections. In such cases, matrix representations are the best choices as they scale better with density. For other cases such as the presentation of key findings, however, node-link diagrams may be a better choice because they are more compact for presenting significant trends and are better at preserving the spatial context.

CONCLUSION AND FUTURE WORK

The comparison of brain connectivity patterns is a general problem in the neurosciences. To address it, we have gathered a list of seven tasks that are very common in this domain, both from interviews with experts and from a literature survey, and shown that most of these tasks can be translated to weighted graph comparisons. To support these tasks, we have explored the design space of applicable visual representations. We chose the two most suitable: one augmenting node-link diagrams and the other augmenting adjacency matrices. We thus designed novel visual representations to depict the edges along with the two weights to be compared between graphs.

Based on this visualization design we performed a controlled study, comparing the two representations using two graph sizes and two graph densities. The results show that matrices outperform node-links for the chosen tasks, especially when the graph becomes dense or large. Our recommendation is thus that matrices should be used unless the graph is small and sparse. To the best of our knowledge, this paper is the first to present visualizations designed for weighted graph comparison tasks as well as a controlled study of their effectiveness.

The tasks that we selected in our study consider the graphs to be non-spatial. Spatial representations, however, are still essential for neuroscientists especially for tasks that rely on spatial locations such as comparing patterns around an injury in the brain. As for future work, we will investigate integration of our proposed non-spatial visualization with spatial visualizations.

Since weighted graphs exist in a wide variety of domains such as social and computer networks, we will also investigate other application areas for our proposed visualization. While some useful tasks for these domains are likely to differ from the ones we considered, we believe our visual representations are still suitable and that our results would still hold, although variations in the visual encodings could certainly improve some particular domain-dependent tasks.

Figure 1 .

 1 Figure 1. Alternative superimposed (a) matrix and (b) node-link visualizations supporting weighted graph comparisons.

Figure 2 .

 2 Figure 2. Existing visualization techniques for brain connectivity. Left column, functional connectivity: (a) 3D spatial node-link diagram within the brain volume (courtesy of Erik Ziegler, Cyclotron Research Centre, Univ. of Liège, generated with ConnectomeViewer [19]), (b) 2D nodelink diagram with biological layout[START_REF] Achard | Low-Frequency, Small-World Human Brain Functional Network with Highly Connected Association Cortical Hubs[END_REF], and (c) force-directed node-link accompanied with a spatial visualization showing actual positions of the nodes[START_REF] Nelson | A Parcellation Scheme for Human Left Lateral Parietal Cortex[END_REF]. Right column, anatomical connectivity: (d) fibers within the 3D volume of the brain, (e) fiber density ROI graph as a spatial node-link diagram[START_REF] Hagmann | Mapping the Structural Core of Human Cerebral Cortex[END_REF], and (f) matrix representation of fiber densities between ROIs[START_REF] Hagmann | Mapping the Structural Core of Human Cerebral Cortex[END_REF]. All images reproduced with authors' permissions.

Figure 3 .

 3 Figure 3. Examples of all visual encodings examined to facilitate the comparison of weighted graphs.

Figure 4 .

 4 Figure 4. Details of the selected edge weight encoding in matrices (left) and node-link diagrams (right) using superimposition.

1 .

 1 Matrix-Overlaid (M): A single adjacency matrix representation shows edge weights in both graphs. Each matrix cell (12 × 12 pixels) contains an inner region encoding the weight of the edge in G 1 and an outer region encoding the weight of the edge in G 2 (Fig. 5(a)). The absolute weight is mapped to the color brightness for which we used a perceptually linear scaling. A cell with a light inner and dark outer regions indicates an edge with a high weight in G 1 and a low weight in G 2 . Vice versa, a cell with a dark inner and a light outer region indicates an edge with a high weight in G 2 and a low weight in G 1 .

Figure 5 .

 5 Figure 5. Example from our controlled study: node-link and matrix representation of the same data (small, dense) for the region identification.

Figure 6 .

 6 Figure 6. (a) Mean accuracy in %, (b) and mean completion time in seconds per task for matrix (blue) and node-link (red) techniques. Error bars represent +/-2 standard errors.

Table 1 .

 1 Means of accuracy in percentages, the standard error is indicated in parentheses. Significant differences in accuracy are indicated by *. More accurate results are highlighted in bold.

		Matrix	Node-Link	p-value
	All tasks*	88.5 (0.9)	69.3 (2.0)	< .001
	Trend *	95.5 (1.2)	85.2 (4.3)	< .05
	Connectivity * 90.3 (1.0)	70.5 (2.5) < .0001
	Region *	79.6 (2.1)	52.3 (4.5) < .0001

Table 2 .

 2 Means of completion times (excluding errors) in seconds, the standard error is indicated in parentheses. Significant differences in completion time are indicated by *. Faster results are highlighted in bold.

		Matrix	Node-Link	p-value
	All tasks*	9.3 (0.3)	11.0 (0.4)	< .001
	Trend	7.1 (0.3)	8.2 (0.5) not significant
	Connectivity * 11.7 (0.5)	14.3 (0.7)	< .0001
	Region *	9.1 (0.5)	11.1 (0.7)	< .01

Table 3 .

 3 User preference (means of ratings from -2-strongly node-link, -1-somewhat node-link, 0-indifferent, 1-somewhat matrix, 2-strongly matrix), the standard error is indicated in parentheses. Significant differences in user preference are indicated by *. Large or Dense networks. The interaction Technique × Size (F (1,10) = 9.84, p < .01) is significant. Node-Link is particularly affected by Size. For Large datasets, the completion time increases by about 60% for Node-Link and 40% for Matrix. For Dense datasets, the completion time increases by about 25% for both techniques.

		Preference	p-value
	Overall*	1.25 (0.26)	< .0001
	Trend	0.63 (0.38) not significant
	Connectivity * 1.31 (0.23)	< .0001
	Region *	1.36 (0.21)	< .0001
	completion time increases for

ACKNOWLEDGEMENTS

We would like to thank Thomas Grabowski, Jr., MD, Dr. Tara Madhyashta, Dr. Kayo Inoue from The Integrated Brain Imaging Center (IBIC) at University of Washington, and to Dr. Arjun Bansal from Harvard Medical School for their valuable input that went into this work.


Manuel Atencia
email: manuel.atencia@inrialpes.fr

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

Giuseppe Pirrò
email: giuseppe.pirro@unibz.it

Alignment-Based Trust for Resource Finding in Semantic P2P Networks

In a semantic P2P network, peers use separate ontologies and rely on alignments between their ontologies for translating queries. Nonetheless, alignments may be limited -unsound or incomplete-and generate flawed translations, leading to unsatisfactory answers. In this paper we present a trust mechanism that can assist peers to select those in the network that are better suited to answer their queries. The trust that a peer has towards another peer depends on a specific query and represents the probability that the latter peer will provide a satisfactory answer. In order to compute trust, we exploit both alignments and peers' direct experience, and perform Bayesian inference. We have implemented our technique and conducted an evaluation. Experimental results showed that trust values converge as more queries are sent and answers received. Furthermore, the use of trust improves both precision and recall.

Introduction

Peer-to-peer (P2P) systems have received considerable attention because their underlying infrastructure is very appropriate for scalable and flexible distributed applications over Internet. In P2P systems, there is no centralised control or hierarchical organisation: each peer is equivalent in functionality and cooperates with other peers in order to solve a collective task. P2P systems have evolved from simple keyword-based file sharing systems such as Napster and Gnutella to semantic data management systems such as Edutella [START_REF] Nejdl | EDUTELLA: a P2P networking infrastructure based on RDF[END_REF], Piazza [START_REF] Halevy | Piazza: data management infrastructure for Semantic Web applications[END_REF] or SomeWhere [START_REF] Adjiman | Distributed reasoning in a peer-to-peer setting: application to the Semantic Web[END_REF].

In this paper, by a semantic P2P network we refer to a fully decentralised overlay network of people or machines (peers) sharing and searching for resources (documents, videos, photos, data, services) based on their semantic annotations using ontologies. In semantic P2P systems, every peer is free to organise her local resources as instances of classes of her own ontology serving as query interface for other peers. Alignments between ontologies make possible to reformulate queries from one local peer vocabulary to another. The result of a query is a set of resources (e.g., documents) which are instances of some classes corresponding, possibly via subsumption or equality, to the initial query posed to a specific peer.

Trust is widely acknowledged as a central factor when considering networks of autonomous interacting entities and notably in the context of the Semantic Web. When referring to the notion of trust, T. Berners-Lee advo cates for a user to be able to search for reasons why he or she should be confident of a returned answer [START_REF] Berners-Lee | Cleaning up the user interface[END_REF]. Trust is helpful to select, from a given set of peers, those that are expected to answer with most satisfactory instances. Peers may use this information for broadcasting their queries to a reduced set of peers and to have an approximation of the reliability of provided answers. Furthermore, peers may preventively send selected queries ino r d e rt oi m p r o v et h et r u s tt h e yh a v e towards another peer. Finally, by identifying "weak correspondences", peers may signal faulty alignments and trigger new matching of the ontologies.

Several proposals have been made that do not share the same meaning for trust [START_REF] Sabater | Review on computational trust and reputation models[END_REF][START_REF] Artz | A survey of trust in computer science and the Semantic Web[END_REF]. Many are user/agent/peer centred and rely on the assumption that all peers share similar implicit goals. Trust is then closely related to the notion of reputation in a community.

In contrast, in the context of semantic P2P systems, each peer may have her own view on how categorising the resources that are exchanged between peers. For this reason, we rather promote the computation of sub jective trust values based on direct experiences between peers. We also argue for a finer grained approach to trust in order to take into account the fact that, for answers provided by the same peer, the trust into these answers may vary according to which class they are instance of within the peer ontology.

An Illustrative Scenario

Consider a semantic P2P system for exchanging bookmarks, in which a peer Alice organises her bookmarks according to two main categories: FavouriteMusic and GoodRestaurants.T h e s ei nt u r na r ed i v i d e di n t os u b c a t e g o r i e s :Jazz , PopRock and Folk for FavouriteMusic ,a n dItalian and Chinese for GoodRestaurants. Within the Semantic Web, this can be implemented as a lightweight ontology that can be expressed in RDFS, in which categories and subcategories correspond to classes and subclasses, and the URLs identifying bookmarks correspond to URIs declared as instances of some classes.

Suppose that Alice is acquainted with Bob and Chris with whom she shares some interests in music and restaurants. This is captured by correspondences between her ontology and Bob's and Chris's ontologies. If Bob organises his best-of songs according to his favourite singers (e.g.,t h ec l a s s e sMichaelJackson and LouisArmstrong are declared as subclasses of BestSongs in his ontology), the following correspondence expresses that any URL bookmarked by Bob as an instance of his class MichaelJackson can be bookmarked by Alice as an instance of her own class PopRock : 1 Bob : MichaelJackson Alice : PopRock 1 We make use of the notation P : A for identifying a class A of peer P 's ontology.

An alignment between two peer ontologies is a set of correspondences between some classes used by these peers. Figure 1 shows the ontologies and alignments between Alice's, Bob's and Chris's ontologies. It must be seen as a (small) part of a semantic P2P system that can be queried for resource finding. Suppose Alice wants to get bookmarks from her acquaintances in the network to enrich her bookmarks about Italian restaurants. The alignments between her ontology and Bob's and Chris's ontologies allow to reformulate her initial query about Italian restaurants into the query Pizzeria asked to Bob,a n dTrattoria asked to Chris.A sh i sa n s w e rs e t ,Bob will return to her the set of instances in the extension of his class Pizzeria,andChris the set of instances in the extension of his class Trattoria .

Alice notices that Chris has some bookmarks in common with her, and thus tends to trust Chris for providing her with instances that fits well with her taste in terms of Italian restaurants. Subsequently, she may be inclined to add new bookmarks in her class Italian when they come from Chris .

However, although she trusts Chris for restaurants, she may not trust him for his musical tastes. For instance, for getting new bookmarks about Jazz ,s h e can discover by choosing a sample of the set of URLs returned by Chris as the extension of his class BluesMusic that very few corresponding music files fit well with her taste in terms of Jazz music. For music, she will later tend not to trust Chris and will prefer to query Bob on this topic.

Contributions

In this paper we propose a probabilistic model to handle trust in a semantic P2P setting. We define the trust of a peer P towards another peer P regarding a class C (belonging to P 's ontology) as the probability that an instance returned by P as an answer to the query asking for instances of C is satisfactory for P .In order to compute trust, we exploit the information provided by peers' ontologies and alignments, along with the information that comes from direct experience. Trust values are refined over time as more queries are sent and answers received.

We have designed an exp erimental proto col to study the convergence of trust, and to measure the gain of using trust for resource finding in practice.

Finally, a by-product of our trust model is a probabilistic setting for resource finding, in which the instances returned as answer for a given query are associated with a probability. This is in line with the recent trends towards probabilistic databases [START_REF] Dalvi | Query evaluation on probabilistic databases[END_REF].

The paper is organised as follows. The background of our work is presented firstly. Then we introduce the notion of probabilistic populated ontology and the definition of trust. Later we explain the computation of trust and update of probabilistic populated ontologies. We discuss experimental results, and finally give some concluding remarks.

2P r e l i m i n a r i e s

In this section the components of a semantic peer-to-peer network are presented: populated ontologies, alignments and acquaintance graphs. The kind of queries that we take into accounti sa l s od e s c r i be d .

Ontologies and Populated Ontologies

We draw a distinction b etween the ontological structure and the instances used to populate it. We deal with lightweight ontologies: classes linked by means of a less-general-than relation and a disjointness relation.

1. if c d then ext(c) ⊆ ext(d),a n d 2. if c ⊥ d then ext(c) ∩ ext(d)=∅.

Alignments

In an open and dynamic environment as a P2P network, the assumption of peers sharing the same ontology is not realistic. But if peers fall back on different ontologies, there must be a way to connect ontologies and translate queries so that their addressees are able to process them. Typically this is done by means of alignments -sets of correspondences between semantically related ontological entities-and finding alignments is what ontology matching is aimed at (see [START_REF] Euzenat | Ontology matching[END_REF]). Ac o r r e s p o n d e n c eb e t w e e nt w oc l a s s e sc and c of two ontologies O and O , respectively, is usually defined as a tuple c, c ,r with r ∈{ , =, , ⊥},w h e r e c c (or c, c , )i sr e a d" c is less general than c ", c = c is read "c is equal to c ", c c is read "c is more general than c ", and c ⊥ c is read "c is disjoint from c ". Here, however, we deal with a more general notion of a correspondence inspired from [START_REF] Euzenat | Algebras of ontology alignment relations[END_REF]. In such correspondences, a class is connected to another through a set of base relations to be thought of as an exclusive disjunction. For instance, c{>, <}c (i.e., c, c , {>, <} )isread"eitherc is more general than c or less general than c ". In this way, we can express uncertainty with regard to the alignment relation. Note that the relations ' 'a n d' 'c a nbes e e na sa b b r e v i a t i o n sf o r{=,>} and {=,<},respectively .Secondly ,anonstandardsymbol' 'isintroduced.Itreflects the idea of overlapping: classes the extensions of which share some instances but no one is equal to or contained into the other. Finally, c Γ c states total uncertainty about the relation between c and c .

According to Definition 3, an alignment may include correspondences that link the same two classes through different relations, or no one connecting two particular classes. However, one would like alignments to relate any pair of classes and to do it in one way. If there exists no correspondence between c and c in an alignment A,w ec a ns i m p l ya d d c, c , Γ .I f c, c ,R , c, c ,S ∈Awith R = S,w ecanrep l acebot hw i t h c, c ,R∩ S .T h i sf ol l o w st h ei n t e rp re t at i onof alignments as a set of correspondences which all hold. The resulting alignment is said to be normalised.

Definition 4. Let A be an alignment between two ontologies O and O .T h e normalisation of A is the alignment

A made up of all correspondences c, c ,R with c ∈ C, c ∈ C and R = R A (c, c ) where R A (c, c )={S : c, c ,S ∈A }. The alignment A is said to be normalised providing A = A. Remark 1. Recall that if R A (c, c )=∅ then R A (c, c )=Γ.
All alignments considered in this work are assumed to be normalised.

Peers and Acquaintance Graphs

We consider a finite set P = {P i } n i=1 of peers. In this work, P i will be identified by i.W ea s s u m et h a te a c hp e e rP i is associated with one populated ontology

O i = O i ,I i ,ext i (where 1 ≤ i ≤ n).
An acquaintance graph stands for peers' acquaintances (or neighbours) in the network. As usual, a link between two peers reflects the fact that they know the existence of each other. In addition, we assume that there exists one alignment between their respective ontologies. Definition 5. An acquaintance graph is a labelled directed graph P, acq where

P = {P i } n
i=1 is the set of vertices and any edge in acq is of the form i, j with i = j,a n di ti sl a b e l l e dw i t ha na l i g n m e n tA ij between ontologies O i and O j . Moreover, if i, j ∈acq then j, i ∈acq and A ji is the inverse of A ij . 2Peer P j is said to be an acquaintance of peer P i if i, j ∈acq.T h es e to f acquaintances of P i is denoted by acq(P i ).

Remark 2. Note that, given two ontologies O and O ,w ec a na l w a y sc o n s i d e r the trivial alignment, that is, the one that is made up of all correspondences c, c , Γ with c ∈ C and c ∈ C .

Queries and Query Translations

Peers pose queries to obtain information concerning other peers' populated ontologies. We deal with a simple query language, as peers can only request class instances: if peer P j is an acquaintance of peer P i ,s h em a yb ea s k e d

Q = c(X)? (1)
by P i with c ∈ O i .N o w ,s i n c ew ed on o ta s s u m et h a ta l lp e e r ss h a r et h es a m e ontology, queries may require to be translated for their recipients to be able to process them. Query translations are determined by correspondences of the alignments of the network. Specifically, if peer P i wants to send Q to P j ,s h ew i l lfi r s tc h o o s e one correspondence c, d, R ∈A ij (typically R is equal to '=' or '>') and then send P j the translation

Q = d(X)? (2)
The answer to (1) through its translation (2) is the set of instances of class d in P j 's populated ontology. Unlike queries, we assume that no translation of instances is ever required. Since alignments may be unsound and incomplete, this answer may contain unsatisfactory instances, i.e.,i n s t a n c e sw h i c ha r en o t considered instances of c by P i .

Ap e e rc a n n o tf o r e s e ew h e t h e rt h ea n s w er that another peer provides to one of her queries contains satisfactory instances or not, but this uncertainty can be estimated with the help of a trust mechanism.

3T h e T r u s t M e c h a n i s m

As mentioned above we look at trust as a way to estimate the proportion of satisfactory instances in a peer answer. The notion of satisfactory instance can be faithfully captured by an ideal populated ontology O * i that corresponds to ah y p o t h e t i c a ls i t u a t i o ni nw h i c hp e e rP i classified all instances of the network according to her ontology O i .InthiswaywecanexpressthefactthatP i considers an arbitrary instance a as an instance of c ∈ O i by a ∈ ext * i (c). It is assumed that

O i = O * i and ext i (c) ⊆ ext * i (c)f o re v e r yc l a s sc ∈ C i .
T h i sp o p u l a t e do n t o l o g y is referred to as the reference populated ontology of peer P i .

If peer P i receives a set B as an answer to the query (2), the proportion of satisfactory instances is given by the conditional probability p(ext * i (c)|B). The probability space under consideration here is the triple (Ω, A,p(•)) where Ω is the set of instances of the network (a finite set), the σ-algebra A is the power set of Ω, and p(•)i sL a p l a c e ' sd e fi n i t i o no fp r o b a b i l i t y .O u ra p p r o a c hf o rt r u s ta i m sa t finding approximations to these conditional probabilities. Before the definition of trust we introduce the notion of a probabilistic populated ontology.

Probabilistic Populated Ontologies

Once an answer is received, it can be (partly) added or not to the extension of the queried class. In order to capture the evolution of class extensions in the network, we consider a time variable t ∈ N,a n dw ew i l lw r i t eO t i to denote peer P i 's populated ontology at instant t (beginning with O i ):

O i = O 0 i , O 1 i ,...,O t i ,... (3)
We assume that the underlying ontology never changes, i.e., O i = O t i (t ∈ N), and that the sequence of class extensions {ext t i (c)} t∈N is monotonically increasing for all c ∈ C i .

Nonetheless, since we deal with probabilities new instances may not be 100% satisfactory. For this reason, at t ∈ N,p e e rP i is associated with a probabilistic populated ontology. Definition 6. Peer P i 's probabilistic populated ontology at time t is a triple

O t i = O i ,I t i , ext t i
where I t i is a set of instances and ext t i is a function that maps each class c of O i with its probabilistic extension

ext t i (c)= A * , F with F = { A k , [p k ,q k ] } k∈K where • A * is a (possibly empty) subset of ext * i (c

),t h a ti s ,as e to fi n s t a n c e sw h i c h are certain to be instances of the class c,a n da l l

• A k are pairwise disjoint subsets of I t i which are also disjoint from A * ,a n d all [p k ,q k ] are distinct subintervals of the unit interval [0, 1],w h e r ek ∈ K and K is a (possibly empty) index set of integers. Furthermore, the tuple O t i = O i ,I t i ,ext t i with ext t i (c)=A * k∈K A k must be ap o p u l a t e do n t o l o g y( s ot h a tt h ea x i o m st h a tr e l a t ec l a s s e sw i t ht h e i re x t e n s i o n s are fulfilled). The idea behind the interval [p k ,q k ] ⊆ [0, 1] is that there exists some statistical evidence for 3 The way probabilistic extensions are built is explained in Section 3.5.

p k ≤ p(ext * i (c)|A k ) ≤ q k .

Remark 3. Every populated ontology O i can be seen as a probabilistic populated ontology

O i = O i ,I i , ext i where ext i (c)={ ext i (c), ∅ } for all c ∈ C i .
Peers build probabilistic populated ontologies as more queries are sent and answered (starting with the "probabilistic version" of O i ):

O i = O 0 i , O 1 i ,..., O t i ,... (4)
And what was said about (3) at the beginning of this section holds for the underlying populated ontologies of (4).

Definition of Trust

With the new terminology, P j 's answer to query (1) via its translation (2) at time t is the extension ext t j (d), and an arbitrary instance a ∈ ext t j (d)i sq u a l i fi e da s satisfactory provided that a ∈ ext * i (c). The proportion of satisfactory instances in ext t j (d)isgivenbytheconditionalprobabilityp(ext * i (c)|ext t j (d)). Our proposal is that the higher this value is, the more P i trusts P j . Definition 7. Let us consider two peers P i and P j (i = j) and two classes c and d of O i and O j ,r e s p e c t i v e l y .T h etrust that P i has towards P j with respect to the translation c, d at time t is the conditional probability p(ext * i (c)|ext t j (d)) and it is denoted by trust t (P i ,P j , c, d ).

This idea is slightly different from most of the existing approaches for trust. In our setting cheating is not directly addressed: unsatisfactory answers are seen as the result of peers' incapacity to understand each other. In addition, trust is dependent on translations: peers may be very trustworthy in regard with some translations but not with others. In the following section, we explain our approach for computing trust. It exploits the information provided by alignments and revises it with direct experience.

Computation of Trust

Our approach for trust aims at approximating trust t (P i ,P j , c, d )b yB a y e s i a n inference. A probability distribution T t (P i ,P j , c, d )representsP i 's belief about θ = p(ext * i (c)|ext t j (d)). If there is no direct experience, alignments are taken to construct prior beliefs. Answers are later used to revise these beliefs. As they can be of a size that cannot be processed manually, we propose to perform sampling with replacement in order to estimate then u m b e ro fs a t i s f a c t o r yi n s t a n c e s .W e work with beta distributions as they are typically used to describe the parameter of a binomial distribution.

No direct experience: alignment-based trust. If T t (P i ,P j , c, d )i sn o td e fi n e d (this is the case when, for instance, t =0),wefallbackonalignments.PeersP i and P j 's ontologies are linked through A ij .S i n c et h i sa l i g n m e n ti sn o r m a l i s e d then there exists a unique R ⊆ Γs u c ht h a t c, d, R ∈A ij .T h ei n t e n d i n g meaning of correspondences is

R = {=} iff ext * i (c)=ext * j (d) R = {>} iff ext * i (c) ⊃ ext * j (d) R = {<} iff ext * i (c) ⊂ ext * j (d) R = {⊥} iff ext * i (c) ∩ ext * j (d)=∅ R = { } iff none of the above holds Hence, provided that ext t j (d) ⊆ ext * j (d), if R is '=' or '>'t h e np(ext * i (c)|ext t j (d)) = 1 if R is '⊥'t h e np(ext * i (c)|ext t j (d)) = 0 if R is '<'o r' 't h e np(ext * i (c)|ext t j (d)) ∈ [0, 1]
In the general case, R is a set {r 1 ,...,r n }⊆Γ( w i t hn ≤ 5). If we assume that all relations in R are equiprobable, by the law of total probability, we have

trust t (P i ,P j , c, d ) ∈ [u, v]w i t hu = 1 n n k=1 a k v = 1 n n k=1 b k where [a k ,b k ]=[ 1 , 1] if r k is '=' or '>', [a k ,b k ]=[ 0 , 0] if r k is '⊥', and finally [a k ,b k ]=[0, 1] if r k is '<'o r' '( k =1,...,n).
The information above can be used to construct P i 's prior belief about the parameter θ = p(ext * i (c)|ext t j (d)) by means of a beta distribution Beta(α, β). If [u, v]=[ 0 , 1], we take the uniform distribution U [0, 1] = Beta(1, 1). If not, and u<v,w ee qu al[ u, v]with[µ -2σ, µ +2σ]andthenfindBeta(α, β)w h o s em e a n and deviation are µ and σ.T h i si st h es t an d ardw a yt ofi n dacon fi d e n c ei n t e rv al based on the normal distribution. If u = v,weproceedwithσ =0.005 and µ = u unless u =1andu =0,inwhic hcasesµ =0.99 and µ =0.01, respectively. 4 In this way, we define the trust distribution T t (P i ,P j , c, d )=Beta(α, β).

Direct experience.

Trust at time t is used to choose a peer to which to send a query, as well as a class through which to translate it. This is explained in detail in Section 3.4. Let us imagine that P i receives B = ext t j (d). A sampling with replacement is performed over B in order to estimate the number of satisfactory instances. Let S ⊆ B be a sample (strictly speaking, S is a multiset). We assume that every peer can call an oracle (typically the user) to find out whether an instance is satisfactory or not. More specifically, given a ∈ S, P i 's oracle provides ay e s / n or e s p o n s et ot h eq u e s t i o n :" a ∈ ext * i (c)?". Even this, nonetheless, may be a high burden for P i 's oracle. We can benefit from peers' populated ontologies to process some instances automatically without the need to call oracles. Recall that P i is associated with a probabilistic populated ontology O t i ,a n dt h a tt h e probabilistic extension of class c includes a set A * of instances which are certain to be instances of ext * i (c). So if a ∈ B ∩ A * , a ∈ ext * i (c). We can also identify unsatisfactory instances automatically: if a ∈ S is such that there exists c in O i with c ⊥ c and a ∈ A * then a/ ∈ ext * i (c). The remaining instances are processed by peer P i 's oracle.

Assume that T t (P i ,P j , c, d )=B e t a ( α, β). If s is the sample size, s + is the number of successes (satisfactory instances), and s -= ss + is the number of failures, peer P i 's posterior belief about θ = p(ext * i (c)|ext t j (d)) is summarised in Beta(α + s + ,β+ s -). Thus we define T t+1 (P i ,P j , c, d )=Beta(α + s + ,β+ s -)( 5 )

Use of Trust

Imagine that peer P i wants to query c(X)? (c ∈ C i )a tt i m et ∈ N.T h e nP i chooses an element from the set P 0 = { P j ,d j : P j ∈ acq(P i )a n dd j ∈ O j } so that, if P j0 ,d j0 is the preferred tuple, P i will send d j0 (X)? to P j0 .T h i s choice depends on trust:

P i opts for P j0 ,d j0 iff E(T t (P i ,P j0 , c, d j0 )) = max Pj ,dj ∈P0 {E(T t (P i ,P j , c, d j ))}
where E(•)d e n o t e st h ee x p e c t e dv a lue of a distribution.

Updating Probabilistic Populated Ontologies

In the end, trust is used for class extensions to be increased with new satisfactory instances. If peer P i receives B = ext t j (d)asananswerto"c(X)?" then B will be (partly) added to ext t i (c). In line with the computation of trust based on direct experience (see Section 3.3), the set B is partitioned into three subsets:

B = B + aut B - aut B aut • B + aut = {a ∈ B : a ∈ ext t i (c)} = B ∩ ext t i (c) • B - aut = {a ∈ B :thereexistsc ∈ O i with a ∈ ext t i (c )a n dc ⊥ c } • B aut = {a ∈ B : a/ ∈ B + aut and a/ ∈ B - aut } = B \ (B + aut B - aut ) The set B +
aut contains the instances in B that already belong to ext t i (c), and B - aut comprises those instances that, if added to ext t i (c), would yield to a logical inconsistency. The set B aut embodies the new information that can be included in ext t i (c). 6 Since the answer B was received as the result of a comparison of trust values, it seems reasonable to add all instances of B aut to ext t i (c). The fact that these instances may not be 100% satisfactory, though, should be reflected in P i 's populated ontology. As described in Section 3.1, probabilistic populated ontologies are designed for this purpose.

The set B aut will be included in ext t i (c)alongwithanin terv al[ p, q]su c ht h at p ≤ p(ext * i (c)|B aut ) ≤ q on the basis of statistical evidence. Again, we propose to perform Bayesian inference, but, instead of weighing more on P i 's oracle, we lean on the previous sampling and make use of the formula

p(ext * i (c),B aut |ext t j (d)) = p(ext * i (c)|B aut ) • p(B aut |ext t j (d)) (6)
Let us explain this in detail. The probability p(B aut |ext t j (d)) represents the proportion of instances of B aut in ext t j (d)a n di t sc o m p u t a t i o ni ss t r a i g h t f o r w a r d . By monotonicity, we have

0 ≤ p(ext * i (c),B aut |ext t j (d)) ≤ p(B aut |ext t j (d))
In order to compute a prior about ϑ = p(ext * i (c),B aut |ext t j (d)), we proceed as the computation of alignment-based trust (Section 3.3): we equate the interval [u, v], where u =0andv = p(B aut |ext t j (d)), with [µ -2σ, µ +2σ], and then find Beta(α, β)w h o s em e a na n dd e v i a t i o na r eµ and σ,r e s p e c t i v e l y .Ap o s t e r i o ri s computed with the same sampling S used for Equation 5, but this time we count as a success any satisfactory instance that also belongs to B aut .

Let Beta(α ,β )b et h er e s u l t i n gp o s t e r i o r ,a n dl e tµ and σ be its mean and deviation. The set B aut is included in ext t i (c)alongwiththein t erv al[ p, q]where

p = 1 p(B aut |ext t j (d)) (µ -2σ ) q = 1 p(B aut |ext t j (d)) (µ +2σ )
Hence, p ≤ p(ext * i (c)|B aut ) ≤ q with 95% probability, which is based on the normal approximation to the posterior density for ϑ and Equation 6. Actually, if S + denotes the set of satisfactory instances in the sample S, B aut is partitioned into B aut ∩ S + and B aut \ S + ,w h i c ha r ea d d e dt oext t i (c)s e p a r a t e l y .T h u s[ p, q] must be resized accordingly, and then replaced by another interval [p ,q ]. Below we explain explicitly how probabilistic populated ontologies are built.

As remarked in Section 3.1, O 0 i is defined as the probabilistic version of P i 's initial populated ontology O i ,t h a ti s ,

• O 0 i = O i ,a n d • at time t ∈ N,i f ext t i (c)= A * , F then we define ext t+1 i (c)= A * (B aut ∩ S + ), F B aut \ S + , [p ,q ]
In order for O t+1 i to be a probabilistic populated ontology, though, B aut must be included in the extension of any superclass c of c.F o rt h es a k eo fs p a c e ,w e give a brief explanation of how this is done. Notice first that no instance in B aut belongs to the extension of a class disjoint from c as B - aut ∩ B aut = ∅ and c is a subclass of c .A l li n s t a n c e si nB aut ∩ S + are certainly instances of c since ext * i (c) ⊆ ext * i (c ). Instead of B aut \ S + we include B aut \ (S + ∪ ext t i (c )) as some instances of B aut \ S + may already belong to ext t i (c ). In order to find an interval with which to estimate p(ext * i (c )|B aut \ (S + ∪ ext t i (c ))), we proceed as before to approximate p(ext * i (c)|B aut \ (S + ∪ ext t i (c ))) and then apply the monotonicity of probability. In this way, the upper bound that we obtain is equal to 1.

By construction, O t+1 i is a probabilistic populated ontology.

4E x p e r i m e n t a l A n a l y s i s

This section reports on a preliminary experimental campaign that has been conducted to test the viability of the trust mechanism described in this paper. We set out to answer two research questions:

1. Do trust values converge as more queries are sent and answers received? 2. Is there any gain in query-answering performance -measured in precision and recall-by using the trust technique?

In what follows we first describe the experimental setting and then explain the execution and evaluation.

Experimental Setting

The trust mechanism presented in this work has been implemented in a simulator written in Java. The simulator also deals with aspects indirectly related to trust, such as generation of P2P networks, populated ontologies and alignments. In the remainder of the section we elaborate more on these aspects.

P2P network topology. Social networks are well-known to exhibit small-world characteristics [START_REF] Watts | Networks, dynamics, and the small-world phenomenon[END_REF]. For this reason, a small-world topology was used for the entire evaluation. To generate this topology, we ran Kleinberg's algorithm included in the JUNG Java library. 7 An o d ei nt h en e t w o r kr e p r e s e n t sap e e ra s s o c i a t e d with a populated ontology. The total number of peers in our evaluation was 20.

Populated ontologies. All populated ontologies in the evaluation had the same underlying ontology O i = O.M o r es p e c i fi c a l l y ,w ec h o s et h eo n t o l o g i c a ls c h e m e described in [START_REF] Lorenz | Ontology of transportation networks[END_REF] (with 64 classes). The semantic heterogeneity was reproduced by the way classes were populated with instances. The simulator implements an ontology population module which was utilised for both reference populated ontologies O * i and initial populated ontologies O i = O 0 i .First,asetS of abstract instances is generated. In our evaluation, the size of S was 6000. Second, for each peer P i ,asampleS i is taken from S.F urthermore,thissamplingisperformedin aw a ythatS i and S j overlap for each pair i, j.Thesizeofeac hS i is determined with a Zipfian distribution, which is often used to approximate data in physical and social sciences [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]. The skewing factor considered was 0.5. Third, the top class of O * i is populated with S i and a top-down population process is carried out by removing instances randomly for the remainder of classes. During this process, we check that all ontological axioms -subclass and disjoint relationsare fulfilled. Initial populated ontologies are generated in a similar way, starting this time with a sample of S i instead of S to populate the top class in O i .

Alignment generation. Ac o n n e c t i o nb e t w e e np e e r sP i and P j in the network (edge between nodes) is labelled with an alignment A ij between their respective ontologies. This is seen as a declined version of a reference alignment A * ij which is never available to the peers. Thus we cancapturetherealpracticeofon tology matching. Reference alignments are built by comparing class extensions in the reference populated ontologies (for instance, c<dis included in

A * ij iff ext * i (c) ⊂ ext * j (d)).
To build initial alignments, correspondences in reference alignments are discarded or replaced randomly in accord with global values for precision and recall. In our evaluation, we chose 0.6 for both measures.

Execution and Evaluation

From all p eers and classes in the network we chose a subset P 0 ⊆P of 15 peers and a subset C 0 ⊆ C of 25 classes randomly and ran 100 simulations. At each round n ≤ 100 of the execution, a peer P i ∈P 0 and a class c ∈ C 0 are randomly chosen. Then an acquaintance P j of P i and a class d ∈ C j are selected by using the trust mechanism (Section 3.4). Notice that C i = C j = C as we chose a single ontological scheme O.T op r o c e s sa n s w e r s ,t h em a x i m u mn u m b e ro fo r a c l ec a l l s allowed was 40. The subset B aut ⊆ ext t j (d)i si n c l u d e di np e e rP i 's probabilistic populated ontology if the expected value E(T n (P i ,P j , c, d )) is greater than a given threshold. In our evaluation, this threshold was 0.6.

In order to test the convergence of trust, we analysed the difference ∆ n = |E(T n (P i ,P j , c, d ))p(ext * i (c)|ext * j (d))| over the 10 most occurred queries. Figure 3 shows the experimentation results. After a number of rounds, ∆ n approached 0. Actually, in most of the cases, no more than 5 rounds were needed for ∆ n to be close to 0.1. In order to test the gain in query-answering performance, we compared the use of the trust mechanism with a naive strategy. In the latter, peers randomly choose acquaintances and always accept their answers. For the evaluation to be fair, the same set of queries was used in both strategies. This time we analysed precision and recall measured by 4 depicts the average precision and recall over the 100 rounds for the 20 most occurred queries. As expected, the naive strategy produced lower values for both measures. Furthermore, the use of the trust mechanism ensured high precision. However, this was not the case for recall. The reasonisthatpeersonly ask their neighbours, and these ones never change. As instances are spread all over the network, many instances may be unaccessible to peers. It is expected that if instances were more accessible, recall would be higher, but this remains to be experimented. The theoretical model presented in this paper is general enough to cover the case where peers receive answers from non-neighbour peers. Regarding the experimentation, we aim to perform a thorough experimental analysis concerning different network configurations in terms of number of peers, instances and oracle calls. Moreover, we want to investigate the relation between the quality of alignments and the speed of convergence of trust values.

Precision (n)= |ext * i (c) ∩ ext n i (c)| |ext n i (c)| Recall (n)= |ext * i (c) ∩ ext n i (c)| |ext * i (c)| Figure

Fig. 1 .

 1 Fig. 1. Three semantic peers in a P2P semantic network

Definition 3 .

 3 Let O and O be two ontologies, and let c and c be two classes of O and O ,r e s p e c t i v e l y .Acorrespondence between c and c is a tuple c, c ,R with R ∈ 2 Γ where Γ is the set {=,>,<, , ⊥}.A n alignment A between O and O is a set of correspondences between classes of O and O .

  Ap r o b a b i l i s t i ce x t e n s i o n ext t i (c)c a nb es e e na sac l a s s i c a le x t e n s i o next t i (c) partitioned into a number of subsets A * ,A 1 ,...,A n . All instances of A * are sure to be instances of the class c and then p(ext * i (c)|A * )=1 .H o w e v e r ,t h e set A k (1 ≤ k ≤ n)m a yc o n t a i ni n s t a n c e st h a ta r ea c t u a l l yn o ti n s t a n c e so fc.

Example 1 .

 1 If R = {<, =} then [u, v]=[.5, 1]. If we make [.5, 1] = [µ-2σ, µ+2σ] then µ = .75 and σ = .125. This leads to Beta(8.25, 2.75) whose shape is depicted in Figure 2(a).

Figure 2 Fig. 2 .

 22 Fig. 2. Beta distributions for different correspondences

Fig. 3 .

 3 Fig. 3. Test of convergence of trust

Fig. 4 .

 4 Fig. 4. Comparison between the use of trust and the naive strategy

Given an alignment A between O and O ,t h ei n v e r s eo fA is the alignment A -1 = { c ,c,R -1 : c, c ,R ∈A}between O and O,w he r eR -1 = {r -1 : r ∈ R} and r -1 is '>'a n d' <'i fr is '<'a n d' >', respectively, and r -1 = r otherwise.

The use of intervals follows Lukasiewicz's notation for conditional constraints in probabilistic knowledge bases[START_REF] Lukasiewicz | Managing uncertainty and vagueness in description logics for the Semantic Web[END_REF].

The values for α and β can be found by solving µ = α α+β and σ = µ(µ-1) α+β+1 .

Although cΓd stands for total uncertainty about the relation between c and d,t h e mean of its associated beta distribution, Beta(0.4, 0.8), is not 0.5b u t0 .6. However, our aim is not to find out the correct relation between c and d,b u tt oe s t i m a t et h e probability p(ext * i (c)|ext t j (d)). In this sense, total uncertainty arises with c<d, c d or c{<, }d, which are all modelled with a uniform distribution (whose mean is 0.5).

The subscript "aut" stands for "automatic", as both instances from B + aut and B - aut can be automatically processed, whereas this is not the case for B aut .

http://jung.sourceforge.net

Acknowledgements. This work is supported under the Dataring project, which is sponsored by the Agence Nationale de Recherche (ANR-08-VERS-007), and the Webdam project, sponsored by the European Research Council (FP7-226513).

5C o n c l u d i n g R e m a r k s

We have prop osed a trust mechanism in semantic P2P systems. The trust that ape e rh a st o w a r d sa n o t h e rpe e rd e pe n d so nas pe c i fi cq u e r ya n dr e p r e s e n t st h e probability that the latter will provide a satisfactory answer. In order to compute trust, we exploit alignments and peers' direct experience, and perform Bayesian inference. Preliminary experimental results show that trust values converge as more queries are sent and answers received, and that there is a gain in queryanswering precision and recall when peers make use of the trust mechanism.

The notion of probabilistic populated ontology has been introduced. This is a by-product of trust computation that allows to store and process the instances obtained from query answers in the same way as it is done in probabilistic databases [START_REF] Dalvi | Query evaluation on probabilistic databases[END_REF]. More precisely, a probabilistic populated ontology can be seen as aprobabilisticdatabaseinwhicheachfactC(i)isassociatedwitha(lowerbound of) probability. As a result, query answers can be ranked, and only top-k answers can be returned to interested users. In addition, since trust evolves over time as more queries are spread over the network and their answers are processed and stored with their probabilities, the resulting probabilistic populated ontologies somehow capture and compile the results of a trust propagation.

Many different probabilistic approaches to trust can be found in the literature [START_REF] Schillo | Using trust for detecting deceitful agents in artificial societies[END_REF][START_REF] Mui | Ratings in distributed systems: a bayesian approach[END_REF]. Some also perform Bayesian inference over feedback on past interactions. However, to the best of our knowledge, our model is the only one which explicitly benefits from ontological content and alignments.

EigenTrust [START_REF] Kamvar | The EigenTrust algorithm for reputation management in P2P networks[END_REF] is a peer-to-peer algorithm which, like ours, has a direct trust computation. Direct trust is then propagated among peers and aggregated to calculate global trust which can be very costly. As remarked above, we avoid this computation by exploiting the information on global trust stored and compiled in the probabilistic populated ontologies of acquaintance peers.

As future work, we plan to extend our trust model in order to deal with more expressive ontology and query languages. Although witness peers are not considered in this paper, the use of witness information is another future research line. Witness peers can help to find new trustworthy acquaintances. In this way, recall values can increase. Furthermore, the impact of malicious peers that hide or bias information, or lie, will be studied too.