Daniel Archambault

Structural Differences Between Two Graphs through Hierarchies

Keywords: H, 5, 0 [Information Systems]: Information Interfaces and Presentation-General G, 2, 2 [Mathematics of Computing]: Discrete Mathematics-Graph Algorithms

This paper presents a technique for visualizing the differences between two graphs. The technique assumes that a unique labeling of the nodes for each graph is available, where if a pair of labels match, they correspond to the same node in both graphs. Such labeling often exists in many application areas: IP addresses in computer networks, namespaces, class names, and function names in software engineering, to name a few. As many areas of the graph may be the same in both graphs, we visualize large areas of difference through a graph hierarchy. We introduce a path-preserving coarsening technique for degree one nodes of the same classification. We also introduce a path-preserving coarsening technique based on betweenness centrality that is able to illustrate major differences between two graphs.

INTRODUCTION

A difference map is a single graph G diff = (N diff , E diff ) constructed from the union of two input graphs G 1 = (N 1 , E 1 ) and G 2 = (N 2 , E 2 ). This graph encodes all of the differences between the node and edge sets of G 1 and G 2 . Figure 1 shows an example.

If the one-to-one correspondence between the nodes of the graphs needs to be computed, the problem is equivalent to subgraph isomorphism which is known to be NP-complete [START_REF] Cook | The complexity of theorem-proving procedures[END_REF]. However, if N 1 and N 2 have a labeling, such that a node in G 1 is the same as a node in G 2 , if and only if, their labels are equal, then computing a difference map can be done efficiently. Such graphs exist in practice, especially in the area of dynamic graph drawing. For example, in a computer network, where nodes are servers and edges are connections between those servers, each server has a unique IP address. These IP addresses can be used to determine correspondences between the nodes and edges of G 1 and G 2 which are snapshots of the network at two different dates, demonstrating how the network evolved during that time.

In previous work, animation has been used to show how nodes and edges are added and removed from the graph. If a node is the same in both graphs, its position in the layout is preserved as much as possible and an animation is used to transform G 1 into G 2 . This preservation of the mental map is highly dependent on user task and requires compromises with accepted graph drawing aesthetics [START_REF] Purchase | How important is the "mental map"? -an empirical investigation of a dynamic graph layout algorithm[END_REF]. An alternative to animation would be to present the differences between G 1 and G 2 in a single drawing. In this drawing, less emphasis would need to be placed on mental map preservation, allowing additional computational resources to be placed on graph drawing aesthetics. A small multiples approach could then be used to demonstrate how the graph evolves over time. Small multiples is an information visualization technique that places several images side-by-side in a sequence. * e-mail: daniel.archambault@inria.fr These difference maps can be very large, possibly on the order of twice the number of nodes and edges in the two input graphs. As these sets can be on the order of tens of thousands of edges, a direct drawing of the difference map suffers from high computational cost and extensive visual clutter. It may be advantageous to consider abstracting away areas of the difference map with similar meaning. In the field of information visualization and graph drawing, graph hierarchies or cluster trees have been used for this purpose. A graph hierarchy, or hierarchy, is defined as a recursive grouping placed on the nodes in this graph. Metanodes are the interior nodes of this hierarchy that contain a subset of nodes and a subset of the edges between those nodes. Leaves are the original nodes of the graph. A hierarchy is path-preserving if any path in a graph hierarchy level corresponds to one or more paths in the underlying difference map. The two conditions for a path-preserving hierarchy are: the subgraph contained in each metanode is connected and an edge between two metanodes must represent at least one edge in the underlying graph [START_REF] Archambault | GrouseFlocks: Steerable exploration of graph hierarchy space[END_REF]. In this work, metanodes store areas of graph difference, providing the user with an overview of the areas that are common to both G 1 and G 2 or present in only one of these graphs.

The primary contribution of this paper is a method for visualizing the differences between two graphs using a difference map and a graph hierarchy. Using a graph hierarchy allows a difference map to scale to larger graphs, as areas of the graph that the user is not interested in are abstracted away, reducing visual complexity. Our hierarchy creation technique takes into account edges as well as nodes to illustrate both differences. We introduce two path-preserving coarsening techniques. The first technique coarsens away nodes of degree one, while the second coarsens the graph by the magnitude of the change in betweenness centrality of each node. Betweenness centrality is a measure of the number of shortest paths in which the node participates, and, is in a way, a measure of the importance of the node in the graph. Finally, although we defined the properties for a graph hierarchy to be path-preserving elsewhere [START_REF] Archambault | GrouseFlocks: Steerable exploration of graph hierarchy space[END_REF], in this work, we extend the definition of path-preserving to allow nodes of degree one connected to the same node to be coarsened together inside metanodes.

PREVIOUS AND RELATED WORK

We categorize related work into two sections. Section 2.1 presents work on dynamic graph drawing. Although our technique is only able to present the differences between two time steps, small mul-tiples could be used to show how the graph evolves. Section 2.2 presents hierarchy-based graph visualization techniques. We use one of these techniques in order for the visualization of the difference map to be tractable.

Dynamic Graph Drawing

The field of dynamic graph drawing conveys evolving graphs over time. The problem can be either offline, where the full sequence of graphs is known ahead of time or online, where the sequence is not known in advance. Our approach would work best in an offline scenario, where all the time steps are available ahead of time.

In offline dynamic graph drawing, Diehl and Görg [START_REF] Diehl | Graphs, they are a changing -dynamic graph drawing for a sequence of graphs[END_REF] considered the problem of general dynamic graph drawing by using what they term a supergraph which encodes all graphs of the time sequence. Using the supergraph and temporal equivalence classes, they give several layout adjustment strategies in order to update the graph layout between time steps. Erten et al. [START_REF] Erten | GraphAEL: Graph animations with evolving layouts[END_REF] applies a forcedirected algorithm to this supergraph as a preprocess in order to derive animations. The work of Brandes et al. [START_REF] Brandes | Dyanmic sprectral layout of small worlds[END_REF] focuses on creating smooth animations between several graphs in a sequence using spectral graph drawing techniques. An animation sequence which dynamically adds or removes elements from a graph hierarchy is presented in Kumar and Garland [START_REF] Kumar | Visual exploration of complex timevarying graphs[END_REF].

Online dynamic graph drawing started with a restricted set of graphs, mainly directed acyclic graphs drawn in a hierarchical manner [START_REF] North | Incremental layout in dynaDAG[END_REF]. General graphs were considered by Brandes and Wagner [START_REF] Brandes | A bayesian paradigm for dynamic graph layout[END_REF] where a Bayesian approach, in combination with forcedirected techniques, is applied. Some work on drawing orthogonal and hierarchical graphs has been undertaken by Görg et al. [START_REF] Görg | Dynamic graph drawing of sequences of orthogonal and hierarchical graphs[END_REF] as well as force-directed methods with weighting functions to evolve the network dynamically while preserving the mental map [START_REF] Frishman | Dynamic drawing of clustered graphs[END_REF][START_REF] Frishman | Online dynamic graph drawing[END_REF]. Boitmanis et al. [START_REF] Boitmanis | Visualizing internet evolution on the autonomous systems level[END_REF] describe a way to show animations of the evolving Internet. In their approach, trees are removed and drawn with radial clustergrams and the remaining network is drawn using a variant of stress majorization which encourages position stability of nodes between frames of the graph animation.

In all of these systems, animation is used to display graph evolution. There exists some evidence that small multiples may be more accurate than animation for the discovery of trends in evolving data [START_REF] Robertson | Effectiveness of animation in trend visualization[END_REF]. We are not aware of any experiment run with users to see if this idea extends to dynamic graphs, but it may. Therefore, methods that can be adapted to a small multiples approach for dynamic graph visualization, such as the approach presented here, should be considered more closely.

One could view our approach as applying graph hierarchy techniques to the supergraph of Diehl and Görg [START_REF] Diehl | Graphs, they are a changing -dynamic graph drawing for a sequence of graphs[END_REF]. However, our technique operates over a pair of time steps rather all of them.

Hierarchy-Based Graph Visualization

Various techniques exist for visualizing a graph with a superimposed hierarchy including: visualizing the graph and associated hierarchy extruded into the third dimension [START_REF] Eades | Multilevel visualization of clustered graphs[END_REF], multi-focal fisheye approaches where metanodes are expanded and viewed in the context of the entire graph [START_REF] Schaffer | Navigating hierarchically clustered networks through fisheye and full-zoom methods[END_REF], topological fisheyes where abstract versions of the graph are presented far away from a focus centre [START_REF] Gansner | Topological fisheye views for visualizing large graphs[END_REF], and interactively visualizing hierarchies of small world clusterings [START_REF] Van Ham | Interactive visualization of small world graphs[END_REF]. However, all of these techniques require a full layout of the difference map to be computed before visualization of the differences can begin. This full layout is computationally expensive, since our graph sizes are large.

Techniques also exist to draw portions of the graph hierarchy on demand as the user explores the graph [START_REF] Abello | ASK-GraphView: A large scale graph visualization system[END_REF][START_REF] Di Giacomo | Graph visualization techniques for web clustering engines[END_REF][START_REF] Archambault | GrouseFlocks: Steerable exploration of graph hierarchy space[END_REF]. They have the principle advantage that the entire graph does not need to be drawn beforehand. We build on the work described in GrouseFlocks [START_REF] Archambault | GrouseFlocks: Steerable exploration of graph hierarchy space[END_REF] to draw and create our graph hierarchies. However, unlike Grouse-Flocks, in this work, we take into consideration the edges of the graph in order to illustrate both node and edge difference.

VISUALIZATION APPROACH

In our approach, we visualize the difference map directly using a hierarchy-based graph visualization technique. As input, the algorithm takes two graphs G 1 and G 2 . The nodes of G 1 and G 2 have unique labellings L 1 and L 2 such that if an element of G 1 and an element of G 2 have the same label, they correspond to the same nodes in both graphs. The approach is broken down into two main stages:

1. Compute the difference map from G 1 and G 2 using L 1 and L 2 . The output of this stage is the difference map G diff with a labeling M, indicating the differences between G 1 and G 2 .

2. Using G diff and M, decompose the difference into connected components where all nodes have the same M label and all edges have the same M label.

The first stage, which is computed as a preprocessing step, is discussed in section 3.1. After the computation of the difference map, the visualization of the difference map using hierarchy-based techniques is discussed in section 3.2. The two-level hierarchy uses metanodes to indicate areas of difference in a high-level overview.

Difference Map Computation

The structural differences between the two graphs G 1 and G 2 are computed based on a pair of unique labellings, L 1 and L 2 on the nodes of the graph. In this first part of the algorithm, we construct a new graph G diff and an output labeling of the nodes and edges, M, that encodes the similarities and differences between G 1 and G 2 . Many dynamic graph drawing algorithms compute all or parts of this graph. The algorithm is not a contribution, but rather it is described for completeness.

The first part of the algorithm inserts all the nodes of N 1 into G diff and labels them as only belonging to G 1 . The nodes are also inserted into a hash table by label. In the second part of the algorithm, the nodes of N 2 are traversed. The algorithm checks to see if the label exists in the hash table. If it does, the node is in both graphs and is labeled as such. If not, the node is inserted into G diff and is labeled as only belonging to G 2 .

Edge differences are determined by discovering if the two adjacent nodes in one graph are adjacent in the other. These differences are computed by scanning the edge lists of G 1 and G 2 separately. For each edge of G 1 , the algorithm inserts the edge into G diff and labels it as being in G 1 only. The edge is also inserted into a hash table. Once completed, the algorithm scans all the edges of G 2 . If either of the nodes belong only to G 2 , it is impossible for the edge to exist in both graphs, because one of its adjacent nodes does not exist in both graphs. Therefore, we label the edge as coming from G 2 and insert it into the graph G diff . If the two nodes are in both graphs, there are three possibilities. The first is that the edge is in G 1 only, in which case we inserted the edge in the scan of E 1 and labeled it as such. The second case is that the edge is in both graphs. The algorithm checks the hash table to see if the edge exists, and, if it does, the edge is labeled as belonging to both graphs. Otherwise, the edge is added and is labeled as only belonging to G 2 .

If adjacency is encoded using hash tables, the difference map can be computed in O(N + E) time where

N = |N 1 | + |N 2 | and E = |E 1 | + |E 2 |.

Hierarchy-Based Visualization of the Difference Map

The difference map can be as large as the sum of the sizes of G 1 and G 2 . As either G 1 or G 2 can be tens of thousands of nodes and edges [START_REF] Boitmanis | Visualizing internet evolution on the autonomous systems level[END_REF], visual clutter can be a problem. We, therefore, use graph hierarchies to visualize the structural differences between the graphs.

Our visualization technique uses the labeling M to simplify G diff into areas of difference between the two graphs. First, it is important to note that if a node is present in G 1 only, then all adjacent edges to that node must be in G 1 only because the two adjacent nodes of an edge need to both be present for the edge to exist. The same is true for nodes present only in G 2 . Therefore, a Grouse-Flocks [START_REF] Archambault | GrouseFlocks: Steerable exploration of graph hierarchy space[END_REF] decomposition on the nodes when the nodes appear in one graph or the other is sufficient. However, for edges whose adjacent nodes present in both graphs, the edge could be present only in G 1 , only in G 2 , or in both graphs. To address this case, we needed to develop a decomposition technique that takes an edge labeling into account.

Our approach, shown in Figure 2, starts by decomposing the graph into connected clusters of edges with the same M label. If a node belongs to multiple clusters of connected edges in the decomposition, it is duplicated. The clusters of connected edges are subsequently subdivided into clusters of connected nodes with the same M label. First, every node that was duplicated at least once, is placed into its own cluster. Subsequently, each connected set of edges is divided into connected sets of nodes of the same M label. For example, the large connected set of light grey edges is subdivided into six clusters in Figure 2. The nodes E, G, and F exist in their own clusters, because they are in more than one edge cluster. The node N is in its own cluster, because it exists in both graphs and is adjacent only to nodes existing in one graph. Finally, the node D and the nodes H, I, and J are in separate clusters because they are not connected by at least one edge. The result of this algorithm is a path-preserving hierarchy as all subgraphs contained in each metanode are connected and edges will be placed between metanodes if they exist in the difference map.

COARSENING DEGREE ONE NODES

GrouseFlocks [START_REF] Archambault | GrouseFlocks: Steerable exploration of graph hierarchy space[END_REF] introduced our definition of a path-preserving hierarchy. The definition in this work required that an edge exists between two metanodes, m 1 and m 2 , if and only if, at least one leaf in m 1 and one leaf in m 2 are connected by an edge. Secondly, the definition required that the subgraph contained at each metanode is connected. In this paper, we extend this definition of pathpreserving to allow disconnected subgraphs inside a metanode as long as it respects the following condition:

• The subgraph contained in a metanode of a path-preserving hierarchy can be disconnected only if every node in the subgraph is degree one and is connected to the same node s in the hierarchy. As all nodes in these metanodes are degree one, no path will ever enter and then exit this metanode in mid-sequence. Therefore, this hierarchy is path-preserving. The coarsening technique can be viewed as clustering the beginnings and endings of paths together.

A path can only begin or end at a node of degree one. As a result, the subgraph contained inside this type of metanode does not need to be connected, because paths do not pass through the metanode. We can view this metanode as a collection of path sources or sinks connected to s in the graph.

In this work, we also restrict the degree one nodes to have the same value in the labeling M computed in Section 3.1. The approach scans every node in the hierarchy once and merges all nodes of degree one that have the same M labeling together into a single metanode. The resultant difference map is simpler for graphs with degree one nodes as shown in Figure 3.

BETWEENNESS CENTRALITY COARSENING

Coarsening using the algorithm presented in Section 4 may generate a hierarchy that still contains too many areas of difference. The resultant graph is often large, difficult to read, and is computationally expensive to draw. In this case, our approach adapts by allowing only the major differences in graph structure to be shown.

Betweenness centrality [START_REF] Freeman | A set of measures of centrality based upon betweeness[END_REF] is a measure of how often a node lies on shortest paths in the graph. These nodes are often structurally important as they appear on many short, and presumably well used, communication paths. For a node v it's betweenness centrality is computed as follows:

BC(v) = ∑ u =v =w σ (u,w) (v)
where σ (u,w) (v) is the number of shortest paths that contains the node v. We do not normalize our betweenness centrality by the number of paths that exist in the graph. Fast algorithms exist to compute the betweenness centrality of all elements of a graph of |N| nodes and |E| edges in O(|N||E|) time [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF]. Edge filtering techniques based on betweenness centrality have been used for the visualization of social networks, most recently in Jia et al. [START_REF] Jia | On the visualization of social and other scale free networks[END_REF], but not for coarsening a graph hierarchy of graph differences.

Using our approach, the algorithm computes the betweenness centrality for G 1 and G 2 independently before the difference map is computed. When computing the difference map, the absolute value of the difference in betweenness centrality is recorded for each node. For nodes present in only one graph, the value is set to its betweenness centrality in that graph. Low betweenness centrality differences indicate areas of the graph that are stable or of low structural importance. Thus, this metric attempts to emphasize important structural changes in the graph.

The algorithm selects nodes of low betweenness centrality difference and replaces each connected component of the induced subgraph by a single metanode. A node n is selected under three conditions:

1. n is a metanode that contains a subgraph that is identical in both graphs 2. n is not a metanode and has a betweenness centrality difference below a user specified threshold 3. n is not a metanode and appears in both graphs such that:

• all adjacent edges appear in both graphs • all adjacent nodes are below the betweenness centrality threshold

The first condition coarsens away large subgraphs that appear in both graphs contained in metanodes. The second condition coarsens away minor structural changes and areas of stable structure. Nodes with a low difference in betweenness centrality are considered less important by the metric or only had a minor change in structural significance. The third condition coarsens away minor edge changes: sets of edges that appear in both graphs have at least one node below the threshold. Note that any metanode containing a subgraph that appears in only one of the graphs is never coarsened away.

RESULTS

In order to test the technique, we ran our algorithm on three sequences of test data. For these results, we used a 3.6GHz Pentium IV with 1GB of RAM running Fedora Core 4. Timing numbers, along with graph and difference map sizes, are presented in Table 1.

The first dataset is the Threads2 graph sequence used in the work of Frishman and Tal [START_REF] Frishman | Online dynamic graph drawing[END_REF]. A movie 1 that shows the evolution of Threads2 is available from the second author's website for comparison. The dataset consists of evolving discussion threads. Nodes are users discussing a topic and an edge exists between two nodes if one user replied to the posting of the other. A special node, A n where n is a number, represents the root of a given topic thread.

The second dataset is two scans of the Opte 2 Internet mapping project. consists of two snapshots of a subset of major Internet servers taken on January 11th and January 15th, 2005, respectively. In this graph, nodes are servers and an edge in the graph exists if those servers exchange packets.

The third dataset is the Routeviews 3 dataset used in the work of Boitmanis et al. [START_REF] Boitmanis | Visualizing internet evolution on the autonomous systems level[END_REF]. A movie 4 that shows the full sequence of 1 www.ee.technion.ac.il/ ∼ ayellet/Movies/OnlineGD.mov 2 www.opte.org 3 www.routeviews.org 4 www.inf.uni-konstanz.de/algo/research/asgraph Routeviews evolving over time is available from the website of the research group. The datasets consist of two scans of the Internet at the autonomous system level, one taken in August 2005 and the other taken August 2006. Autonomous systems are typically groups of networks under the same administrative authority. In the graph, there is a node for each autonomous system and an edge between two nodes if the systems are connected.

To draw the resultant hierarchies, we use GrouseFlocks [START_REF] Archambault | GrouseFlocks: Steerable exploration of graph hierarchy space[END_REF]. GrouseFlocks uses algorithms to draw the graphs based on the topological features detected in the graph. Therefore, if the metanode contains a tree, a tree drawing algorithm is used. Threads2 uses the same set of drawing algorithms specified in the GrouseFlocks paper. However, Opte and Routeviews use the FM 3 [START_REF] Hachul | Drawing large graphs with a potential-fieldbased multilevel algorithm[END_REF] algorithm for subgraphs of unknown topological structure. We use FM 3 , as this algorithm is fast and produces reasonable results for large general graphs. Even after the generation of a hierarchy and coarsening, the resultant graphs are still on the order of thousands to tens of thousands of nodes.

Threads2

In Threads2, we are trying to describe the evolution of a set of discussion threads. The results of our approach are shown in Fig- ure 4. Tan nodes are nodes that appeared in both graphs over the time step while purple nodes have just been added. Circular nodes contain subgraphs of the same difference value. Square nodes are the original nodes of the dataset. Neither form of coarsening was used on this small dataset. We notice immediately that there are no deletions from the dataset during the time steps as only two colours are used. Therefore, none of the messages were deleted during these scans. The figures also demonstrate reasonably well what was added in purple. Pinpointing exactly what changed may be harder to do with the video of the evolving graph mentioned above.

In Figure 4(a), we present the difference between time steps 10 and 11 of the dataset with no graph hierarchy. Differences are still coloured using the colour scheme above. In this small example, it is relatively easy to see the differences between time steps without a hierarchy. If the graphs were larger and substantially different, the task would require a more time consuming visual search to detect the differences. On the other hand, Figure 4(b) highlights these differences immediately. We can see that the new discussions were stimulated by the postings of Locutus465 and KaiserCSS. By using an interactive system, such as GrouseFlocks, we could interactively open these two metanodes to see which user responded to this discussion thread.

Figures 4(b) through 4(f) show the evolution of the graph over five time steps. The diagrams show how the discussion in the newsgroup evolves rather easily. In Figure 4(e), the drawing depicts the emergence of a new discussion topic A 5082. This topic was started by Gigahertz 19. In the next time step, this discussion is continued by Mazor. KristopherKubicki joins this disconnected discussion with the rest of the newsgroup by replying to at least one new post.

Opte

The Opte difference map encodes the differences between two Internet scans in 2005. The results are presented in Figure 5. Sections of the network that remained the same appear in tan, and new sections that were found on January 15 of 2005 appear in purple. Once again, no parts were deleted as no third colour needed to be used. Therefore, this network only grew.

In Figure 5(a), a FM 3 layout of the entire difference map is presented. General areas of difference are visible in purple, but it is hard to gauge the size of the differences and their locations. Figure 5(b) shows a hierarchy of the differences. The size of the node is mapped to the size of the subgraph. At the center of the diagram, there is a large component of the network that is identical. This fact is not immediately evident from the previous drawing.

Dataset

We can begin to see some areas of major growth in the upper right section of the diagram where a few large purple metanodes reside.

In Figure 5(c) these changes are still visible. The periphery of the drawing is improved by the degree one clustering, making some of these areas at the fringe of the diagram more visible. Figure 5(d) emphasizes the major edge changes, where major is defined as having a betweenness centrality difference above 600,000. Clutter is greatly reduced as most of the nodes that appeared in both graphs are now in the residing central component. The few edges, between nodes close to this large brown component, are edges adjacent to nodes with a major change in betweenness centrality.

Routeviews

Routeviews tests the limits of our approach. The difference map generated contains tens of thousands of nodes and contains about ten thousand more edges than either of the original datasets. This dataset has both removals and insertions. Once again, areas of the graph which are the same are illustrated in tan. Areas of growth in the graph appear in purple and areas of the graph that disappeared appear in teal. Result images are shown in Figure 6. Figures 6(a) and 6(b) do not clearly demonstrate the changes in the the graph structure between these two dates. Other than noticing that many of the teal nodes and edges have been placed into components of the hierarchy, we cannot see much, so we need to resort to coarsening. Figure 6(c) demonstrates some of the major differences in the graph structure. A few large areas of the graph that did not change are drawn in tan. There are some areas that were added and taken away in purple and teal, respectively. However, even with degree one coarsening, the changes in the graph are not well depicted. Once we coarsen away areas of the graph that have a betweenness centrality inferior to 2,000,000, as in Figure 6(d), the drawing does a more accurate job of depicting major areas of difference. There is a single large component of stable structure with a few nodes connected to it. A more rapidly changing part of the graph is visible in the lower left portion of the diagram. However, none of these drawings are very clear.

DISCUSSION

From the timings shown in Table 1, the only step which requires significant computational time is computing the betweenness centrality on the two input graphs. Currently, we use Brandes' al-gorithm [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF] to compute the betweenness centrality for each node. These times can be reduced by estimating the betweenness centrality at each node, using a technique, such as Jia et al. [START_REF] Jia | On the visualization of social and other scale free networks[END_REF], to approximate the value rather than to compute it exactly. Also, metrics and interfaces for selecting a good betweenness centrality threshold should be investigated further.

The difference map approach is best suited for a small multiples approach to graph visualization. A small multiples approach places several images side-by-side in a sequence rather than showing the sequence as an animation. In our work, we would place the hierarchically-decomposed difference maps in a matrix. This approach has the advantage that a user can view all the data at once, but the disadvantage is that all these images require significant space as seen from the size and quantity of images in this paper.

The main advantage of our approach is that it targets the core of dynamic graph visualization: depicting what exactly has changed. Through difference maps, hierarchy generation, and the coarsening techniques presented here, our work depicts differences using spatial position and colour. We think that these differences are easier to notice when depicted in this way, rather than by using animation. However, a user experiment is required to support this hypothesis.

FUTURE WORK AND CONCLUSIONS

We plan to run a user study which will hopefully support the hypothesis that the presented difference maps outperform animation when the user would like to discover structural changes in graphs. Such an experiment would also attempt to determine if hierarchy construction on top of the difference map helps users understand how a graph evolves over time.

Currently, our approach does not place metanodes which contain similar graph elements into similar areas of the plane. As spatial position is an important visual cue, ensuring that similar parts of the graph are in similar locations would improve our technique.

It may be an interesting area of future work to illustrate changes in attribute values associated with the nodes and edges of the graph. As an example, in computer networks, an attribute could encode the amount of network traffic passing through an edge between two servers.

In this paper, we have presented a method for visualizing the structural differences between two graphs. Using a graph hierarchy allows the approach to scale, as large areas of the graph that are the same are abstracted away, reducing visual complexity. Our hierarchy creation technique takes into account edges as well as nodes to illustrate both differences. We introduce two path-preserving coarsening techniques and modify the definition of path-preserving.

Figure 1 :

 1 Figure 1: Example of a difference map between two small example graphs G 1 and G 2 based on the labeling shown in all three subfigures. (a) The input graph G 1 . (b) The input graph G 2 . (c) The difference map of G 1 and G 2 . In this figure, black nodes and edges only appear in G 1 , light grey nodes and edges only appear in G 2 , and the dark grey nodes and edges appear in both G 1 and G 2 .

Figure 2 :

 2 Figure 2: Steps to creating the hierarchy encoding the node and edge differences in the graph. (a) The original difference map with node and edges existing only in the first graph in black, nodes and edges existing only in the second graph in light grey, and nodes and edges existing in both graphs in dark grey. (b) Decomposition of the graph by edge difference value. The graph is divided into connected sets of edges of the same type. Nodes belonging to more than one edge set are duplicated. (c) Each connected set of edges is further clustered by node difference value. Notice the node N is clustered out of its connected edge set because it appears in both graphs whereas all the other nodes appear only in the second graph. All the nodes participating in more than one edge cluster are placed in their own cluster. (d) Final drawing of the hierarchy. Metanodes abstract the graph into clusters where every node has the same difference value and every edge has the same difference value.

Figure 3 :

 3 Figure3: Coarsening technique that merges degree one metanodes of the hierarchy together. (a) Nodes of the hierarchy are not grouped together, causing a very bushy tree out on the periphery. (b) Nodes of the hierarchy are grouped into metanodes according to their M labeling. As all nodes in these metanodes are degree one, no path will ever enter and then exit this metanode in mid-sequence. Therefore, this hierarchy is path-preserving. The coarsening technique can be viewed as clustering the beginnings and endings of paths together.

Figure 4 :

 4 Figure 4: Figure showing the evolution of the graph sequence Threads2. (a) The difference between graphs 10 and 11 in the sequence drawn without a hierarchy. (b) -(f) Hierarchies demonstrating the differences between a pair of consecutive time steps. Nodes in the graph that appear in both time steps appear in tan. Nodes that have just been added over the last time step appear in purple. Circular nodes contain connected subgraphs of the same difference value and square nodes are nodes of the dataset.

Figure 6 :

 6 Figure 6: Figure showing differences between two Routviews snapshots taken on August 1st of 2005 and 2006 respectively. Nodes and edges that were the same in both graphs are in tan. Nodes added are in purple and nodes removed are in blue. (a) Graph without any hierarchy or coarsening drawn with FM 3 . (b) Graph with hierarchy but no coarsening. (c) Graph with hierarchy and degree one coarsening. (d) Graph with degree one and betweenness centrality coarsening. The brown nodes are the components that have a relatively stable or small betweenness centrality. Black edges connect these coarsened components to the rest of the graph. A betweenness centrality threshold of 2,000,000 was used to generate the betweenness centrality coarsened hierarchy.

Table 1 :

 1 Size of datasets used in the results and timings for the stages of the creation of the difference map and hierarchy. The Graph 1 and Graph 2 columns list the size of the two input graphs in number of nodes and edges. The Difference Map column contains the size of the difference map in number of nodes and edges and the time required to compute the difference map in seconds. The B. Centrality column lists the time required to compute the betweenness centrality of each input graph in seconds The Hierarchy column contains the size of the hierarchy graph in number of nodes and edges and the time required to compute the hierarchy in seconds. No next to the dataset name indicates no coarsening. A 1 indicates degree one coarsening. B. indicates both degree one and betweenness centrality coarsening were executed. Betweenness centrality thresholds of 600,000 and 2,000,000 were used for Opte and Routeviews, respectively. The numbers next to Threads2 indicate the two graphs in the sequence used to create the difference map.

		Graph 1	Graph 2	Difference Map	B. Centrality		Hierarchy
		N	E	N	E	N	E	sec.	sec.	sec.	N	E	sec.
	Threads2 10 -11	62	72	66	76	66	76	0.01	0.02	0.02	4	4	0.14
	Threads2 11 -12	66	76	69	80	69	80	0.01	0.02	0.02	12	12	0.22
	Threads2 12 -13	69	80	70	83	70	83	0.01	0.02	0.02	10	12	0.20
	Threads2 13 -14	70	83	72	87	72	87	0.01	0.02	0.02	10	11	0.24
	Threads2 14 -15	72	87	75	91	75	91	0.01	0.02	0.02	6	5	0.14
	Opte No	35,386 42,387	40,027 47,215	40,027 47,215 3.16	5,389 6,827	2,642	3,132	20
	Opte 1	35,386 42,387	40,027 47,215	40,027 47,215 3.16	5,389 6,827	1,970	2,460	18.91
	Opte B.	35,386 42,387	40,027 47,215	40,027 47,215 3.16	5,389 6,827	657	788	14.51
	Routeviews No	20,432 43,498	23,072 48,891	24,302 58,043 5.61	1,820 2,407	23,656 57,283 104.97
	Routeviews 1	20,432 43,498	23,072 48,891	24,302 58,043 5.61	1,820 2,407	19,372 52,999 117.32
	Routeviews B.	20,432 43,498	23,072 48,891	24,302 58,043 5.61	1,820 2,407	3,212	6,773	78.4

ACKNOWLEDGEMENTS

I would like to thank INRIA Bordeaux Sud Ouest Gravié project for support. I also acknowledge David Auber and Guy Melanc ¸on for many interesting discussions on this topic. Thank you Morgan Mathiaut, for helping shoot the figures in the results section. Finally, I would like to thank the anonymous reviewers of GI, as well as Julie, Mari, and David for their useful comments.


Camille Chaserant

MINIMAL GROUP IDENTITY AND GENDER IN ULTIMATUM GAMES

Keywords: JEL classification: C91, A12, C99 minimal group, ultimatum game, social identity, gender

Social identity, or group membership, affects economic outcomes. However, this influence may differ according to the nature of the groups involved. Investigating the weakest group cohesion necessary to influence individual behaviors, we undertook three linked ultimatum game experiments involving a minimal categorization process. Three main results are presented here: (i) Belonging to a minimal group affects behaviors; (ii) Men and women differ systematically in the nature of this influence and (iii) The 'label' given to a minimal group is in itself not neutral.

Introduction

Identity and economics

 Akerlof andKranton (2000, 2004)show that identity, or a person's sense of self, affects many economic outcomes such as poverty, gender discrimination in the labor market, the household division of labor or workers' motivation. Resting on the main insights of social identity theory [START_REF] Tajfel | The social identity theory of intergroup behaviour[END_REF], they propose to insert the person sense of self as an additional argument of individual utility functions. The idea is that traditional utility functions capture our personal characteristics, or the first level of the identity concept. However, several decades of research in social psychology showed that our identity strongly depends on our membership in social categories and groups and that this second level of identity has been rather neglected by economic analyses. Akerlof and Kranton thus incorporate social identity as a motivation for behavior beside the traditional economic motivations. Therefore, belonging to a group yields gains or losses in identity, mainly deriving from behaviors that conform to or departs from the norm of the group in a given situation. For example, following the prescriptions of our own gender category results in asserting our identity as a man or a woman as well as the identity of the men or women we are interacting with, thus generating gains in identity for everyone. However, a man wearing a dress threatens the identity of other men inducing losses in identity for them.

One of the more robust findings of social identity theory is indeed that an action initiated by a member of one's own group or social category (the ingroup) is evaluated quite differently from the same action initiated by a member of another group or category (the outgroup) [START_REF] Brewer | Intragroup bias in the minimal intergroup situation: a cognitivemotivational analysis[END_REF]. The related gains and losses in identity are therefore different although deriving from the same behavior and maximizing utility induces dissimilar reactions. Ingroup favoritism commonly occurs: we all share the tendency to evaluate our ingroup, its members or their actions more favorably than the outgroup, its members or actions (for a review, see [START_REF] Hewstone | Intergroup bias[END_REF]. A lot of experiments illustrate the influence of social identity on behaviors in strategic contexts. For example, in the investment game, [START_REF] Buchan | Let's get personal: an international examination of the influence of communication, culture and social distance on other regarding preferences[END_REF] find that American students exhibit an ingroup bias: they are more willing to trust other American students than students of other nationalities. On the contrary, Chinese students tend to favor the outgroup, and Japanese and Korean students behave in the same way regardless of their partner's nationality (on the same game, see also Carpenter and Camilo Cardenas, 2004). In the same vein, [START_REF] Ruffle | Cooperation and the in-group-out-group bias: A field test on Israeli kibbutz members and city residents[END_REF] observe that kibbutz members cooperate more with members of their own kibbutz than with city residents.

The object of our research is to determine the influence of social identity on behaviors in the ultimatum game2 . The experiment motivating our research had been conducted by [START_REF] Kramer | Why ultimatums fail. Social identity and moralistic aggression in coercitive bargaining[END_REF] (thereafter KSW). In a ultimatum game involving members of two rivals business schools, they find that Responders are more willing to accept an unfair offer made by an ingroup Proposer than the same offer made by someone from the outgroup. [START_REF] Kahneman | Fairness and the Assumptions of Economics[END_REF] observe similar behavior patterns with groups of students belonging to psychology classes. When they are informed that they are being paired with a student in commerce classes, psychology students make less generous offers and exhibit higher minimum acceptable offers than when they are paired with other psychology students. In the same way, in the experiment of Robert and Carneval (1997), Proposers will more often offer a fair share to a member of their own class than to a member of a different one. Considering gender, [START_REF] Eckel | Chivalry and Solidarity in Ultimatum Games[END_REF] find that women are more generous with men. All of these experiments illustrate the idea that gains or losses in identity are dissimilar (and often superior) in a ultimatum game if the Proposer and the Responder belong to the same social group than if they do not.

Real vs. Minimal groups

In theory, the absolute value of payoffs in identity may depend on the sense of belonging, or on the degree of identification with the group. If you feel deeply involved in a group or if you have strong ties with your ingroup members, you may more easily categorize situations by defining an "us" and a "them" and have discriminatory behaviors. Sense of belonging can be experimentally manipulated in several ways. For example, [START_REF] Charness | Individual behavior and group membership[END_REF] make the presence of the ingroup salient and shows that this affects behaviors in the Battle of Sexes and the Prisoner's Dilemma games. [START_REF] Solow | Group identity and gender in public goods experiments[END_REF], following [START_REF] Brown-Kruse | Gender effects in public goods contribution: do individuals put their money where their mouth is[END_REF], try to create a sense of community in some groups through pre-experiment activities. In the experiment of [START_REF] Kramer | The social context of negotiation: effects of social identity and interpersonal accountability on negotiator decision making[END_REF], some subjects are asked to list all of the ways in which they are unique or different from the others (low social identification condition), whereas some others have to list all the ways in which they are similar to the others (high social identification condition). We proceed differently here and operate on the distinction established in social identity theory between real and minimal groups. A real group is a group or a social category existing outside the lab, such as the business schools in the KSW experiment or the classes in Robert and Carneval (1997) or [START_REF] Kahneman | Fairness and the Assumptions of Economics[END_REF]. Introduced by [START_REF] Rabbie | The arousal of ingroup-outgroup bias by a chance win or loss[END_REF] and [START_REF] Tajfel | Social categorization and intergroup behaviour[END_REF] (thereafter TBBF), the minimal group paradigm rests, on the contrary, on an artificial and arbitrary social categorization created and used only during the experiment. For example, in the experiment of Rabbie et al. subjects are (randomly) assigned to a given group labeled as "blue" or to another group labeled as "green" supposedly "for administrative reasons". In TBBF, subjects are told that people with similar artistic preferences are associated to form two separate groups, although in reality the matching is random. A minimal group is therefore a random assignment of people who share none of the ties or goals of a group; in other words, they share nothing but a name or a label. Nevertheless, this label is enough to induce discriminatory behaviors. One of the fundamental findings of the minimal group paradigm is that the social categorization process in itself, i.e. the simple assignment of people to labels, induces them to act in favor of their ingroup members.

The study presented here originates from the following question: Will we find out that people are behaving in the same way as in the KSW experiment except with minimal groups? In a ultimatum game, do responders react differently to an offer if this offer is made by a Proposer with whom they only share a group label? In other words, we are trying to identify the minimum conditions necessary for social identity to influence strategic behaviors. This research clearly pursues the aim of Charness et al. (2005, p1) to begin "a systematic analysis of how groups affect individual behavior" in order "to provide a theory of how groups influence strategic behavior in economic contexts".

Using the idea of a minimal group in the strategic context of the experimental game theory requires to specify two important points:

(i) First, TBBF specified a set of criteria required for a group classification to be considered as minimal: (1) no face to face interaction, (2) group membership is completely anonymous; subjects do not know who is a member of which group, (3) no instrumental link between the group categorization and the nature of the task or of the response required to the subjects, (4) no difference across choices in the material payoffs for the chooser and (5) those choices should not be familiar but rather important to the subjects. Introducing minimal groups in an ultimatum game experiment clearly violates the condition (4). The choice of an amount to offer by the Proposer, and the choice of the Responder to either accept or reject it, directly impact on their own respective payoffs. If our experiment is not then a minimal-group experiment, we follow however exactly the same categorization manipulation as TBBF. This will allow us to observe if an artificial and arbitrary group membership induces enough group identification in order to check selfinterested individual behaviors. (ii)

Second, minimal group experiments involve a minor deception of the subjects who believe that they are grouped according to a criterion (for example their artistic preferences) when categorization is in fact random. To our knowledge, the only game experiment using such a minimal categorization is the one of Ball et al. (2001). They allocate high and low status to groups through two procedures that they call "random" and "awarded" status. In fact, status is allocated randomly in both procedures but the second one is designed in order to suggest to the subjects that the high status is deserved. The deception involved in our experiment seems even slighter given that groups are created through a perfectly symmetrical categorization process and that there is no status difference among them. As in Ball et al., therefore, this minor deception meets American Psychological Association guidelines3 and is of a degree common in other social science experiment.

We conducted our experiments in the following way: We first replicated the KSW experiment by adding a preliminary stage of minimal group categorization identical to that of TBBF. We did not find the same results as KSW, but observed behaviors that are definitely more complex: members of only one of the two groups are influenced by their social identity and their reactions are at the opposite of KSW observations (they more often rejected unfair offers from the ingroup).

We then conducted experiments involving a real ultimatum game using the decision method (as opposed to the manipulated experiment of KSW) with minimal groups in order to observe behaviors of Responders as well as of Proposers and to compare them according to the presence or the absence of minimal groups. We first found that behaviors of both Proposers and Responders in the experiment with minimal groups significantly differ from behaviors in a standard ultimatum game experiment. Belonging to a minimal social group social thus induces specific behaviors in ultimatums. Next, we observed that this minimal social identity differently affects behaviors according to the gender of the participants. Indeed, belonging to a group did not generate a similar identification for men and women. Both sexes in both roles had been affected by their minimal social identity. But, in each case, women and men behaved in a radically opposed way. These results underline the complexity of the links between personal and social identities.

The remainder of the paper is organized as follows: we review the experimental designs of KSW and TBBF before presenting our own experimental designs in Section 2. Our main results are presented and discussed, step by step, in Section 3. We conclude in Section 4. KSW (1995) sought to analyze the influence of the Proposer group membership on the Responder's behavior in an ultimatum game (noted UG). According to social identity theory, the Responders' most vehement reaction would be towards either: (i) An unfair offer made by an outgroup Proposer ("the outgroup derogation hypothesis"): As outgroup members are typically expected to be less fair than the ingroup members, the fact that they transgress the "fair rule" will generate a more violent reaction. (ii)

Ultimatum game and Minimal groups

The KSW experiment: An Ultimatum Game with Real Groups

An unfair offer made by a member of the ingroup ("the expectancy violation hypothesis"): As members of the same group are supposed to share the same values and thus to act cooperatively, Responders might therefore evaluate an unfair offer much more negatively when it comes from the ingroup.

Participants in the KSW experiment were 110 MBA students belonging to two rival American business schools. They were informed of the rules of the ultimatum game and the amount to be divided was fixed at $25. Although they believed interacting with other persons, experimenters actually predetermined offers in order to manipulate their perceived fairness. Indeed, all the students were assigned to the Responder role and were proposed either an equal split ($12.5), or an unfair offer ($7.5). They were also told whether the offer came from a member of their own business school (ingroup condition) or from a member of the other one (outgroup condition).

Behaviors confirmed the outgroup derogation hypothesis. Indeed, all the fair offers were accepted, regardless of the group membership of the Proposer. In contrast, the reactions to unfair offers were influenced by the Proposer's social identity: whereas 75% of the unfair offers from ingroup members had been accepted, only 43% of those from the outgroup were accepted. Thus, participants more strongly reacted to unfair offers from outgroup members in order to punish their discriminatory behaviors. Moreover, answers to questionnaires completed during the experiment showed that unfair offers made by the outgroup were systematically judged as "less fair", "more exploitative" and marginally "more selfish" than the same offers made by the ingroup, leading Responders to be "more irritated" and "less happy".

Students of a Business School thus regarded a priori those of the other School as being less fair and, when they received an unfair offer from them, they were frequently willing to reject it. As already underlined, a Business school is a real group, which exists apart from the lab. Students could then identify themselves more or less with their ingroup, or could feel concerned by their group membership in a way that was not controlled by the experiment. On the contrary, minimal group experiments yield situations devoid of the trappings of real ingroup membership.

2.2.The TBBF minimal groups experiment

The seminal paper in the minimal group paradigm is TBBF (1971). This study shows that social categorization, i.e. the distinction between an "us" and a "them", or between the ingroup and the outgroup, leads in itself to discriminatory intergroup behaviors.

In the first part, participants (young boys of a same school) were asked to express their aesthetic preference between "two foreign modern painters, Klee and Kandinsky" having been shown a pair of slides reproducing paintings by the two men with the respective signatures obscured. Once all of the answers had been collected, an experimenter was seen by the participants to be apparently compiling them. Participants were then divided in two groups, "the group preferring Klee" and "the group preferring Kandinsky". Actually, subjects' assignment to a group was not based on the answers provided but was rather random. Each subject was then isolated, shown various matrices of remunerations and requested to select a pair of rewards that would remunerate two other participants in the experiment: one belonging to their own group and one belonging to the other. Nobody could choose its own reward; each participant was thus paid at the end of the experiment according to choices made by others (condition (4) of the minimal categorization definition).

This experiment brought out three key results: (i) over 72% of the subjects made choices that favored the ingroup and discriminated against the outgroup -even though these groups had been constructed artificially; (ii) these discriminating behaviors were deliberate strategies -indeed, participants chose significantly more often to maximize the ingroup member's payoff than to maximize the joined gain of the two participants they had been asked to reward; (iii) lastly, participants prefered offering less to the ingroup provided that this choice maximizes the advantage of the ingroup relative to the outgroup. Therefore, not only did subjects discriminate in favor of an ingroup created in a random way, they also sought through their choices to affirm the superiority of their ingroup on the outgroup even if it is costly for the ingroup. As Tajfel et al. (p178) concluded: "in a situation in which the subjects' own interests were not involved in their decisions, in which alternative strategies were available that would maximize the total benefits to a group of boys who knew each other well, they acted in a way determined by an ad hoc intergroup categorization".

A ultimatum game with minimal groups: experimental design

Ingroup favoritism thus appears to be an ordinary behavioral strategy of most of people (i) in minimal group settings (ii) where material payoffs of the chooser are not involved (TBBF), as well as (iii) when they are members of real groups (iv) in a ultimatum game where their own payoffs are involved (KSW). What should happen if conditions (i) and (iv) are met? Our experimental design replicates, in a first stage, the first part of the experiment of TBBF. Subjects are separated in two groups, supposedly because of their aesthetic preferences. Then, in a second stage, they are asked to play a UG being informed of their partner's group membership.

Precisely, we proceeded the following way. During all the experiment, subjects were separated by dividers, ensuring that no one was aware of the identity (and the gender) of the rest of their group. Instructions were distributed in envelopes, so that the information contained in each envelope was private. After an aloud reading of the instructions, subjects could ask questions, and after all questions were answered, they were requested to complete a preliminary test of comprehension. Only one participant did not correctly answer the test, and the corresponding data has been dropped from the sample.

In the first part of the experiment, participants were requested to reveal their preference between pictures by two abstract painters, Gerard Schneider and Thibault de Reimpré. As in TBBF, they saw slides of their work with the signatures concealed and completed a form concerning them. Once the answers had been collected, an experimenter was seen to be apparently verifying them in order to separate those who preferred Schneider from those who preferred de Reimpré. In fact, we divided randomly the participants into the two groups, "the group preferring Schneider" (hereafter the S group) and "the group preferring de Reimpré" (the DR group).

Afterwards, subjects played a UG where the roles of Proposer and Responder had been randomly assigned. Proposers were requested to offer a split of €20, having been informed of their and the Responder's group membership. After receiving the offer, Responders had to either accept or refuse it. 4 At the end of the experiment, the subjects were paid according to their UG's outcome. No show up fee was paid.

Overall, we conducted twenty-seven experimental sessions with 226 subjects recruited by announcements during classes:

-In 6 sessions, we replicated during the second part of the experiment the double manipulation of KSW. All the subjects were assigned to the Responder role and received a pre-determinate offer, either €10 (equal split) or €6 (unfair offer). They were informed of the group membership of the assumed Proposer. -In 21 sessions, during the second part of the experiment, subjects really played a ultimatum game in which the Proposer and Responder roles were allocated randomly. Two parallel sessions allowed us to carry out between-subjects treatments. In the control one, subjects played a standard ultimatum game whereas in the other one, the first stage of minimal categorization was introduced. Finally, 19 sessions were devoted to the complete experimental design described above.

Table 1 summarizes the various sessions and the number of subjects.

Results

Reactions to expectancy violation

As just noted, six sessions consisted in adding a first stage of minimal social categorization to the 2×2 factorial design of KSW. We recruited 36 subjects, as many men as women, who were all assigned to the role of Responder and were equally divided between the two groups of painting lovers (see table 2). We observe that the decision whether to accept or to reject the offer does not depend on the in-or outgroup condition but rather on the group×role interaction considered 5 . S Responders (i.e. Responders belonging to the S group) are more willing to reject offers coming from their ingroup. They refuse four of the six unfair offers and one of the six fair offers from ingroup members. These behaviors significantly differ from those of the other subjects (p=0.02), especially from those of the other ingroup interaction, between Proposers and Responders both belonging to the DR group (p<0.01). DR Responders reject only one (unfair) offer, coming from the outgroup. Logically, the earnings of S members are the smallest of the sample since their payoffs are equal to zero in six ingroup interactions.

Table 2 2×2 between-subjects factorial design

From their answers to questionnaires, we observed that S members expected to be favored by their ingroup Proposers. Their mean expectation for the ingroup offer was €9.54, which is significantly higher than the €7.54 expected from the outgroup (p=0.02). Note that DR members also expected to receive a greater offer from the ingroup than from the outgroup (€8.58 against 7.54). Even if this last difference is not significant, it gives further evidence that to be favored by ingroup members is the implicit norm of behavior.

In short, if DR members do not discriminate between offers from the ingroup and from the outgroup, S members do make a clear distinction and reject the majority of the unfair offers coming from the ingroup. First, note that these two results contrast with the observations of KSW. On the one hand, members of only one group seem to take into account the source of the offer. On the other hand, by rejecting ingroup unfair offers, they rather react to expectancy violation than by outgroup derogation.

Second, given that the size of the sample is small, a pool bias may be possible in our experiment [START_REF] Ball | Subject pool choice and treatment effects in economic laboratory research[END_REF]. Nevertheless, our results may be interpreted in two other ways6 :

(1) The fact that members of only one group are influenced by the minimal categorization could simply indicate that minimal groups not that much affect individual behavior in a UG. If group membership often induces an ingroup favoritism, the ultimatum setting, where players' decisions directly affect their payoffs, stimulates withdrawal on personal identity and self-interested behaviors (a similar interpretation can be found in Robert and Carneval, 1997).

(2) The fact that S members react to expectancy violation whereas DR members do not and also KSW results favor the outgroup derogation hypothesis suggest that the way people react to unfair offers depend on the kind of group they belong to. Moreover, in our experiment, the "group preferring Schneider" and the "group preferring de Reimpré" are symmetrically created during the categorization stage. The only thing distinguishing between them is the name of the painter to which each one refers. This name in itself is probably far from neutral since the name of "Schneider" generates a group identification whereas the name of 'de Reimpré" does not.

Nevertheless, going further in the interpretation requires a replication of the experiment. However, we chose not to repeat exactly the last experimental design and rather to conduct sessions with a real play of the UG in the second part of the protocol. The idea was that, in addition to having a greater number of observations, we would be able to collect information not only on the Responders' behaviors but also on Proposers' offers.

Real ultimatum game: A first "between-subjects" analysis

We began the sessions with real UG by conducting two preliminary sessions with 36 students. Twelve of them played a standard ultimatum game, those six interactions being used as a control set. The others participated to a UG with minimal categorization. Six ingroup and six outgroup interactions took place, equally distributed between the 2×2 possible group interactions.

Not surprisingly, results of these preliminary sessions meet traditionally observed behaviors in UG experiments. Proposers offer on average €8.03 that is 40.15% of the €20 to be divided.

Only three offers are refused by Responders, two of them being lower than €5, and on average, participants win €9.67. Furthermore, as expected, we observe significant differences in participants' behaviors between the standard and the group version of the experiment (see Table 3). First, Proposers offer more, on average, in the standard UG than in the group version (p<0.05). Moreover, average offer in ingroup conditions is higher than in outgroup conditions (€7.92 against €6.67). Even if this difference is not statistically significant7 , it fits well with the ingroup bias traditionally observed in social psychology experiments. Always confirming an influence of group membership on participants' behaviors, we also note slight differences in the mean offers made by Proposers assigned to the DR and the S group, as well as in the average amount offered to Responders of the DR and the S group (p<0.1).

Real ultimatum game: the cross effects of gender and minimal groups

Provided with these initial results, we conducted 19 additional sessions in the course of which 152 university students took part (see table 4). We briefly present our main results about Proposers' offers and focus afterwards on Responders choices. Table 5 gives the main results by interaction and by gender.

The Proposers' offers

The mean offer is €7.88, or 39.4% of the initial amount. Offers do not significantly vary according to the Responders' or the Proposers' group membership neither do they depend on the group×role interaction as we had observed it before. Nevertheless, female Proposers behave significantly differently from male Proposers. Indeed, women more often offer a fair split than men do (p<0.01). They are 59.64% to propose a minimum share of €9.5 to the Responder, whereas only 24.24% of men do it.

We conducted an ANOVA test on the null hypothesis that there was no gender effect on Proposers' mean offers in each group×role interaction. The null hypothesis was rejected at the 95% level of confidence (p<0.1). Men do offer less on average than women do. Moreover, the mean offer of S male Proposers to S Responders was significantly lower than the remainder of the sample (that is lower than the offer of S female Proposers to their ingroup Responders and lower than the offer of the other participants of both sexes in every group×role interaction). This specificity of S male Proposers towards their ingroup partners does not appear in a first-level analysis because S female Proposers behave the exact opposed way: they make more unfair offers to DR Responders than to S Responders (or to the outgroup than to the ingroup).

The Responders' reactions

Both genders are sensitive to the Proposer's group membership

Overall, 81.7% of the offers are accepted. The thirteen rejected offers (on seventy-one) are unfair offers and more precisely offers under €8. As Proposers' offers, at a first-level analysis, the acceptance rate of Responders does not differ according to Proposers group membership or to group×role interaction. However, as Proposers' choices, the decisions of male and female Responders are clearly distinct according to the interaction. 81.7% * female responders receive more unfair offers from DR Proposers than from S Proposers (p<0.1) **male responders receive more unfair offers from S Proposers than from DR Proposers (p<0.1) Do Responders' behaviors favor the expectancy violation or the outgroup derogation hypothesis? Given that all the fair offers are accepted, we focus only on unfair offers. An offer is said to be unfair if it is below €88 . Analyzing acceptance decisions of unfair offers according to gender shows that both women and men are sensitive to the group membership of the Proposer. Globally, women are more willing to reject unfair offers of S than of DR Proposers (p<0.01). The effect of social identity is patent here given that women receive a greater number of unfair offers from DR Proposers (p=0.067). At the exact reverse, men are more willing to reject unfair offers of DR than of S Proposers (p<0.05) although they receive a greater number of unfair offers from the latter (p=0.016).

The interaction effects between gender, role and group membership are significant. Receiving an unfair offer, S female Responders are more willing to accept it if it is proposed by the outgroup (p<0.1), whereas DR female Responders accept it more easily if it is proposed by the ingroup (p=0.0167). In other words, only S female members behave following the expectancy violation hypothesis. On the contrary, the behaviors of DR female members more closely correspond to the outgroup derogation hypothesis. Male behaviors are not less clear-cut. When they belong to the DR group, they do not discriminate among offers according to the Proposer's group membership; they reject as many offers of the ingroup as of the outgroup. However, S male Responders accept significantly more unfair offers of the ingroup than of the outgroup (p<0.01).

In order to test whether the sexes are different in their willingness to accept unfair offers from Proposers belonging to both groups, we ran the following regression. The dependent variable is ACCUNF, equals to 1 if the Responder accepted an unfair offer, 0 otherwise. The reported results confirm the observed differences between men and women in their willingness to accept unfair offers according to Proposers' group membership. Individually, neither gender nor Proposer group membership affect Responders' acceptance rate. However, their interaction significantly influences Responders' decision. In other words, the influence of group membership depends on the gender of subjects. The positive coefficient for SEX×PROP_GP indicates that men are more likely than women to accept an unfair offer from a S Proposer than from a DR one.

Hypothetic vs. real choices

Table 5 above contains both real decisions of Responders whether to accept the offer and their hypothetical decisions deduced using the strategy method of [START_REF] Selten | Die Strategiemethode zur Erforschung des Eingeschänkt Rationalen Verhaltens im Rahmen eines Oligopolexperiments[END_REF]. Before receiving the offer, Responders were asked to state their minimum acceptable offer (MAO). The strategy method consists in inferring the Responder's decision by comparing the actual offer with this MAO. This method is often used in UG studies because offers lie most of the time around the equal split; they are then regularly accepted, and consequently, the data sets are not large enough in order to analyze the willingness of the Responders to accept unfair offers [START_REF] Camerer | Measuring Social Norms and Preferences Using Experimental Games: A Guide for Social Scientists[END_REF]). Yet, we observe that using the strategy method, acceptance rates are significantly lower than they are actually and especially for female Responders. If we were using the strategy method, rejects of unfair offers should have been largely overestimated. [START_REF] Blount | The inconsistent evaluation of absolute versus comparative payoffs in labor supply and bargaining[END_REF] also observed such a gap between real and hypothetical behaviors and explained it by the fact that a rating task (like stating MAOs) does not have an exact behavioral equivalent. Consequently, « It seems plausible that the rated acceptability of an option reflects its probability of being accepted in a take-or-leave-it decision, but this cannot be assumed » (Blount and Bazerman, 1996, p 229) A subject could truly think that under a certain amount an offer is so unfair that she will reject it. Yet, when she actually receives the unfair offer, the tradeoff between the willingness to punish the Proposer and the opportunity to have a low but positive payoff could lead her to accept it9 . Knowing the MAOs stated by the subjects is however interesting. We first observe that the gap between real and hypothetical decisions depends on the gender of the Responder (p<0.1). Women more often state MAOs higher than the offers actually accepted than men do. Moreover, MAOs differ according to the group×role interaction for both sexes. They are then precious information that allows us to reconstitute the timing of the game. Before, note that participants of both sexes belonging to the DR group behave regardless of the Proposer's group membership. Only S members exhibited specific behaviors.

(i) S female members stated lower MAOs when they were paired with an ingroup Proposer than when they were paired with an outgroup one (p=0.06).

Notwithstanding, they expected to be favored by the ingroup 10 . Well, they actually received a higher offer on average from the ingroup than from the outgroup (p<0.1) and especially less unfair offers. However, they rejected more unfair offers from the ingroup than from the outgroup. In other words, when they actually received an unfair offer, they reacted more strongly in ingroup than in outgroup interactions. Their expectations (rather than their MAO) shaped their decision. (ii)

Male S members also reported lower MAOs when they were paired with an ingroup Proposer than with an outgroup one. Then, they were more likely to accept unfair offers from the ingroup, although they expected to be favored by the ingroup. The designs of the offers received by male S Responders and of their reaction were at the exact opposite of women ones. They were actually not favored by the ingroup but by the outgroup. Indeed, DR Proposers made both higher offers in average and less unfair offers than S Proposers did to S male Responders (p<0.1). In spite of this, S male Responders ended by accepting the unfair offers from the ingroup and rejecting more often those coming from the outgroup. Either men are more willing to maximize monetary payoffs than women and this is why they finally accepted the unfair offers coming from the ingroup; or they are actually more indulgent with the ingroup than women are. However, they ex post reported to be "less satisfied" in ingroup than in outgroup interactions (p<0.5) and judged S Proposers "less fair" and "less generous" than DR Proposers (p<0.01).

Summary and conclusions

In summary, our between-subject treatment show that introducing minimal categorization in UG affects behaviors compared to a standard UG. Moreover, the manipulated as well as the non-manipulated experiments show that membership to minimal groups shapes behaviors of members (of only one group). Such results indicate that groups formed by nothing else than a random assignment of subjects to names affect individual behaviors. The effects of social identity are less straightforward and definitely more complex with minimal than with real groups, but they are palpable.

After the first experiment, we thought of a pooling bias possibility. It seems now that this eventuality should be left out since in all our treatments, behaviors of members of the S group systematically differed from those of the remainder of the sample. However, the question is: why did S group members have been the only ones influenced by their minimal social identity? The only explanation rests on the group's name itself (and not on the belief that categorized people share artistic preferences). In designing further experiments involving minimal categorization, experimenters should very carefully choose the names of the groups 11 .

Belonging to the S group did not generate a similar identification for men and women. Both sexes in both roles had been affected by their minimal social identity. But, in each case, 10 Pre-offer questionnaires distinguished questions about MAO from questions about expectations of the Responders, as you can see in the Appendix A.3. 11 In our experiment, the question becomes : why did the name of « Schneider » apparently elicite a sense of belonging whereas the name of « de Reimpré » did not? When we presented an earlier draft of this paper at the International Conference Morality, Norms and Economics (Lisbon, September 2004), it has been suggested that, in French language, « de Reimpré » is a name belonging to the nobility whereas « Schneider » is not (it is moreover a frequent name in the East of France). Behaviors of members of the S group could thus reflect a reaction to their « low-grade » group label. Nevertheless, it remains that men and women reacted differently to this group label.

women and men behaved in a radically opposed way. Female Proposers favored the ingroup whereas male Proposers favored the outgroup. Female responders reacted to an expectancy violation by rejecting more unfair offers from the ingroup whereas male Responders did not, but exhibit either outgroup derogation or monetary self-interested behaviors. This gender effect is not innocuous since at the end of the game, payoffs of male and female players (and payments of male and female subjects) were significantly different. Women earned more in ingroup interactions, especially when they were assigned to the Responder role (p<0.1). On the opposite, men earned more in outgroup interactions, especially when they were assigned to the Responder role (p<0.01).

Minimal categorization thus affects differently men and women behaviors. Such a result confirms those studies explicitly designed in order to observe gender differences and extend them in a framework with minimal categorization. For example, Brown-Kruse et Hummels (1993), who tried to create a sense of belonging to some groups through pre-experiment activities, observed that men who took part in those activities contributed more to the public good than those who did not, while there was no such effect for women. [START_REF] Solow | Group identity and gender in public goods experiments[END_REF] also fund complex cross-effects of gender and social identity in a public good game. We agree that the effects of gender and social identity (groups being minimal or real) need further investigations. In the current state of experimental research, their interaction is not enough to predict differences in behavior in bargaining games.

Table 1 Summary of experimental designs and number of subjects

 1

		Exp.1: 2×2 design	Exp. 2: Real UG	Exp. 3: Real UG with
		UG with minimal groups	Test between-subjects	minimal groups
	Subjects	48	36	142
	Females	24	6	77
	Males	24	30	74
	Role		18 proposers	71 proposers
		48 responders	18 responders	71 responders

Table 3 Overall results of the test sessions

 3

		Number of	Average offer	Acceptance rate
		interactions	(standard deviation)
	Overall	18	€8.03	83.3%
	Standard UG	6	€9.5 (1.76)	100%
	Group UG	12	€7.29 (2.14)	75%
	Ingroup conditions	6	€7.92 (2.11)	66.7% (2 refusals)
	Outgroup conditions	6	€6.67 (2.18)	83.3% (1 refusal)
	DR Proposers	6	€7.58 (1.86)	83.3%
	S Proposers	6	€7 (2.55)	66.7%
	DR Responders	6	€7.42 (2.54)	66.7%
	S Responders	6	€7.17 (1.91)	83.3%

Table 4 Experimental design and number of subjects

 4

	Role	Group	Females	Males
	Proposer	DR	14	17
		S	23	16
	Responder	DR	18	15
		S	22	16

Table 5 Summary statistics by interaction and gender Responder's gender

 5

	Interaction		Female*	Male**
	DR -DR	Mean offer	€7.33 (2.04)	€8.06 (2.21)
		Real acceptation	100%	77.78%
		Acceptation using SM	33.33%	66.67%
	DR -S	Mean offer	€6.9 (1.22)	€9.64 (1.44)
		Real acceptation	80%	85.71%
		Acceptation using SM	30%	85.71%
	S-DR	Mean offer	€7.25 (2.84)	€8.67 (1.78)
		Real acceptation	75%	83.33%
		Acceptation using SM	41.67%	66.67%
	S-S	Mean offer	€8.75 (2.73)	€6.22 (0.83)
		Real acceptation	91.67%	66.67%
		Acceptation using SM	66.67%	22.22%
	Overall	Average offer		€7.88
		Acceptation rate

Table 6 Logit regression results

 6

	Independent variables	Coefficient	Standard error	p-values
	Dependent variable: accunf
	Pay	0.013	0.08	0.87
	Sex	-0.38	0.307	0.21
	Prop_gp	0.025	0.307	0.93
	Sex*Prop_gp	1.022	0.315	0.0012
	Eco	0.15	0.299	0.607
	Age	-0.13	0.136	0.335
	Intercept	2.44	3.15	0.437
	N = 71
	R 2 = 0.2963
	Test of the null hypothesis rejected whatever the indicator may be (e.g. Likelihood ratio: 16.2962, p-value:
	0.0122, Score = 15.287, p-value: 0.0181)

E-mail address: camille.chaserant@u-paris10.fr, Fax: +33 1 40 97 71 83, Tel.: +33 1 40 97 47 66. The European Program NORMEC, "The Normative Dimension of Action and Order; for an inclusive Europe" (HPSE-CT-00081) provided research support for this project. Experiments had been partly conducted at the Supelec laboratory, supported by the Région Ile-de-France. I would like to thank Isabelle Bilon and Sophie Plumel for assistance. Earlier drafts have been presented at the International Conference "Morality, Norms and Economics" in Lisbon (September

2004) and at the IAREP SABE Congress in Paris (July 2006). Participants to conferences and especially Helena Lopes, Werner Güth and Luigi Marengo provided helpful comments. All errors fully remain the author's responsibility.

In this game, introduced by[START_REF] Güth | An experimental analysis of ultimatum bargaining[END_REF], two (anonymous) players must divide a given amount (say €20). The Proposer is instructed to make an offer ranging from zero to €20 to the Responder. The latter can either accept or reject this offer. If he accepts the offer, the €20 will be divided accordingly. If he rejects the offer, neither of them will receive anything.

See http://www.apa.org/ethics/code.html

Subjects were each asked to complete 2 questionnaires: Proposers had to complete one questionnaire after they had made their offers (in order to ascertain the degree to which they thought that their offer was likely to be accepted) and another after they had received the answer from the Responder (to guage their reaction) (the latter is given in Appendix A.2.). Responders were each asked to complete a questionnaire before receiving the offer from the Proposer (in order to ascertain their expectations) and another after they had given their response (to guage their reaction).

Data analysis and statistic treatments were carried out using SAS and Sphinx Lexica softwares. Probabilities in brackets are those of the t-test when the sample contains less than 30 data and the chi-deux test if its size is over. Results are then weakly significant when p<0.1 and strongly significant when p < 0.01.

We exclude that subjects perceived the manipulation of the offer and reacted accordingly. As we noted, dividers separated each subject ensuring that they could neither see nor talk to others and instructions were privately given to each one.

Only the difference between the outgroup condition and the standard one is significant (p<0.05).

Among unfair offers, the modal offer is €6, exactly the same amount that we used in the manipulated version of the experiment. Enlarging the definition of an unfair offer until reaching €8 allows to improve the size of the sample but do not modify our results.

In the same spirit,[START_REF] Boles | Accepting unfairness: Temporal influences on choice[END_REF] show that when unfair offers are accompagnied by actual currency (a $1 bill), they are more likely to be accepted than if they are received without any currency attached.


Bernard Courtois
email: bernard.courtois@imag.fr

SOC/SIP for energy management

Keywords: energy, power, CO 2, photovoltaics

This paper deals with how ICs and MEMS can address energy issues like the generation, the conversion, the use, the storage, of energy. Energy management is indeed a major issue for the world. Several domains are reviewed like equipment, buildings, lighting, transport, industry. Such a topic complements another important topic addressed for ICs and MEMS themselves, namely the design of low-power devices. A way for future ultra low power devices is also addressed. ICs and MEMS for energy management can be obtained from CMP that is briefly reviewed.

I -INTRODUCTION

For a long time the IC power issue has been focusing on the design of low-power ICs and MEMS in order to look for the longest possible battery lifetime of mobile devices, like telephones. This is a very useful goal, but the role of ICs and MEMS in energy management is likely to be even more important. This paper has 4 external sources: the IEA to G8 policy recommendations, in terms of total energy, the keynote by R.P. de VRIES at ISSCC 2009 [START_REF] Leaner | Adapting to a Changing Climate of Innovation[END_REF], the keynote by Ch. BELADY at ICCD 2008 [START_REF] Lean | Lead or Die[END_REF], and course notes by A. SHAKOURI [START_REF] Shakouri | [END_REF].

The recommendation of IEA to G8 is to save 20% of total energy by 2030. This will reduce by 20% per year the global CO 2 emissions by 2030.These savings could come from various domains like Buildings, equipment, Lighting, Transport, Industry, for a total of 92 EJ. Examples of savings are given for several domains in the following.

II -ELECTRONIC EQUIPMENT

The standby modes and the operational modes can be considered. It is considered that the standby mode is responsible for 5% to 10% of the total home power consumption. Great savings may be achieved.

An example of potential savings in the operational mode can be given with TV displays. The figure 1 displays the power as a function of the size of the screen. When 36M decide to move to home cinema, it means that an additional power plant is necessary…. The worst comes from the fact that plasma TV consumes much more than LCD while plasma TV is recommended for very large screens. These power consumption values are much more higher than the power consumption of the old cathodic displays: around 100 W. Huge savings could be obtained here. MEMS are also offering a hope if TMOS could replace LCD, plasma and OLED devices [START_REF] Leaner | Adapting to a Changing Climate of Innovation[END_REF].

Figure 1: TV power vs. screen size Data centers were responsible for 1.2% of the total consumption in USA in 2005. Here the design of low-power servers is crucial since every W saved in the die translates into $3 to $4 in support cost. This is important when data centers contain 100.000 or 200.000 servers.

III -AUTOMOTIVE

Automotive is a major source of oil consumption: 60% of the world oil is consumed in transport, road vehicles are responsible for 80% of the total transport energy consumption. Much has already been done since 35% decrease in oil consumption per car has been achieved over the last 30 years. But more is recommended to come: 50% more reduction by 2030 and 50% more for light-duty vehicles. Of course, electronics has been and will even be more responsible for these savings. Electric cars will help on oil consumption on the roads, but they need an electrical source …. (if all cars in France would go electrical, this would lead to +25% to +50% electrical consumption…). So the total process may be not very efficient. Presently, the $ value of batteries is about 30% in an electrical car.

Various types of hybrid cars can save oil consumption with stop-start, with the use of electrical power for acceleration, with regenerative braking, with electrical transmission…. Many DC-DC converters are needed, DC-AC are needed, etc.

IV -LIGHTING

Lighting is responsible for 20% of total electricity produced. The replacement of incandescent lamps by fluorescent or tube lights can save 80% (EU: by 2012). The move from discrete power components to integrated solutions for the drive electronics will help. Occupancy detection can also help in savings.

V -BUILDINGS

Energy is consumed here for the ventilation, heating, air conditioning, lighting.

Metering allows the shaving of peaks (hence of the total capacity), by powering off some devices. Many sensors are required.

Concrete examples exist like a zero energy building in France (where 1,600 sensors and 550 sqm of PV are used) and a rotating solar building in Germany.

VI -THE DEVELOPMENT OF SOLAR ENERGY

Here is another example of the use of electronics. The power output of a PV cell is maximized when the cell is operated at an optimal voltage, depending on the temperature and on the irradiance. This is illustrated by the figures 2, 3 and 4. Electronics is necessary to optimize the power generation. The installed PV capacity is expected to grow by 20% to 40% per annum, and to increase rapidly when the parity cost will be achieved (between 2012 and 2018 depending on the countries).

VIII -CONCLUSIONS

Energy management is a formidable challenge to the world. Electronics will greatly help in coping with that challenge. CMP can help by providing an infrastructure for Students, Researchers, SMEs to prototype and obtain small volume production.

Other than energy management key application areas are healthcare, environment and security. CMP provided a help in many BioMed applications [START_REF] Biomed | Infrastructures for Education, Research and Industry: CMOS and MEMS[END_REF]. To cope with all these challenges, CMP will develop along several lines.

A. More Moore

It has been recognized that Students, Researchers and SME designers must be provided with the possibility to have their circuits fabricated. From its inception in 1981, CMP has been successfully pursuing this goal and experiencing a very significant growth to reach and to keep its present level. The success is partly due to the basic principles which have been governing the choices of the Service: use of industrial and advanced process lines. And fundamental limits will be reached coming from thermodynamics, quantum mechanisms, electromagnetics, etc.

B.-More than Moore

But the never ending quest for more complex systems may be satisfied by other technology developments, like the move to 3D processes, possibly not including very advanced process dies. 3D processes lead to easier to manage interconnections and to reasonable cost. CMP will introduce soon 3D processes using TSVs (through silicon vias).

It is also recognized that complementary developments must be addressed, in order to address more diversified needs. With this respect, CMP has been a pioneer in being the first service in the world to offer MEMS processes as early as 1995. Going further, more than mechanics-electronics is to be addressed like photonics, optics, fluidics, etc. CMP will be actively promoting these developments in the future.

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Optimum Load for Single Photovoltaic Cell (National Semiconductor)

Table 1 :

 1 IC processes available

	ICs design kits and CAD software
	Design kits and libraries are distributed by CMP for most of
	the processes and most commonly used CAD tools. CMP
	sometimes develop design kits, in cooperation with the
	manufacturers and the CAD vendors. CMP also offers special
	CAD software conditions from a few CAD vendors. As a focal
	point, CMP also distributes information on configuration files,
	converters, etc. About 40 design kits are available for each
	process and the main CAD tools.
	Test and packaging
	Packaging and testing services are also offered. Various types
	of packages are supported, including DIL, SOIC, CQFP,
	JLCC, PGA, etc. Test of prototypes is usually done by the
	final user. On request, especially for low volume production,
	CMP may take over testing together with manufacturing.
	MEMS
	CMP offers several processes for MEMS manufacturing based
	on bulk micromachining, as well as specific MEMS processes.
	These are depicted in Table 2.

Table 2 :

 2 MEMS processes available