Emmanuel Maruani
email: emmanuel.maruani@gmail.com

Michel Grabisch
email: michel.grabisch@univ-paris1.fr

Agnieszka Rusinowska
email: agnieszka.rusinowska@univ-paris1.fr

A study of the dynamic of influence through differential equations ⋆

Keywords: JEL Classification: C7, C6, D7 social network, inclination, importance weight, decision, influence function, differential equations

The paper concerns a model of influence in which agents make their decisions on a certain issue. We assume that each agent is inclined to make a particular decision, but due to a possible influence of the others, his final decision may be different from his initial inclination. Since in reality the influence does not necessarily stop after one step, but may iterate, we present a model which allows us to study the dynamic of influence. An innovative and important element of the model with respect to other studies of this influence framework is the introduction of weights reflecting the importance that one agent gives to the others. These importance weights can be positive, negative or equal to zero, which corresponds to the stimulation of the agent by the 'weighted' one, the inhibition, or the absence of relation between the two agents in question, respectively. The exhortation obtained by an agent is defined by the weighted sum of the opinions received by all agents, and the updating rule is based on the sign of the exhortation. The use of continuous variables permits the application of differential equations systems to the analysis of the convergence of agents' decisions in long-time. We study the dynamic of some influence functions introduced originally in the discrete model, e.g., the majority and guru influence functions, but the approach allows the study of new concepts, like e.g. the weighted majority function. In the dynamic framework, we describe necessary and sufficient conditions for an agent to be follower of a coalition, and for a set to be the boss set or the approval set of an agent.

Introduction

The phenomenon of influence between individuals or, more broadly, influence of a group of agents on an individual, is studied carefully in numerous works, e.g., in psychology, sociology, economics, physics and mathematics. The economics literature offers several surveys of different models of influence and of different approaches to this phenomenon; see, e.g., [START_REF] Jackson | Social and Economic Networks[END_REF], [START_REF] Grabisch | Different approaches to influence based on social networks and simple games[END_REF], [START_REF] Rusinowska | Different approaches to influence in social networks[END_REF]. Some of the works on influence and interaction, in particular in the game theoretical literature, are one-step models. In reality, however, the influence does not necessarily stop after one step, but may iterate. Consequently, in order to study the iteration of influence, different dynamic models of influence are proposed by sociologists and economists. One of the leading works of opinion formation is introduced in [START_REF] Degroot | Reaching a consensus[END_REF]. In that model, individuals start with initial opinions on a subject and place some (nonnegative) weights on the current beliefs of other agents in forming their own beliefs for the next period. These beliefs are updated over time. Several other authors study the DeGroot model and propose its generalizations, in particular, models in which the updating of beliefs can vary in time and circumstances; see e.g. [START_REF] Berger | A necessary and sufficient condition for reaching a consensus using DeGroot's method[END_REF], [START_REF] Demarzo | Persuasion bias, social influence, and unidimensional opinions[END_REF], [START_REF] Krause | A discrete nonlinear and nonautonomous model of consensus formation[END_REF], [START_REF] Lorenz | A stabilization theorem for dynamics of continuous opinions[END_REF], Friedkin andJohnsen (1990, 1997), [START_REF] Jackson | Social and Economic Networks[END_REF], [START_REF] Golub | Naïve learning in social networks and the wisdom of crowds[END_REF]. A related dynamic framework of influence is also presented in [START_REF] Asavathiratham | Influence model: a tractable representation of networked Markov chains[END_REF], [START_REF] Asavathiratham | The influence model[END_REF] and [START_REF] Koster | Voting power and social interaction[END_REF].

A cooperative approach to influence is presented in Hu and Shapley (2003a,b), where the command structure is applied to model players' interaction relations by simple games. Boss sets and approval sets for a player are defined, and based on these sets a simple game called the command game for the player is constructed. Also the concept of command function is defined. The authors introduce an authority distribution over an organization and define the authority equilibrium equation. In particular, they consider multi-step commands, where commands can be implemented through command channels.

The present paper is related to another framework of influence originally introduced in [START_REF] Hoede | A theory of decisional power[END_REF]. In the original one-step model, agents have to make their acceptance-rejection decision on a certain issue. Each agent has an inclination to say either 'yes' or 'no', but due to a possible influence of the other agents, his final decision ('yes' or 'no') may be different from his initial inclination. Refinements and generalizations of this model are presented in several works. Grabisch and Rusinowska (2010a) investigate some tools to analyze influence in this framework. In particular, they define the influence indices to measure the influence of a coalition on an agent, introduce several influence functions and study their properties, and investigate the concept of a follower of a coalition. In Grabisch and Rusinowska (2010b) the yes-no model of influence is generalized to a framework in which each agent has an ordered set of possible actions, and in Grabisch and Rusinowska (2011b) the model is extended to a continuum of actions. [START_REF] Grabisch | Measuring influence in command games[END_REF] compare the influence model with the framework of simple games called command games (Hu and Shapley (2003b,a)). It is shown that the presented framework of influence is more general than the framework of command games. In Grabisch and Rusinowska (2011a) the exact relations between the key concepts of the influence model and the framework of command games are established. There are also some studies of the dynamic of influence in the model mentioned above, i.e., the model of initial inclinations and final decisions. In [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF] the yes-no model with a single step of mutual influence is generalized to a dynamic model of influence based on aggregation functions. The decision process in which the mutual influence does not stop after one step but iterates, and the convergence of an influence function are studied. In particular, the authors investigate stochastic influence functions and apply Markov chains theory to the analysis of such functions.

The aim of the present paper is to apply another approach proposed in Maruani (2010) to study the dynamic of influence. We propose a dynamic model in which an agent gives a certain importance, reflected by a weight, to other agents in making his final decision. Such a weight might be positive, negative, or equal to zero, which corresponds to the stimulation of the agent by the 'weighted' one, the inhibition, and the absence of relation between the agents in question, respectively. Furthermore, we define the exhortation of an agent which is the weighted sum of the opinions that the agent receives from all agents. The opinions of the agents are updated over time and the updating rule is based on the sign of the exhortation. The use of continuous variables permits the application of differential equations systems to the analysis of the convergence of agents' decisions in long-time. We study the dynamic of some influence functions introduced originally in the discrete model, e.g., the majority and guru influence functions, but the approach allows the study of new concepts, like e.g. the weighted majority function. In the dynamic framework, we describe necessary and sufficient conditions for an agent to be follower of a coalition, and for a set to be the boss set or the approval set of an agent. By applying the approach based on differential equations to the influence model, we recover the results of the discrete model on classical influence functions, and the results on the boss and approval sets for command games equivalent to some selected influence functions.

What are the innovative elements of the model with respect to other studies of the influence framework, and what are the improvements and advantages that the model brings to the analysis of influence? First of all, we like to stress that to the best of our knowledge the approach based on differential equations has not been used in the influence frameworks so far. We see two original features of the present model compared to our previous studies as well as to other ones.

First, the main aim is the analysis of the dynamic aspects of influence, where the opinion of agents is evolving in time, instead of considering as in our studies so far that influence stops after one step. Generally speaking, there are two main streams in analyzing the dynamic aspects of a system. The first one is to model the system with a set of states, and assume a probabilistic transition between states. This leads to stachastic processes, and in particular, Markovian processes. In a recent paper, [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF] follow this line and provide a general analysis of convergence of the dynamic yesno model of influence, assuming that agents update their opinion by aggregating opinions of the other agents. The second stream is to establish a set of differential equations governing the evolution of the system. This is the way we follow in this paper. We believe that new insights in the analysis of influence can be brought by this approach. This paper constitutes a first step in this direction.

Its second original feature lies in incorporating the importance weights of positive and negative signs. This allows to model the positive (direct) and negative (opposite) influence at the same time, and in a very simple way. The yes-no model introduced in Grabisch and Rusinowska (2010a) and its generalization to the multi-action model presented in Grabisch and Rusinowska (2010b) are one-step models for which the authors define the indices of positive and negative influence separately, and they do not assume any weights of importance. The same remark holds for our study of command games in [START_REF] Grabisch | Measuring influence in command games[END_REF] and Grabisch and Rusinowska (2011a). [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF] do provide a general analysis of convergence of the dynamic yes-no model of influence in which every agent updates his opinion according to his aggregation function. However, the nondecreasingness assumption in the definition of an aggregation function implies positive influence, and therefore the model based on aggregation functions does not cover a framework of negative influence. The model of [START_REF] Degroot | Reaching a consensus[END_REF] and its modifications (for an overview, see e.g., [START_REF] Jackson | Social and Economic Networks[END_REF]) assume that the opinion of an agent is a number in [0, 1] and the aggregation is done through a weighted arithmetic mean (convex combination). Players place weights on the current beliefs of the others in forming their own beliefs for the next period, but these weights are nonnegative and no inhibition possibility is incorporated in the model. The convergence of the process (of the updating/interaction matrix) is studied.

The paper is structured as follows. In Section 2 the main concepts of the influence model in question and the framework of command games are presented. In Section 3 we introduce the dynamic model of influence. The dynamic of selected influence functions is studied in Section 4. Section 5 concerns followers in the dynamic model and under selected influence functions. The analysis of the dynamic model in terms of command games, in particular, the determination of the boss and approval sets in the presented framework is delivered in Section 6. Concluding remarks are given in Section 7.

2 The model of influence and command games

Main concepts of the influence model

Let us start by mentioning some notations used in the paper. (1, 1, . . . , 1) ∈ {-1, +1} n is denoted by 1 N , (-1, -1, . . . , -1) ∈ {-1, +1} n by -1 N , and mixed cases by (-1 N \S , 1 S ). For every real number x ∈ R, ⌊x⌋ denotes the largest integer not greater than x. By δ ij we denote the Kronecker delta, i.e., δ ij = 1 if i = j, and 0 otherwise.

In this section we recapitulate main concepts of the one-step yes-no model of influence investigated in Grabisch and Rusinowska (2010a). We consider a social network with the set of all players (agents, voters) denoted by N := {1, ..., n}. Each player has to make an acceptance-rejection decision concerning a certain issue, and he has an inclination to say either 'yes' (denoted by +1) or 'no' (denoted by -1). An inclination vector is denoted by I = (I 1 , ..., I n ), where I k ∈ {-1, +1} indicates the inclination of agent k, for each k ∈ N . For any I ∈ {-1, +1} n , I + denotes the set of players with the positive inclination

I + := {k ∈ N : I k = +1}.
Moreover, for any S ⊆ N , we denote by U I S the set of all inclination vectors under which all members of S have the same inclination

U I S := {I ∈ {-1, +1} n : ∀k, j ∈ S [I k = I j ]}. In particular, U I k = {-1, +1} n for any k ∈ N . We denote by I S the value I k for some k ∈ S, I ∈ U I S .
It is assumed that agents may influence each other in the network, and due to the influences the final decision of an agent may be different from his original inclination. Formally, each inclination vector One of the key concepts of the influence model is the concept of follower. An agent is said to be follower of a coalition if he always decides according to the inclination of that coalition, assuming that the coalition in question is unanimously inclined. Formally, for ∅ = S ⊆ N and B ∈ B, the set of followers of S under B is therefore defined as

I ∈ {-1, +1} n is transformed into a decision vector B(I) = (B 1 (I), ..., B n (I)), where B : {-1, +1} n → {-1, +1} n , I → B(I)
F B (S) := {j ∈ N : ∀I ∈ U I S [B j (I) = I S ]}.
We recapitulate three particular influence functions that have been introduced and investigated in Grabisch and Rusinowska (2010a):

-Let n ≥ t > ⌊ n 2 ⌋.
The majority influence function Maj [t] ∈ B is defined by

Maj [t] (I) := 1 N , if |I + | ≥ t -1 N , if |I + | < t , ∀I ∈ {-1, +1} n .
According to the majority influence function if a majority of players has the positive inclination, then all agents decide +1, otherwise all decide -1. For each S ⊆ N , the set of followers under the majority function is equal to

F Maj [t] (S) = N, if |S| ≥ t ∅, if |S| < t, (1)
i.e., everybody follows a coalition with a cardinality of at least t, and nobody follows a coalition with less than t members. -Let k ∈ N be a particular player called the guru. The guru influence function Gur [ k] ∈ B is defined by

Gur [ k] j (I) := I k , ∀I ∈ {-1, +1} n , ∀j ∈ N.
Hence, according to this function, when a guru exists, every agent follows the guru. For each S ⊆ N , the set of followers under the guru function is given by

F Gur [ k] (S) = N, if k ∈ S ∅, if k / ∈ S. (2)
In other words, all agents follow a coalition containing the guru, and nobody follows a coalition without the guru. -The identity function Id ∈ B depicts the absence of any influence and is defined by

Id(I) := I, ∀I ∈ {-1, +1} n .
Moreover, we have for each S ⊆ N ,

F Id (S) = S, (3)
which means that all members of a coalition and only them follow that coalition.

Command games and equivalence with influence functions

Next, we present some of the main concepts concerning command games that have originally been introduced by Hu and Shapley (2003a,b).

Let N = {1, ..., n} be the set of agents (players, voters). With each k ∈ N , two collections of coalitions, the so called boss set and approval set are associated. Hu and Shapley (2003a) define these sets as follows. For k ∈ N and S ⊆ N \ k:

-S is a boss set for k if S determines the choice of k; -S is an approval set for k if k can act with the approval of S.

It is assumed that any superset (in N \ k) of a boss set is a boss set. For each k ∈ N , a simple game (N, W k ) called the command game for k is created, with the set of winning coalitions given by W k := {S : S is a boss set for k} ∪ {S ∪ k : S is a boss or approval set for k}.

We recover the boss sets for agent k

Boss k = {S ⊆ N \ k : S ∈ W k } = W k ∩ 2 N \k
and the approval sets for k

App k = {S ⊆ N \ k : S ∪ k ∈ W k but S / ∈ W k }. Obviously, Boss k ∩ App k = ∅. Given the set of command games Ω = {(N, W k ) : k ∈ N },
for any coalition S ⊆ N , the command function ω(S) is defined as the set of all members that are commandable by S:

ω(S) := {k ∈ N : S ∈ W k }.
In [START_REF] Grabisch | Measuring influence in command games[END_REF] the model of influence is applied to the framework of command games and the relations between these two frameworks are shown; see also Grabisch and Rusinowska (2011a). We present one of these relations, i.e., the equivalence between command games and (command) influence functions.

Let Ω = {(N, W k ) : k ∈ N } be a set of command games, ω(S) be a set of agents commandable by S, and F B (S) denote the set of followers of S under an influence function B. The influence function B and the set of command games Ω are said to be equivalent if F B ≡ ω, i.e., if for each coalition S ⊆ N , the set of followers of S under the influence function B and the set of agents commandable by S under Ω coincide.

In [START_REF] Grabisch | Measuring influence in command games[END_REF] we construct command games equivalent to the influence functions recapitulated in Section 2.1 and determine boss and approval sets for these command games:

(i) Let n ≥ t > ⌊ n
2 ⌋ and Maj [t] ∈ B be the majority influence function and let {(N, W Maj ) : k ∈ N } be a set of command games given by

W Maj [t] k = {S ⊆ N : |S| ≥ t}, ∀k ∈ N.
The majority influence function Maj [t] and the set of command games {(N, W Maj [t] k ) : k ∈ N } are equivalent. In other words, the command games in which winning coalitions for each player are the ones with the cardinality at least t, n ≥ t > ⌊ n 2 ⌋, are equivalent to Maj [t] . Moreover, we have for n > 2, n ≥ t > ⌊ n 2 ⌋, and k ∈ N

Boss Maj [t] k = {S ⊆ N : |S| ≥ t ∧ k / ∈ S} (4) App Maj [t] k = {S ⊆ N : |S| = t -1 ∧ k / ∈ S}. (5)
In particular, for t = n, k ∈ N ,

Boss Maj [t] k = ∅, App Maj [t] k = N \ k.
(ii) Let Gur [ k] ∈ B be the guru function with the guru k ∈ N and let {(N, W

Gur [ k] k ) : k ∈ N } be a set of command games given by W Gur [ k] k = {S ⊆ N : k ∈ S}, ∀k ∈ N.
The guru function Gur [ k] and the set of command games {(N, W

Gur [ k] k ) : k ∈ N } are equivalent.
Hence, the command games in which winning coalitions for each player are the coalitions containing a certain player k, are equivalent to the guru function Gur [ k] with the guru k. Moreover,

Boss Gur [ k] k = ∅, App Gur [ k] k = 2 N \ k (6) Boss Gur [ k] k = {S ⊆ N : k ∈ S ∧ k / ∈ S}, App Gur [ k] k = ∅, f or k = k. ( 7
Id k = ∅, App Id k = 2 N \k . ( 8
)
3 The dynamic model of influence

Description of the model and stable states

In order to analyze the dynamic aspects of influence, we consider the following model introduced originally in Maruani (2010).

Let N = {1, 2, ..., n} denote the set of agents. We are interested in the influence of all n agents on a player i ∈ N . Let e j denote the inclination of agent j ∈ N , where e j = ±1. Agent i gives to agent j a certain importance which is reflected by a weight p ij ∈ [-1, 1]. p ij > 0 corresponds to the stimulation of i by j, p ij < 0 corresponds to the inhibition, and p ij = 0 means the absence of relation. The state (inclination) e j will contribute to the decision of agent i with the weight c ij = p ij e j .

What is the interpretation of the contribution weights c ij ? Obviously, they can be positive, negative or zero, which means that if player i would consult only the state e j , then i's decision would be 'yes', 'no' or would be equal to i's state, respectively. More precisely, suppose that agent i when forming his decision does not take into account the inclination of agent j, i.e., p ij = 0. Then obviously p ij e j = 0, independently of the inclination of agent j, which reflects no contribution of j's state to i's decision. Suppose that j stimulates the decision of agent i, i.e., p ij > 0. Then the weight of the contribution of j's state to the decision of agent i has the same sign as e j , which means that i's decision would be as the state of j when i considered only the state e j . Moreover, the higher p ij the more e j contributes to i's decision being the same as e j when all players are considered. Suppose now that j inhibits or discourages the decision of agent i, i.e., p ij < 0. Then the weight of the contribution of j's state to the decision of agent i has the opposite sign than e j , which means that i's decision would be opposite to the state of j when i considered only the state e j . In particular, if j is inclined negatively, then i's decision would be positive when consulting only e j . The higher the absolute value of p ij the more e j contributes to i's decision being opposite to e j when all players are considered.

Since the players interact, every agent consults the states of all agents, and based on the importance weights he aggregates all contributions to his decision. Hence, the exhortation E i obtained by agent i ∈ N is defined by the weighted sum of the inclinations of all agents, or saying differently, by the weighted sum of the opinions that i receives from the agents (including his own opinion):

E i = j∈N c ij = j∈N p ij e j . (9)
Figure 1 presents the idea of the exhortation. The updating rule is the following. If E i > 0, then agent i goes to the state +1. If E i < 0, then he goes to the state -1, and if E i = 0, then i stays in his present state.

The influence function B i of agent i ∈ N is defined by

B i (e) = sgn(E i )
, where e = (e 1 , . . . , e n ) and sign

(E i ) =      1, if E i > 0 -1, if E i < 0 e i , if E i = 0 (10)
Remark 1 In this dynamic model, we can express the influence functions recapitulated in Section 2.1 as follows:

(i) The majority influence function with t = ⌊ n 2 ⌋ + 1 in which every agent plays a role can be represented by p ij = 1 n . (ii) The guru function with the guru k in which every agent is influenced only by the guru can be represented by p ij = 0 for each j = k and p i k = 1. (iii) The identity function in which every agent influences only himself can be represented by

p ij = δ ij .
Stable states of the system satisfy e

(k+1) i = e (k) i
for each i ∈ N , starting from a certain k, where k is the number of iteration and e (k) i denotes the inclination (state) of i at time k. This means that the state e i and the exhortation E i have the same sign, and therefore e i E i > 0. In other words, the stable states satisfy the following inequality: j∈N p ij e i e j > 0 for each i ∈ N.

The evolution of the population can be expressed by

e (k+1) i = B i (e (k) 1 , e (k) 2 , . . . , e (k) j , . . . , e (k) n ) (11)
where B i is the influence function of voter i ∈ N . A stable state satisfies therefore

e (k) i = B i (e (k) 1 , e (k)
2 , . . . , e

j , . . . , e (k) n ).

An obvious way to get stability is to forbid any relation between agents, i.e., to assign the weights as p ij = δ ij .

Dynamic of the model in the continuous framework

Let us consider an extension of the dynamic influence model to the continuous framework; see also [START_REF] Maruani | Jeux d'influence dans un réseau social[END_REF]. The influence function remains

e (k+1) i = sgn E (k) i which together with E (k) i = j∈N p ij e (k) j
can be written as

e (k+1) i -e (k) i (k + 1) -k = sgn j p ij e (k) j -e (k) i . ( 12
)
For a small time step, we can make the approximation

e (k+1) i -e (k) i (k + 1) -k ≈ de i dt (13)
and also the approximation

sgn j p ij e j ≈ tanh a j p ij e j ( 14
)
where the parameter a controls the tendency towards the function sgn. This approximation keeps the properties of the function sgn that are essential for our analysis: it is increasing and bounded between -1 and 1 and nullifies in 0. From ( 12), (13), and ( 14), in order to study the dynamic of the model, we need to solve the following system:

de i dt + e i = tanh a j p ij e j , i = 1, . . . , n (15)
and then put e i = sgn [e i (t)]. In Section 4 we apply this dynamic approach of differential equations to classical influence functions. The results that we present have been originally shown in [START_REF] Maruani | Jeux d'influence dans un réseau social[END_REF].

4 The dynamic of selected influence functions 4.1 The majority influence function with t = ⌊ n 2 ⌋ + 1 As mentioned in Remark 1(i), the majority influence function with t = ⌊ n 2 ⌋ + 1 can be represented by the weights p ij = 1 n . The system (15) of differential equations that we need to solve is therefore

de i dt + e i = tanh a n j e j , i = 1, . . . , n. (16)
The dynamic approach allows for the analysis of the influence model introduced in Grabisch and Rusinowska (2011b) in which agents have a continuum of actions, i.e., the set of all inclinations is equal to an interval [x, y], where x, y ∈ R. with p = 1 a . The fixed points satisfy tanh(y) = py. There is always y = 0 and another fixed point y 0 iff p < 1 (a > 1). We are interested in the stability of fixed points. In the neighborhood of y = 0

dy dt + y = 1 p tanh(y) ≈ y p dy dt + p -1 p y = 0 y(t) = y(0) exp 1 -p p t
For 0 < p < 1 the origin is unstable.

In the neighborhood of y 0 , we put y(t) = y 0 + ε(t)

dy dt + y = 1 p tanh(y) dε dt + y 0 + ε(t) = 1 p tanh (y 0 + ε(t)) = 1 p tanh(y 0 ) + tanh (ε(t)) 1 + tanh(y 0 ) tanh (ε(t)) = 1 p py 0 + tanh (ε(t)) 1 + py 0 tanh (ε(t))
where we have used py 0 = tanh(y 0 ). A first order approximation yields

dε dt + y 0 + ε(t) ≈ 1 p py 0 + ε(t) 1 + py 0 ε(t) ≈ 1 p [py 0 + ε(t)] [1 -py 0 ε(t)] ≈ y 0 -py 2 0 ε(t) + ε(t) p
and ultimately dε dt

+ 1 + py 2 0 - 1 p ε(t) = 0 If 1 + py 2 0 -1 p > 0
, then the solution is the decreasing exponential and point y 0 is stable. Let us show that 1 + py 2 0 -1 p > 0. Let

A = 1 + py 2 0 - 1 p py 0 = tanh(y 0 ) A = 1 + y 0 tanh(y 0 ) - y 0 tanh(y 0 ) = 1 + y 0 tanh(y 0 ) - 1 tanh(y 0 ) = 1 + y 0 tanh 2 (y 0 ) -1 tanh(y 0 ) = 1 -y 0 1 cosh 2 (y 0 ) tanh(y 0 ) = 1 -y 0 1 cosh(y 0 ) sinh(y 0 ) = 1 - 2y 0 sinh(2y 0 ) = 1 - u sinh(u) We have sinh(u) u = 1 + u 2 3! + u 4 5! + ... sinh(u) u > 1 ⇒ 1 - u sinh(u) > 0.
Proposition 1 If agents make their decisions according to the majority influence function with t = ⌊ n 2 ⌋ + 1, then the decision of each agent converges to the sign of the sum of the agents' inclinations.

Proof: Let us consider the system de i dt + e i = tanh a n j e j (t) , i = 1, . . . , n.

With ε i = a n e i , we have, for each i,

dε i dt + ε i = a n tanh j ε j (t)
Adding term by term the equations of the system, the sum S(t) = j ε j (t) satisfies

dS dt + S = a tanh [S(t)]
According to Lemma 1, S converges to a stable fixed point S ∞ , which satisfies for a > 1

S ∞ = a tanh(S ∞ )
The system that we consider becomes

dε i dt + ε i = a n tanh [S(t)] .
By changing the function ε i (t) = E i (t) exp(-t) (ε i (0) = E i (0)), we get the equation

dE i dt = a n exp(t) tanh [S(t)]
whose general solution is

E i (t) = E i (0) + a n t 0 exp(u) tanh [S(u)] du
The solution for ε i is therefore

ε i (t) = ε i (0) exp(-t) + a n exp(-t) t 0 exp(u) tanh [S(u)] du (17)
We are interested in the asymptotic form of the solution. The first term of the right hand side of (17) vanishes. Let us denote by η i the second term, i.e.,

η i (t) = a n exp(-t) t 0 exp(u) tanh [S(u)] du
Let us fix for the moment some T . Then, for t > T we decompose the integral in two terms

η i (t) = a n exp(-t) T 0 exp(u) tanh [S(u)] du + t T exp(u) tanh [S(u)] du = η (1) i (t) + η (2) i (t)
and consider successively the two components. We analyze the first term η

(1)

i (t) = a n exp(-t) T 0 exp(u) tanh [S(u)] du
The tanh is bounded by 1, so we have

T 0 exp(u) tanh [S(u)] du ≤ T 0 exp(u)du = exp(T ) -1
Given T , exp(T ) -1 is a fixed number and we denote it by B. Then

η (1) i (t) ≤ aB n exp(-t)
and therefore lim t→∞ η

(1)

i (t) = 0 The second term is η (2) i (t) = a n exp(-t) t T exp(u) tanh [S(u)] du
For u large enough, which is the case, S(u) is close to S ∞ . By continuity tanh [S(u)] is close to tanh (S ∞ ), which is equal to S∞ a . It is then appropriate to choose T as follows. Setting

tanh [S(u)] = S ∞ a [1 + δ(u)]
introduces the function δ(u) which vanishes at infinity. The free parameter T is then chosen such that for any given positive ε and for t > T , |δ(t)| < nε |S∞| . We have then η

(2)

i (t) = a n exp(-t) t T exp(u) tanh [S(u)] du = a n exp(-t) t T exp(u) S ∞ a [1 + δ(u)] du = S ∞ n exp(-t) t T exp(u)du + S ∞ n exp(-t) t T δ(u) exp(u)du = S ∞ n (1 -exp(T -t)) + ϕ(t)
where the asymptotic value of the first term is S∞ n , and the second term is

ϕ(t) = S ∞ n exp(-t) t T δ(u) exp(u)du |ϕ(t)| ≤ S ∞ n exp(-t) t T exp(u) nε |S ∞ | du ≤ ε exp(-t) t T exp(u)du ≤ ε
The asymptotic value of ε i is then S∞ n , and the asymptotic value of j ε j is

n j=1 S∞ n = S ∞ .
Remark 2 (The majority vote decreases costs) The fixed points of the differential system de k dt = g k (e 1 , e 2 , ..., e n ), k = 1, . . . , n satisfy by

definition de k dt = 0, k = 1, . . . , n, which is equivalent to k de k dt 2 = 0.
Let us suppose the existence of a function G of n variables such that for each k

g k (e 1 , e 2 , ..., e n ) = - ∂G ∂e k and calculate dG dt = k ∂G ∂e k de k dt = - k g k de k dt = - k de k dt 2 ≤ 0
which means that G is decreasing in time and reaches its minimum when each de k dt = 0, i.e., for the fixed point of the system. We have

de k dt + e k = f k (e 1 , e 2 , ..., e n ) ⇒ de k dt = f k (e 1 , e 2 , ..., e n ) -e k (g k = f k -e k )
Let us apply this to our differential system (16), letting ε k = a n e k :

dε k dt = a n tanh j ε j (t) -ε k
(all f being identical). We multiply both sides of each differential equation by

dε k dt dε k dt 2 = a n dε k dt tanh j ε j (t) -ε k dε k dt and obtain k dε k dt 2 = a n tanh j ε j (t) k dε k dt - k ε k dε k dt With S(t) = k ε k (t) we have then k dε k dt 2 = a n dS dt tanh [S(t)] - 1 2 d k (ε k ) 2 dt Note that dS dt tanh [S(t)] = 1 cosh [S(t)] d dt cosh [S(t)] = d dt ln {cosh [S(t)]}
Hence, up to some unessential additive constant, we get the cost function

G(ε 1 , ε 2 , ..., ε n ) = 1 2 k ε 2 k (t) - a n ln cosh k ε k (t) .

The guru function and the identity function

As mentioned in Remark 1(ii), the guru function with the guru k can be represented by

∀j = k, p ij = 0, p i k = 1.
The system of differential equations given in (15) that we need to solve becomes

de i dt + e i = tanh(ae k ), i = 1, . . . , n. (18)
One can see that, on the one hand, the guru evolves only according to its own inclinations, and on the other hand, for all the remaining agents the guru evolution acts as a forcing term. The respective evolution equations of the agents differ only in their respective initial values. Hence, the following Proposition 2 is coherent with the intuition:

Proposition 2 If agents make their decisions according to the guru function, then the decision of each agent converges to the inclination of the guru.

Proof: Let g 0 = 0 be a stable fixed point of the equation dy dt + y = a tanh(y) (it exists by virtue of Lemma 1). This means that asymptotically (in long term) we can write, letting g = e k for simplicity:

g(t) = g 0 + γ(t)
where pg 0 = tanh(g 0 ), p = 1 a , and γ(t) converges to zero with t tending to infinity. There exists t 0 such that for t > t 0 , γ(t) < ǫ pg 0 . For each agent i, we have

de i dt + e i = 1 p tanh[g(t)] = 1 p tanh [g 0 + γ(t)] = 1 p tanh(g 0 ) + tanh [γ(t)] 1 + tanh(g 0 ) tanh [γ(t)] ≈ 1 p pg 0 + γ(t) 1 + pg 0 γ(t) ≈ 1 p [pg 0 + γ(t)] [1 -pg 0 γ(t)] ≈ 1 p pg 0 -(pg 0 ) 2 γ(t) + γ(t) = g 0 + Bγ(t)
where we used that 1 1+ǫ = 1ǫ (|ǫ| ≪ 1).

The value B is not important. The change of the function e i (t) = g 0 + z i (t) (the aim is to show that z i (t) converges to 0) gives

dz i dt + z i = Bγ(t)
We will show that lim t→∞ z i (t) = 0. Let us consider the equation

dz dt + z(t) = Bγ(t)
The homogeneous solution is z(t) = z 0 exp(-t)

For t > t 0 the particular solution is of the form

z(t) = u(t) exp(-t)
and it must satisfy

dz dt + z(t) = du dt exp(-t) du dt = Bγ(t) exp(t)
We have

u(t) = B t t 0 γ(u) exp(u)du
The general solution is therefore of the form z(t) = z 0 exp(-t) + u(t) exp(-t) = z 0 exp(-t) + B exp(-t) Since this converges to zero, we have for each i, e i (t) = g 0 + z i (t) → g 0 .

As mentioned in Remark 1(iii), the identity function can be represented by p ij = δ ij . The system of differential equations that we need to solve for each i is

de i dt + e i = tanh(ae i ).
Proposition 3 If agents make their decisions according to the identity function, then the decision of each agent converges to his own inclination.

Proof: Evident from Lemma 1.

Followers in the dynamic model

As recapitulated in Section 2.1, followers of a coalition S are the agents who always follow the inclination of S, assuming that S is unanimously inclined. The set of followers of coalition S under the influence function B is therefore defined as This result shows that in case of the guru function, the followers of S depend only on the presence of the guru in coalition S. We get then

F Gur [ k] (S) = N, if k ∈ S ∅, if k / ∈ S
which is equal to (2).

For the identity function p ij = δ ij for each i, j. We have

j∈S p ij = 1 if i ∈ S 0 if i / ∈ S , j / ∈S |p ij | = 0 if i ∈ S 1 if i / ∈ S .
Hence,

j∈S p ij > j / ∈S |p ij | ⇔ i ∈ S. (20)
This means that the followers of S under the identity function are the players of S and only them, i.e., F Id (S) = S which confirms (3).

6 Boss and approval sets in the dynamic model

Using our dynamic model, we can also determine the boss and approval sets of command games. We have the following:

p ij + p ii > i =j / ∈S |p ij | j∈S p ij ≤ j / ∈S |p ij |.
Proof: It is clear from the proof of Proposition 4.

Proposition 5 provides simple conditions for determining boss sets and approval sets. Boss sets for i are those sets S such that the algebraic sum of weights for agents in S is greater than the sum of absolute values for the other agents. From Proposition 4, we see that an agent follows his boss sets. The condition for approval sets shows that roughly speaking, an approval set of i together with i has "more weight" than the remaining agents, but it is not the case anymore if i's weight is counted for the weights of agents outside the approval set.

Let us apply Proposition 5 to the majority influence function with t = ⌊ n 2 ⌋ + 1. We have p ij = 1 n for each i, j. S is the boss set for agent i if and only if

j∈S p ij > j / ∈S |p ij | ⇔ |S| n > n -|S| n ⇔ |S| > n 2 .
We have therefore Boss

Maj [t] i = S ⊆ N \ i : |S| > n 2 which is coherent with (4).
S is the approval set for agent i if and only if

∀e ∈ E, j∈S p ij + p ii > i =j / ∈S |p ij | j∈S p ij ≤ j / ∈S |p ij | ⇔ |S| n + 1 n > n-|S|-1 n |S| n ≤ n-|S| n We have therefore App Maj [t] i = S ⊆ N \ i : |S| = ⌊ n 2 ⌋
which is coherent with (5).

Let k be the guru. By virtue of Proposition 5(i) and ( 19), we have

Boss Gur [ k] k = ∅ and Boss Gur [ k] k = {S ⊆ N \ k : k ∈ S} for k = k.
Using Proposition 5(ii), we conclude that S is the approval set for agent i if and only if p ii = p k k = 1. Hence, every set not containing k is the approval set for k, and every agent different from k has the empty approval set:

App Gur [ k] k = 2 N \ k and App Gur [ k] k = ∅ for k = k.
We get therefore the results given in ( 6) and (7).

For the identity function, we have p ij = δ ij for each i, j. Using Proposition 5(i) and (20), we get Boss Id i = ∅. By virtue of Proposition 5(ii), we conclude that S is the approval set for agent i if and only if p ii = 1, that is, each set not containing i is the approval set for i. Hence, App Id i = 2 N \i , which gives exactly (8).

Conclusions

The paper concerns the influence model originally introduced in Hoede and Bakker (1982) and later studied and generalized in several works. We have proposed a new approach to analyze the dynamic of the model. This approach is based on the use of differential equations.

To be more precise, we have introduced a dynamic model of influence in which an agent may give a certain importance to other agents in making his final decision. This importance is reflected by a weight which, depending of the sign (positive, negative or zero), corresponds to the stimulation, the inhibition or the absence of relation, respectively. We have defined the exhortation obtained by an agent as the weighted sum of the opinions that the agent receives from the others. The updating rule is based on the sign of the exhortation: its positive (negative) value means going to the positive (negative) state, and the exhortation equal to zero corresponds to staying in the present state.

The main ideas of the application of this approach to the model of influence is to switch to the continuum case and to apply some approximations allowing the use of differential equations systems. The solutions of these systems give the same results obtained earlier for the classical influence functions. It also leads to the results on followers obtained for the discrete case, and to the results on the boss and approval sets of command games.

In the paper we have shown that if the majority function is used, then the decision of each agent converges to the sign of the sum of the agents' inclinations, and in case of the guru function, the decision of each agent converges to the inclination of the guru. Under the identity function, the agents' decisions converge obviously to their own inclinations. Furthermore, we have described the necessary and sufficient condition that an agent is the follower of a coalition in the dynamic framework. We have used that result to determine the sets of followers for the majority function, the guru function, and the identity function. We have also determined the necessary and sufficient conditions that a coalition is the boss set or the approval set for an agent in the dynamic model. We have applied these results to determine the boss and approval sets of command games equivalent to the three influence functions in question: the majority influence function, the guru function, and the identity function. Both in the case of followers and boss and approval sets, the conditions depend on the relation(s) between the weights that reflect the importance given by the agents to the inclinations of the others in making their own decisions.

To the best of our knowledge, the differential equations approach has never been applied before to the influence model in question and is also innovative with respect to analysis of the influence framework in general. We believe that this approach can bring new insights in the analysis of the dynamic aspects. Moreover, modeling positive and negative influence in the same time by incorporating the importance weights that can be of any sign increases significantly the applicability of the model.

In the paper, we aimed at introducing this new and useful framework of influence and at studying the dynamic of the standard influence functions defined in the one-step yesno model of influence. Although we have focused on these classical influence functions, we would like to stress that the approach allows the study of new concepts, like e.g. the weighted majority function. In our future research on this model, we would like to deliver a detailed analysis of the concepts that were not defined in the original yes-no model of influence, but could be defined in the present stimulation-inhibition framework. There are several possible research issues related to this model that could be raised. In the future research on this framework, we would like to analyze, in particular, non-linear influence functions and to consider temporary effects in the behavior of a group of agents.

  is the influence function 1 , and B k (I) indicates the decision made by agent k, for each k ∈ N . The set of all influence functions is denoted by B.

  [t]

  k

  ) (iii) Let Id ∈ B be the identity function and let {(N, W Id k ) : k ∈ N } be a set of command games given by W Id k = {S ⊆ N : k ∈ S}, ∀k ∈ N. The identity function Id and the set of command games {(N, W Id k ) : k ∈ N } are equivalent. This means that the command games, in which for each player k winning coalitions for k are the coalitions containing k, are equivalent to the identity function. We have also for each k ∈ N Boss

p

  Fig. 1. The exhortation

Lemma 1

 1 For a > 1, the differential equation dx dt + x = tanh(ax) has an unstable fixed point in 0 and another stable fixed point. Proof: In the equation dx dt + x = tanh(ax) we put ax = y. Hence, dy dt + y = a tanh(y

F

  B (S) := {i ∈ N : ∀e ∈ E S [B i (e) = e S ]}, where in our model, B i (e) = sgn j p ij e j . In order to determine the followers for every influence function B, first we consider a particular case with S = {e 1 }. Agent i is the follower of S if and only if ∀e ∈ E, sgn j p ij e j = sgn(e 1 ) ⇔ ∀e ∈ E, e 1 j p ij e j > 0 ⇔ ∀e ∈ E, p i1 + e 1 j≥2 p ij e j > 0 ⇔ p i1 > j≥2 |p ij | Proposition 4 Agent i is the follower of coalition S if and only if j∈S p ij > j / ∈S |p ij |.

We can also speak of the influence function of agent k, B k : {-1, +1} n → {-1, +1}, I → B k (I), for each k ∈ N .

this research has been conducted. Michel Grabisch and Agnieszka Rusinowska acknowledge support by the National Agency for Research (Agence Nationale de la Recherche), Reference: ANR-09-BLAN-0321-01.

Proof: In the general case, agent i is the follower of S if and only if ∀e ∈ E S , sgn j p ij e j = sgn(e k ) = sgn(e l ) = ... for each e k , e l ∈ S ⇔ ∀e ∈ E S , e k j p ij e j > 0

Proposition 4 gives a very simple condition to test whether an agent is a follower of a coalition S: the algebraic sum of the weights (that is, negative influence acts as a discounting factor) for the agents in S should be greater than the sum of the absolute values of weights (that is, positive and negative influence are not distinguished) for the other agents.

Let us apply Proposition 4 to the majority influence function with t = ⌊ n 2 ⌋ + 1. We have p ij = 1 n for each i, j. For each S, agent i is the follower of coalition S if and only if

This shows that in case of the majority influence function, the followers of S depend only on the cardinality of S and

which is coherent with (1).

Let player k be the guru. We have then for each i

and therefore


Reactive Workflows for Visual Analytics

Ioana Manolescu 1 and Wael Khemiri 2 and Véronique Benzaken 2 and Jean-Daniel Fekete 1 1 INRIA, France, 2 Univ. Paris-Sud, France An important class of visual analytics applications has to deal with dynamic data, which is continuously updated (e.g. by receiving new additions) while the analysis process is running. For instance, a visual analysis of Wikipedia articles, based on a live feed of Wikipedia data. The analysis has to gracefully adjust to the updates; stopping the process and triggering a total re-computation is not acceptable.

We have designed ReaViz, a reactive workflow platform, conceived and deployed in close connection with a database of application and workflow-related data. ReaViz enables the declarative specification of data-driven workflows, enforcing a clean separation between the process data, the process structure, and the user interaction which may or may not involve visualization. A distinguishing feature of ReaViz is the possibility provided to the process designer to specify reactive behavior in the event of data changes to one or several of the data collections involved in a process. Thus, ReaViz aims at enabling the easy, elegant specification of visual analytics applications where data dynamics is an important aspect.

Related works

Research in data visualization has produced several interactive platforms for data visualization [?]. Such platforms focus on the interaction between the human expert and a data set consisting of a completely known set of values, but they do not facilitate the inclusion of data analysis programs on the data.

In parallel, significant research and development efforts have been spent establishing models [?, ?, ?] and platforms for workflow specification and deployment. In recent years, moreover, scientific workflow platforms have received significant attention [?]. Such platforms are based on sligthly different premises than regular (business-oriented) workflows. Most notably, scientific workflows incorporate data analysis programs (or scientific computations more generally) as a native ingredient, and are meant to be specified by scientists, their end users. This contrats with business workflows, typically specified by some business analysts and en-

Process ProcInstance

ActivInstance Activity

Group User

ApplEntity acted by actors which do not need to have a global view of the process.

1:1 0:n 1:n 1:1 0:n 1:1 1:n 1:1 1:n 1:1 1:1 0:n 1:1 1:n VisualAttrs X Y
Scientific workflows have enabled the development of numerous applications. Thus, one could attempt to implement visual analytics applications as instances of scientific processes. However, the platforms we have surveyed have several shortcomings. First, the relationship between the data and the process specification is not well formalized. Second they are not easily extended to handle dynamic data sources, while preserving clear semantics.

A model and tool for reactive processes

Data model

The data model of a ReaViz application is a set of relations, which can be classified as belonging to three categories. Application-dependent relations model the data used by the specific visualization/analysis application. Separately, a set of workflow-related relations are used to capture the definition and instances of workflows. Finally, visualizationrelated relations capture the information items required by submitted to Eurographics/ IEEE-VGTC Symposium on Visualization (2009) the data visualization modules. An outline of the data model is provided in Figure ??. On the left, the entities Process, Activity and Group describe the process schemas (or process descriptions); the latter entity corresponds to groups of users. The next vertical colum comprises entities used for process instance bookkeeping, namely: process instance, activity instance, and specific users which belong to groups. An activity instance has a start date and an end date, as well as a status flag which can take the values: not_started, running and terminated. The status of a process instance can take similar values.

The ApplEntity entity refers in a generic manner to all entities which may actually be used by a given application. The relationship between ApplEntity and ActivityInstance captures is to be instantiated according to the specifics of each application; it represents the way activity instances are created or otherwise manipulated during process instance execution.

Finally, the entity VisualAttributes encapsulates a set of attributes frequently used in data visualisation applications, such as: (x, y) coordinates, width, height, color, label (a string), transparency, whether the data instance is currently selected by a given visualisation component etc.

Process model

We consider a simple yet expressive model for describing reactive processes. A reactive process is defined as a 5-tuple consisting of:

• a set of relations or queries R resulting from a data model; • a set of variables, where each variable v is a name, value pair; • a set of procedures, each procedure p being a computation unit implemented by some external, black-box software (developed outside the workflow engine by means in a language such as C++, Java or MatLab) that takes relations as parameters; • a process P; and • a set of compensating actions CA.

For the sake of conciseness, we leave out the formal specifications of these entities except for the reactive process:

RP ::= R * , v * , p * , P,CA * (1)
A compensating action CA specifies what should be done in the event that a set of tuples, denoted ∆R, are added to an application-dependent relation R during the execution of a process instance. Observe that we consider additions to R, regardless of the way the addition takes place: in particular, it may be due to a table assignment on R (thus, take place within the enactment of our processes), but it may also be due to some external event which modified R.

Let t ∆R be the moment when ∆R was received. Several options are possible.

1. Ignore ∆R for the execution of all processes which had started executing before t ∆R . The data will be added to R, but will only be visible for process instances having started after t ∆R . This recalls a process-granularity transactional model, where each process operates on exactly the data which was available when the process started. This is the default behavior. 2. Ignore ∆R for the execution of all activities which had started executing (whether they are finished or not) before t ∆R . However, for a process already started, instances of a specific activity which start after t ∆R may also use this data. 3. As a macro over the previous option and the process structure, one could wish for ∆R to be propagated to instances of all activities that are yet to be started in a running process. 4. Execute compensation work for all the terminated instances of a given activity. We can moreover specialize the behavior on whether we consider only activity instances whose process instances have terminated, only activity instances whose process instances are still running, or both. 5. Execute compensation work for all the running instances of a given activity. Obviously, in this case, the process instances to which the activity instances belong are all running.

Conclusion

We believe this formal approach will lead to cleaner and more scalable visual analytics applications, built upon well understood and reliably implemented components such as databases and workflow systems.

We need to continue integrating existing analysis and visualization components into this framework to better understand the implications of supporting reactive workflows for existing implementations.

submitted to Eurographics/ IEEE-VGTC Symposium on Visualization (2009)

Figure 1 :

 1 Figure 1: ReaViz data model.


Member, IEEE Niklas Elmqvist

Pierre Dragicevic

Jean-Daniel Fekete

Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation

Keywords: Visual exploration, visual queries, visual analytics, navigation, multivariate data, interaction

Scatterplots remain one of the most popular and widely-used visual representations for multidimensional data due to their simplicity, familiarity and visual clarity, even if they lack some of the flexibility and visual expressiveness of newer multidimensional visualization techniques. This paper presents new interactive methods to explore multidimensional data using scatterplots. This exploration is performed using a matrix of scatterplots that gives an overview of the possible configurations, thumbnails of the scatterplots, and support for interactive navigation in the multidimensional space. Transitions between scatterplots are performed as animated rotations in 3D space, somewhat akin to rolling dice. Users can iteratively build queries using bounding volumes in the dataset, sculpting the query from different viewpoints to become more and more refined. Furthermore, the dimensions in the navigation space can be reordered, manually or automatically, to highlight salient correlations and differences among them. An example scenario presents the interaction techniques supporting smooth and effortless visual exploration of multidimensional datasets.

INTRODUCTION

Developing novel visualization techniques has long been one of the core activities in information visualization research, and each installment of the annual conferences in the field introduces new visual representations for new types of data, each one more complex than the next. In light of this increasing complexity, scatterplots [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF][START_REF] Utts | Seeing Through Statistics[END_REF] remain one of the oldest and simplest yet most flexible and widely used visual representations of them all. Employed in standard statistical data graphics as well as in commercial visualization tools such as Spotfire and Tableau (formerly Polaris [START_REF] Stolte | Polaris: A system for query, analysis, and visualization of multidimensional relational databases[END_REF]), scatterplots form part of the basic vocabulary of data visualization.

Scatterplots visualize multidimensional datasets by assigning data dimensions to graphical axes and rendering data cases as points in the Cartesian space defined by the axes. However, even if we employ 3D graphics as well as point color, shape, and size as graphical properties, a standard scatterplot diagram can only visually represent a handful of data dimensions at a time. Most real-world datasets have many more dimensions. Beyond choosing a more complex visual representation, the standard solution to this problem is to only visualize a subset of the dataset dimensions in the scatterplot, giving control of the visual mapping to the user. Unfortunately, this approach provides no clear structure to the visual exploration process of the dataset and does not explicitly show the relations between different subsets of data dimensions. On the other hand, alternative visual representations for multidimensional data-such as parallel coordinates [START_REF] Inselberg | The plane with parallel coordinates[END_REF], dense pixel displays [START_REF] Keim | VisDB: Database exploration using multidimensional visualization[END_REF], or dimensional stacking [START_REF] Leblanc | Exploring N-dimensional databases[END_REF]-trade away some of the simplicity of scatterplots for more flexibility and visual expressiveness.

In this work, we are interested in preserving the simplicity and familiarity of scatterplots while addressing their shortcomings. We present a method based on scatterplots for visual exploration of multidimensional datasets using structured navigation in data dimension space, trading visual complexity for interactivity to reach a wider audience.

Following a review of existing work, this paper describes our scatterplot matrix navigation method as well as the purpose and motivation for the navigation techniques. We then describe how we integrate query sculpting functionality with the general scatterplot matrix metaphor. We also discuss dimension reordering to optimize grand tours of a dataset. We present a scenario using the tool for a multidimensional dataset and give some implementation details. The paper concludes with a summary and our plans for future work.

BACKGROUND

In the following subsections, we will give a basic background to the challenges of multidimensional visualization and how previous work has attempted to overcome the complexity of high-dimensional datasets. We then introduce the concept of interactive exploration of data as a possible way of managing this complexity, and discuss how animated transitions can help in this endeavor.

Multidimensional Visualization

Keim [START_REF] Keim | Information visualization and visual data mining[END_REF] presents a taxonomy of primarily multidimensional visualization techniques, listing categories such as standard 2D/3D displays, geometrically transformed displays [START_REF] Cleveland | Visualizing Data[END_REF], iconic displays [START_REF] Chernoff | Using faces to represent points in k-dimensional space graphically[END_REF], dense pixel displays [START_REF] Keim | VisDB: Database exploration using multidimensional visualization[END_REF], and stacked displays [START_REF] Leblanc | Exploring N-dimensional databases[END_REF]. Scatterplots are part of the first category, and are basic building blocks in statistical graphics and data visualization [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF][START_REF] Utts | Seeing Through Statistics[END_REF]. Here, data cases are drawn as points in the Cartesian space defined by two or three graphical axes, their positions determined by the data dimension assigned to each axis.

The case for employing scatterplots for multidimensional visualization lies in their relative simplicity in comparison to other multidimensional visualization techniques, familiarity among users, and their high visual clarity [START_REF] Tufte | The Visual Display of Quantitative Information[END_REF]. Multidimensional visualization tools that feature scatterplots, such as Spotfire, Tableau/Polaris [START_REF] Stolte | Polaris: A system for query, analysis, and visualization of multidimensional relational databases[END_REF], GGobi [START_REF] Swayne | GGobi: evolving from XGobi into an extensible framework for interactive data visualization[END_REF],

and XmdvTool [START_REF] Ward | XmdvTool: Integrating multiple methods for visualizing multivariate data[END_REF], typically allow mapping of data dimensions also to graphical properties such as point color, shape, and size. Still, the number of dimensions that a single scatterplot can reliably visualize is considerably less than many realistic datasets.

To remedy this, scatterplot visualizations often give control of mappings from data dimensions to graphical properties directly to the user, allowing the user to dynamically change the visualized dimensions. However, this approach yields very little structure to the visual exploration and provides no relations between the data dimensions. Instead, multiple plots can be arranged in a scatterplot matrix [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF] with the data dimensions on the rows and columns and each cell representing an individual scatterplot (see Figure 2 for an example scatterplot matrix for a simple dataset). While this approach does lend overview and structure to the exploration, the individual scatterplots in the matrix can appear a little like a set of image thumbnails with no indication how data points distribute between scatterplots when compared pairwise.

Our approach in this paper is to build on this very simple visual representation by adding structure and defining a navigation space for Fig. 1: Scatterplot matrix navigation for a digital camera dataset. The user is building queries for maximum camera resolution against price ranges and then studies them in relation to release year. The transition is performed using an animated 3D rotation.

Fig. 2: Example of a scatterplot matrix for a 7-dimensional car dataset.

exploring the data. A similar approach could be employed for other simple visual representations, such as sets of one-dimensional visualization widgets.

Grand Tour

As we have seen, high-dimensional datasets pose a problem for 2D scatterplots. To visit such dataset using a scatterplot limited to showing two dimensions at a time, Asimov describes a method called the "grand tour" [START_REF] Asimov | The grand tour: A tool for viewing multidimensional data[END_REF]. His idea is that a multidimensional dataset is fully visited when all the possible 2D projections have been seen, ignoring the symmetries and rotations. Therefore, a grand tour should visit a dense subset of all the possible 2D projections. This set is built according to criteria such as density, uniformity, continuity, linearity of the motion path, and some degree of user control.

Asimov describes several methods to compute approximations of a grand tour. However, Huber shows that it would require prohibitive time to extensively explore a high-dimensional dataset [START_REF] Huber | Projection pursuit[END_REF] so he advocates the projection pursuit method [START_REF]Toward a practical method which helps uncover the structure of the set of multivariate observations by finding the linear transformation which optimizes a new 'index of condensation[END_REF]. Projection pursuit has been designed to only show "interesting" aspects of high-dimensional spaces and has been adapted for visualization of such data [START_REF] Crawford | Projection pursuit techniques for visualizing high-dimensional data sets[END_REF].

Finding Interesting Planes

Several statistical methods have been designed to find the most interesting 2D planes and to create 2D views that best summarize a high-dimensional dataset; they are globally called dimensional reduction methods. Among these methods, Principal Component Analysis (PCA) is the simplest and most popular. The axis that maximizes the variance of all the projected points of the dataset is called the first component. The second component is orthogonal to the first and maximizes the variance of the projected dataset and so forth for all the other components up to n for an n-dimensional dataset. The plane defined by the first two components is frequently considered as the "most interesting" plane since it provides the best overview of the dataset in the sense of the largest variance. Furthermore, since PCA only considers linear projections, it fits well with the grand tour and projection pursuit ideas of important planes, whereas some other dimensional reduction methods find non-linear projections.

However, PCA suffers from several pitfalls, as described by Koren [START_REF] Koren | Robust linear dimensionality reduction[END_REF]: it is very sensitive to outliers and to artifacts in the data. Therefore, Koren proposes several variants of PCA that correct some of the issues but introduce parameters. Overall, all of these statistical methods find 2D planes. but have a very specific and restricted interpretation of the notion of "interest" and thus provide no guarantee that all the interesting planes will be found, nor that all planes found will actually be interesting.

Furthermore, and more importantly for our purpose, methods that compute 2D projections of high-dimensional spaces are beyond the understanding of casual information visualization users. As explained by Matthew Ericson during his keynote address at IEEE InfoVis 2007, scatterplots are considered too difficult to understand for readers of the New York Times, except when one of the axes is time. Understanding general scatterplots when the axes are meaningful is one thing, but understanding the meaning of axes that are linear combinations of attributes is beyond the skills of most people. Therefore, much research has focused on optimizing the navigation and selection of attributes.

Dimension Reordering

A simpler version of selecting "interesting" 2D planes is finding a rational order for exploring the dimensions of a dataset. Ankerst et al. [START_REF] Ankerst | Similarity clustering of dimensions for an enhanced visualization of multidimensional data[END_REF] approach dimensional reordering from the viewpoint of placing similar dimensions close to each other, deriving a set of similarity metrics for general data and proposing an algorithm based on a translation of the problem to a Traveling Salesman Problem (TSP). Rosario et al. [START_REF] Rosario | Mapping nominal values to numbers for effective visualization[END_REF] take advantage of the special properties of nominal data to find an optimal dimensional mapping that minimizes visual clutter. Similarly, Peng et al. [START_REF] Peng | Clutter reduction in multi-dimensional data visualization using dimension reordering[END_REF] generalize this to study visual clutter for a number of visualization techniques-scatterplots being one-and derive visualization-specific clutter measures. The rank-by-feature framework [START_REF] Seo | A rank-by-feature framework for unsupervised multidimensional data exploration using low dimensional projections[END_REF] presents a set of ranking criteria to the user and then makes the ranking of each projection of the dataset explicit, allowing the user to select among them.

Interactive Exploration

Interaction is a powerful tool for managing the complexity of highdimensional datasets, particularly when the analyst has little or no existing information about the dataset, or when the exploration goals are unclear. More formally, visual exploration [START_REF] Keim | Information visualization and visual data mining[END_REF][START_REF] Keim | Challenges in visual data analysis[END_REF] is the use of interactive visualization for exploratory data analysis [START_REF] Cleveland | Visualizing Data[END_REF][START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF][START_REF] Tukey | Exploratory data analysis[END_REF]. Some existing work consider interactive data exploration in scatterplots. The original PRIM-9 system developed by Tukey et al. [START_REF] Tukey | PRIM-9: An interactive multi-dimensional data display and analysis system[END_REF] allows for visualization of datasets of up to nine dimensions using a combination of projection and rotation followed by isolation and masking of the data into subsets.

High-dimensional filtering is a standard feature of information visualization systems through the use of dynamic queries [START_REF] Ahlberg | Dynamic queries for information exploration: An implementation and evaluation[END_REF][START_REF] Williamson | The dynamic HomeFinder: Evaluating dynamic queries in a real-estate information exploration system[END_REF] that allow for direct manipulation of conjunctive filters; for instance, they form a cornerstone of the Spotfire application suite. However, standard dynamic query controls are not integrated into the visualization.

Some systems support the integration of query and filtering operations as well as their feedback directly into the visualization. Highdimensional brushes [START_REF] Martin | High dimensional brushing for interactive exploration of multivariate data[END_REF] support selection and filtering in data space using visual queries. Theron [START_REF] Theron | Visual analytics of paleoceanographic conditions[END_REF] integrates axis-filtering [START_REF] Seo | Interactively exploring hierarchical clustering results[END_REF] in a a special-purpose parallel coordinate display. The DataMeadow [START_REF] Elmqvist | DataMeadow: a visual canvas for analysis of large-scale multivariate data[END_REF] is a canvas for analysis of multidimensional data using a visual query language that provide filtering in high-dimensional space. The Time-Searcher [START_REF] Hochheiser | Dynamic query tools for time series data sets: timebox widgets for interactive exploration[END_REF] use box-queries in time-series visualizations where the queries are visualized as rectangles on top of the visualization.

Animated Transitions in Visualization

According to the principle of congruence [START_REF] Tversky | Animation: can it facilitate?[END_REF], sudden changes in the layout of a visualization are disruptive since it prevents users from tracking changes over time. Animation can help solve that problem, although its utility for conveying complex information is uncertain.

Animation has long been an important part of data visualization; the rotation component of the PRIM-9 [START_REF] Tukey | PRIM-9: An interactive multi-dimensional data display and analysis system[END_REF] system is central to understanding the structure of the 3D scatterplots visualized in the system. Other examples include the animated rotations in cone trees [START_REF] Robertson | Cone trees: Animated 3D visualizations of hierarchical information[END_REF] that are used to show selection, the use of motion as a display dimension of its own in visualization [START_REF] Bartram | Filtering and brushing with motion[END_REF], and the animated transitions and state changes in the Many Eyes [START_REF] Viégas | Many Eyes: a site for visualization at internet scale[END_REF] system.

Recently, Heer and Robertson [START_REF] Heer | Animated transitions in statistical data graphics[END_REF] developed design guidelines for animated transitions between different data graphics as well as for value changes. While their transitions are basic interpolations of size, shape, and position, one key aspect of their approach is the use of stages in the animation to aid cognition. It seems that animated transitions are always better than instantaneous transitions when the motion of points is clearly understood. This is the case when changing one axis of a scatterplot: the points only move along one axis, so such animated transitions are easy to understand.

SCATTERPLOT MATRIX NAVIGATION

The purpose of this work is to support structured visual exploration of multidimensional data using scatterplots. Instead of letting the user choose mappings for the axes of a single scatterplot, we create one scatterplot per every combination of dimensions and arrange them in a large scatterplot matrix [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF][START_REF] Tukey | PRIM-9: An interactive multi-dimensional data display and analysis system[END_REF]. The whole matrix serves as an overview of the dataset and also defines a visual space for navigation, turning the visual exploration process into a navigation task. Transitions from one scatterplot to another is performed using a 3D rotation that is consistent with the overall navigation metaphor and that provides more natural cues than standard interpolated animation. Furthermore, we provide advanced visual queries using bounding volumes that allows the user to iteratively refine a query from different viewpoints using a set of query sculpting operations. Naturally, the order of columns and rows in the scatterplot matrix is significant, and can either be computed automatically as a function of the similarity between dimensions [START_REF] Ankerst | Similarity clustering of dimensions for an enhanced visualization of multidimensional data[END_REF] or the degree of visual clutter [START_REF] Peng | Clutter reduction in multi-dimensional data visualization using dimension reordering[END_REF], or manually by the user through drag-and-drop of rows and columns in an interactive mode [START_REF] Stolte | Polaris: A system for query, analysis, and visualization of multidimensional relational databases[END_REF][START_REF] Ward | XmdvTool: Integrating multiple methods for visualizing multivariate data[END_REF].

The primary tasks that we aim to support with our method is comparison and correlation of data dimensions in a dataset. These are compound tasks that consist of several smaller subtasks [START_REF] Amar | Low-level components of analytic activity in information visualization[END_REF]. The animated transitions explicitly support these tasks by favoring object constancy and consistency between adjacent scatterplots, and the 3D nature of the transition carries more semantic meaning than naive interpolation. Furthermore, the highly interactive nature of the method is designed to promote direct and evocative control and overview of the data, supporting both reconfigure and connect interaction [START_REF] Yi | Toward a deeper understanding of the role of interaction in information visualization[END_REF].

Visual Design

The two main visual components of our method consist of the current scatterplot and the scatterplot matrix. These components represent detail and overview of the dataset, respectively. The left side of Figure 1 shows this basic setup in our prototype implementation of the method.

The scatterplot component shows the currently viewed cell in the scatterplot matrix, together with the names and labels of the two displayed axes. The axes can have linear or logarithmic scales as controlled by the users. Data cases are drawn as points or boxes using a configurable colorscale that visualizes a user-selected dimension in the data.

The scatterplot matrix component (Figure 3) serves both as an overview and a tool for navigation. Miniature versions of the individual scatterplots are shown in the cells of the matrix, and the current position and potential navigation targets are highlighted using colors.

The overview can also be used to show the extents of the visual queries (Section 4), a history of previous exploration, as well as suggestions for future exploration (see Section 5 for more details on how to use dimension reordering algorithms for this purpose).

Animated Transitions

As stated above, navigation in the scatterplot matrix is restricted to orthogonal movement along the same row or axis in the matrix. In other words, one dimension in the focused scatterplot is preserved while the other changes. The change is visualized using an animated transition. Instead of simply interpolating the position of each point for the transition, we perform the transition as a 3D rotation. This gives some semantic meaning to the movement of the points, allowing the human mind to interpret the motion as shape [START_REF] Ullman | The Interpretation of Visual Motion[END_REF]. It also reinforces the metaphor of navigating in the space defined by the scatterplot matrix.

It is important to note that our technique is not based on 3D scatterplots. We use two dimensions for the visualization, and take advantage of the fact that the third dimension (depth) is hidden in the projection onto the 2D screen only for the actual transition to a new dimension assignment. In a way, this can be seen as a lazy or just-in-time allocation of graphical axes to data dimensions. Furthermore, the direction of the rotation-left or right for changing the horizontal axis versus up or down for the vertical axis-aids in the user's perception of their position and movement in the scatterplot matrix.

In accordance with the findings presented by Heer and Robertson [START_REF] Heer | Animated transitions in statistical data graphics[END_REF], the actual transition is performed as a three-stage animation: extrusion into 3D, rotation, and projection into 2D. This is necessary for perspective 3D projection of the scatterplot due to perspective foreshortening. 1 More specifically, given two currently visualized dimensions x and y and a vertical transition to a new dimension y ′ , these are the individual steps (see Figure 4 for a step-by-step visual sequence):

• Extrusion: The 2D scatterplot visualizing x and y is smoothly extruded to 3D where y ′ becomes the new depth coordinate for each data point. At the end of this stage, the 2D scatterplot has become 3D (Figure 4(a) and (b)).

• Rotation: The scatterplot is rotated 90 degrees up or down (depending on the relative position of y and y ′ in the scatterplot matrix), causing the axis previously pointing along the depth dimension to become the new vertical axis (Figure 4(c)).

• Projection: The 3D plot is projected back into 2D with x and y ′ as the new horizontal and vertical axes (Figure 4(d) and (e)). 1 For orthographic (parallel) projection, the animation can be directly performed as a rotation with no need for extrusion or projection.

Navigation

All navigation operations are restricted to orthogonal movement and are atomic transactions in that they never leave the main scatterplot visualization in an intermediate stage-when the user stops interacting, the visualization settles into one of the 2D scatterplots in the scatterplot matrix. This ensures that the navigation metaphor of navigating between 2D projections of the dataset is consistent. The user may still directly control the transition (using the "scratching" operation) in order to see details in the comparison and correlation of data points.

The interaction techniques supported in the framework have been designed to support all levels of the visual exploration task. Here follows a list of them (refer to Figure 5 for a graphical overview):

• Stepping: The user may utilize the arrow keys on the keyboard to step through the adjacent cells in the scatterplot matrix, giving the user direct and tangible control of the navigation in dimension space. The time the keyboard button is held down will govern the speed of the animated transition; a quick tap will result in a fast transition, a longer press will cause a slower one. The onscreen navigation bar (Figure 7(a)) also supports stepping in the same way, but is primarily intended for touch tablet interaction (see Section 7 for more information on this).

• Scratching: A little like crossfading between two records for hiphop music (also known as "scratching"), this interaction technique gives the user direct control of the transition by clicking the current matrix cell and moving the mouse towards the intended direction. The user can directly manipulate the animation (including pausing it and moving it back and forth) by dragging across the surface of the matrix overview. Releasing the mouse button will return the visualization to the nearest scatterplot.

• Path planning: Hovering with the mouse over the scatterplot matrix overview will show the shortest path from the current position to the indicated position in the matrix. Clicking will cause a sequence of animated transitions to be performed as the scatterplot visualization follows the planned path to the destination.

• Path drawing: Dragging the mouse on the matrix overview will draw a path on the surface of the scatterplot matrix. Once the button is released, the animation is performed in sequence.

• Hyperjump: Sometimes the user wants to jump to a different part of the scatterplot matrix without passing through the intermediate cells. Hyperjumping allows for a right-click on the overview matrix to perform this operation. Changing both dimensions at the same time will require two transitions, however; one horizontal and one vertical. It is important to note that, unlike simply changing the mapping of one or several axes for a standard scatterplot visualization, hyperjumping preserves the user's spatial cognition by making use of the scatterplot matrix.

Drill-Down, Reordering, and Overview Interaction

Beyond the navigation operations, we define several other interaction techniques. Drill-down to see details is central to visual exploration [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF], and we support this by an implementation of the excentric labeling [START_REF] Fekete | Excentric labeling: dynamic neighborhood labeling for data visualization[END_REF] technique as a resizable lens that can be moved on the surface of the main scatterplot (Figure 6). Another important feature is support for manual reordering of dimensions, akin to systems like Polaris [START_REF] Stolte | Polaris: A system for query, analysis, and visualization of multidimensional relational databases[END_REF] and XmdvTool [START_REF] Ward | XmdvTool: Integrating multiple methods for visualizing multivariate data[END_REF]. Our prototype implements this through simple drag-and-drop operations where the user can grab a row or a column in the overview matrix and place it at the desired position.

Finally, holding down a key (currently the Control key in our prototype) animates the overview scatterplot matrix to fill the screen; releasing the key scales the matrix back down to its original size. This large version allows for better viewing of details in the scatterplot miniatures as well as for high-precision navigation (such as when scratching). The matrix is rendered using semi-translucency so that it still shows the scatterplot visualization in the background.

QUERY SCULPTING

To facilitate visual exploration using the scatterplot matrix navigation method described above, we define an iterative filtering mechanism that we call query sculpting. Essentially, query sculpting allows for selecting data items in the main scatterplot visualization using 2D bounding volumes (boxes or convex hulls) and then iteratively refining the selection from other viewpoints while navigating the scatterplot matrix. The metaphor is a sculptor repeatedly chiseling away at the outline of a block of stone and rotating it until the sculpture is complete. Points can either be removed or grayed out. The technique is similar to high-dimensional brushing [START_REF] Martin | High dimensional brushing for interactive exploration of multivariate data[END_REF], but the iterative sculpting aspect is an integral part of our scatterplot matrix navigation method.

Our prototype implementation provides a number of color-coded queries that can be used during the visual exploration. A special query window (Figure 7(b))-modeled on the Photoshop image layers window-is used for selecting, naming, and clearing the queries. All query operations operate on the currently selected query, and clicking and dragging one query onto another will perform a union or intersection operation (by dragging using the left or right mouse button, respectively), similar to how layers are merged in Photoshop. Each query layer also gives a visual indication of the number and percentage of items currently selected by it. Queries are sculpted in the data space of the current dataset, two dimensions at a time (the dimensions currently viewed in the scatterplot visualization) using lasso or rubberband box selection on the 2D surface of the visualization. The selection may either be a union or an intersection operation (again by using the left or right mouse button) with the existing items in the current query.

The visual representation of queries conforms to the overall navigation metaphor and is extruded, rotated, and projected in 3D as the user navigates the scatterplot matrix. This helps the user by creating a smooth transition between the extents of each query in two adjacent scatterplots. Furthermore, to support a tighter definition of the selection areas, we support both rectangular boxes as well as convex hulls to bound the selected items for each query layer.

The concept of a grand tour [START_REF] Asimov | The grand tour: A tool for viewing multidimensional data[END_REF] automatically portraying a highdimensional dataset as a sequence of projections onto lowerdimensional subspaces is a potentially useful method for helping a user get an overview of a new dataset and see some of its salient features. In the context of our method, we could define the grand tour as an animated sequence of 2D scatterplot diagrams. However, in the interest of maintaining the interactive aspect of the visual exploration paradigm [START_REF] Keim | Information visualization and visual data mining[END_REF], we opt to instead reorder navigation space-i.e. the data dimensions in the scatterplot matrix-in such a way that salient features are highlighted, and continue to let users navigate themselves.

We adopt the systematic dimension reordering approach of Ankerst et al. [START_REF] Ankerst | Similarity clustering of dimensions for an enhanced visualization of multidimensional data[END_REF], where similar dimensions in a multidimensional dataset are placed next to each other. Our implementation uses an external TSP implementation 2 to compute an optimal ordering. Such implementations are typically able to find an optimal ordering for datasets of less than 100 dimensions in a reasonable time (i.e. a few seconds at most).

The use of a scatterplot matrix allows us to have independent row and column orderings. In our method, it makes sense to utilize this fact and display similarity on the column and dissimilarity on the row order.

There are a number of suitable similarity measures for our problem depending on what similarity features to highlight; we use the absolute correlation of pairwise dimensions and its inverse for the dissimilarity metric D and the similarity metric S, respectively:

D X,Y = |ρ X,Y | (1) S X,Y = 1 -|ρ X,Y | (2)
ρ X,Y = cov(X,Y ) σ X σ Y (3)
In our prototype implementation, users can choose to reorder the dimensions of a dataset after loading it into the application. This will cause the navigation space to be arranged for structured visual exploration: horizontal movement explores scatterplot sequences of similar dimensions, whereas vertical movement shows dissimilar dimensions.

IMPLEMENTATION NOTES

Our prototype implementation of scatterplot matrix navigation (SCATTERDICE) is built in Java and uses the InfoVis Toolkit [START_REF] Fekete | The InfoVis Toolkit[END_REF] for all dataset management, loading, and reordering functionality. Rendering is performed using OpenGL through JOGL. Performance is interactive even for very large datasets with framerates of over 100 FPS.

The animated transitions are implemented using a three-stage sequence, as outlined above. The extrusion and projection steps simply assign data values from the new dimension to the depth (z) coordinate using an animated parameter as a weight, and the rotation is performed by rotating the 3D camera. Instead of keeping track of the camera orientation, moving to a new cell in the scatterplot matrix simply resets the camera to its default and swaps the axis mappings as needed.

Many implementation details that are not critical to the general idea of the framework remain open, including the choice of graphical marks (2D points, 3D boxes or 3D spheres), the use of perspective or parallel projection, and whether or not to start stepping animations immediately when the user presses a key or to wait until the keypress has finished. In our prototype, we have turned as many of these choices as possible into options configurable by the user. 2 Concorde, see http://www.tsp.gatech.edu/concorde/ Fig. 8: Wacom CintiQ 21UX graphical tablet used for the visual exploration scenario, here shown running our prototype implementation.

USAGE SCENARIO

We now demonstrate how our method could be used for visual exploration in scatterplot matrices. We will use a very basic scenario based on exploring a digital camera dataset in order to find a suitable camera given an initially loose set of constraints. The operations involved in this simple task are common to general multidimensional visual exploration for both expert and novice users alike.

We will follow Liza, a visualization analyst who is trying to make an informed decision on buying a digital camera using our prototype implementation for multidimensional visual exploration. Liza uses a graphical tablet with our tool to make the interaction smooth and effortless (Figure 8). She uses a camera dataset built from online camera shopping and review sites.

Liza has no previous knowledge of digital cameras, and so her initial exploration goals are very fuzzy and she would like to let the visual exploration process itself guide and inform her selection. All she knows is her approximate budget-at most around $1000-and that she would like an all-round camera with good image resolution that she can use to take both nature shots as well as portraits.

Loading up a digital camera dataset containing 1039 cameras categorized in 13 dimensions (one being the name, the rest categorical or numerical) in the scatterplot navigation application, Liza is confronted with the main interface of the application. Since price and resolution is one of her most important constraints, she hyperjumps to the scatterplot showing maximum resolution on the vertical axis and price on the horizontal axis. She immediately notices that digital cameras seem to cluster into four different price ranges-between 0 and $1000, $1000-$3000, $3000-$6000, and $6000 and above-and she uses the lasso tool to create four different queries, one for each of the four clusters (see the leftmost plot of Figure 1). She notices that price does not appear to have much correlation with maximum resolution, since even the cheapest cameras span the whole range of resolutions-except for the highest price range query (the blue one, containing 3 of the total 1039 cameras in the dataset), that make up the high resolution range.

Trying to get a feel for the dataset, Liza steps to the right in the scatterplot matrix, giving rise to a smooth horizontal rotation (the center scatterplot in Figure 1) that finishes with the release year of the cameras on the horizontal axes of the scatterplot (rightmost in Figure 1).

Here she immediately sees that the cheapest category of cameras (the red one, containing 900 cameras or 87% of the dataset) is spread over the whole range of release years. However, it appears that as digital cameras have matured, the newer and more expensive categories Liza knows that weight is an important factor for her choice, so she drags and drops the weight column to the right of the current column in the scatterplot matrix. She then steps to the right, bringing weight onto the horizontal axis through another smooth horizontal rotation. Figure 9(a) shows this scatterplot. It appears that the red (low-budget) and green (upper-budget) queries are spread all over the weight range, whereas yellow (mid-budget) are compact cameras with low weight, and the blue (high-budget) query are relatively heavy SLR-type professional cameras.

Intrigued by the mid-level cameras designated by the yellow query, Liza decides to change her exploration goals somewhat and incorporate both the red and yellow queries in her search even though the high $3000 range of the yellow query set is beyond her budget. Since she wants to be able to take both close-up portrait and long-range nature shots, she next navigates to the scatterplot showing the tele and wide zoom measurements through path-planning. This gives her some continuity to see how the four queries distribute as the tool smoothly animates to the new position in the scatterplot matrix. Figure 9(b) shows the destination scatterplot. Interestingly enough, the two higher price ranges (green and blue) do not have high zoom capabilities. Liza drills down into the dataset using the excentric label lens and realizes that this is because the green and blue cameras are primarily system cameras that have interchangeable lenses and come equipped with a very basic allround lens (if they have a lens at all).

Moving on, Liza sculpts both of the red and yellow queries to include only cameras with both high tele and wide zoom. She then drags the maximum resolution row to the position above the current row and then scratches up to bring the new dimension into view. Figure 9(c) shows the new view in the application. Disappointingly enough, the yellow mid-range query that caught Liza's eye previously all have low maximum resolutions. However, Liza now feels that she has enough knowledge of the dataset to perform her search in earnest.

Clearing all queries, Liza hyperjumps back to the nearest price dimension and uses the lasso tool to build a new red query containing both the low and mid-level budget cameras (1023 cameras). She then proceeds to sculpt her query through a succession of scatterplots, selecting only cameras with more than 3 megapixel resolution (489 cameras), then cameras that weigh less than 1000 grams (477 cameras), and finally cameras with more than 400 mm focal length (15 cameras). Navigating back to the maximum resolution plot, she refines the query to select only the two cameras with the highest megapixel capability. Figure 10 shows her resulting scatterplot on the price and tele zoom dimensions.

Drilling down into the dataset using the excentric label lens, Liza finds out that these two cameras are the Leica V-LUX 1 ($529) and the Panasonic Lumix DMC-FZ50 ($149). After having read reviews for both of these, Liza settles for the Leica as her camera of choice.

CONCLUSIONS AND FUTURE WORK

In this paper, we have proposed a coherent design that uses scatterplots for exploring multidimensional datasets. Its benefit lies in the seamless integration of several components that all support the basic tasks of comparing and correlating dimensions in this kind of dataset. More specifically, the contributions of this paper are the following:

• A unified design for structured visual exploration of multidimensional data in scatterplot matrices using 3D animated transitions,

• A set of carefully designed interaction techniques for navigation in scatterplot matrix space,

• An approach for iterative refinement of queries by bounding volume sculpting that is integral to the scatterplot navigation metaphor, and

• A method for dimension reordering of scatterplot matrix rows and columns designed to show correlation and disparities, respectively, between individual dimensions in the dataset.

In the future, we envision validating this design through empirical evalution. User evaluation is difficult for such broad tasks as visual exploration, so we anticipate performing qualitative or longitudinal studies. We are also interested in investigating similar ways of turning a complex visualization into navigable sequences of simpler visualizations.

Fig. 4 :

 4 Fig. 4: Stage-by-stage overview of the scatterplot animated transition.

Fig. 3 :

 3 Fig. 3: Scatterplot matrix component used for overview and interaction in our prototype implementation.

Fig. 5 :

 5 Fig. 5: Overview of the navigation operations supported by the scatterplot matrix navigation method.

Fig. 6 :

 6 Fig. 6: Excentric labeling lens showing labels for selected points (indicated by hulls and a red colorscale; unselected points are blue).

Fig. 7 :

 7 Fig. 7: User interface components: (a) Navigation bar. Provides the same navigation functionality as the keyboard arrow keys and is especially suitable for interaction when using a touch tablet. (b) Query layer control box. Each line shows the query name and color as well the number and percentage of items selected by it.

Fig. 9 :

 9 Fig. 9: Digital camera dataset visual exploration session: (a) weight distribution; (b) wide and tele zooms; (c) maximum resolution.

Fig. 10 :

 10 Fig. 10: Final visual exploration result for the digital camera dataset. The red circle denotes the two finalist cameras.

•

  Niklas Elmqvist is with INRIA in Paris, France, E-mail: nickelm@acm.org.• Pierre Dragicevic is with INRIA in Paris, France, E-mail: dragice@lri.fr.

	• Jean-Daniel Fekete is with INRIA in Paris, France, E-mail:
	jean-daniel.fekete@inria.fr.
	Manuscript received 31 March 2008; accepted 1 August 2008; posted online
	27 October 2008.

For information on obtaining reprints of this article, please send e-mail to: tvcg@computer.org.

ACKNOWLEDGEMENTS

This work was supported in part by the joint Microsoft Research/INRIA ReActivity project. Thank you to Nathalie Henry for her comments on this manuscript.


published or not. The documents may come

Early development, recruitment and life history trajectory in long-lived birds

Emmanuelle Cam, Lise