Anne-Marie Kermarrec

Afshin Moin

Energy Models for Drawing Signed Graphs *

Graph drawing is the pictorial representation of graphs in a multi-dimensional space. Energy models are the prevalent approach to graph drawing. In this paper, we propose energy models for drawing signed unidirectional graphs where edges are labeled either as positive (attractive) or as negative (repulsive). The existent energy models do not discriminate against edge sign. Hence, they do not lend themselves to drawing signed graphs. We suggest a general equation for signed energy models by proposing a dual energy model for graphs containing uniquely negative edges, and combining it linearly with the primary model. We then concentrate on revealing the community structure of social network graphs (sociograms) where edge sign represents the state of relationship between two individuals. In this goal, Signed LinLog model is built based on LinLog model whose clustering properties for unsigned graphs is already known. The properties of Signed LinLog model are outlined analytically, and its synthetic and real layouts are presented.

Introduction

The drawing of a graph called layout is the graphical representation of the graph where each vertex is assigned with a coordinate vector in a metric space. Graph drawing has applications in many branches of science needing information visualization like cartography, bioinformatics and social network analysis. Large scale Internet applications can also benefit from graph drawing to assign hosts with virtual network coordinates reflecting Internet latency [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF].

Energy-based (also known as force-based1 ) technique [START_REF] Hall | An r-dimensional quadratic placement algorithm[END_REF][START_REF] Eades | A heuristic for graph drawing[END_REF][START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF][START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF][START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF][START_REF] Noack | Energy models for graph clustering[END_REF] is a pretty popular approach to graph drawing thanks to advantages like good layout quality, ease of implementation and code flexibility. The basic assumption in these models [START_REF] Eades | A heuristic for graph drawing[END_REF][START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF][START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF][START_REF] Noack | Energy models for graph clustering[END_REF] is that there is an attraction force between the connected vertices while all vertices repulse each other. This line of modeling captures all edges as a measure of attraction, while in many contexts like social networks [START_REF] Hage | Structural Models in Anthro-pology[END_REF], vertices (users) express positive or negative attitude towards each other. Consequently, the existing models place connected vertices close to each other even if some edges reflect dislike. While numerous works have studied positive interactions in social networks, there has been less research about signed networks [START_REF] Newman | The structure and function of complex networks[END_REF]. In particular, there is a big gap in the literature of drawing signed graphs. We are only aware of the work in [START_REF] Kunegis | Spectral analysis of signed graphs for clustering, prediction and visualization[END_REF] shortly investigating prediction, clustering and visualization in signed graphs by generalizing the spectral approaches for signed graphs. However, their visualization technique has not the clustering property we seek. This lack of literature about signed graph visualization motivated us to suggest energy models for drawing unidirectional signed graphs. In these models, positive edges are interpreted as attraction between vertices while negative edges denote repulsion. In this paper we first give the summary of the related work in 2. Notations are defined in Section 3. In Section 4, we suggest a dual formulation for a popular class of energy models aimed at drawing graphs containing only negative edges. This model is linearly combined with its primary to suggest a general equation for signed energy functions. Precisely because we are interested in drawing sociograms where clusters indicate communities, we emphasize how to draw clustered layouts of signed graphs. The clustering property of energy models has recently been elaborated by Noack [START_REF] Noack | Energy models for graph clustering[END_REF]. In sprite of this work, we suggest the Signed LinLog model, and analytically derive its clustering properties. The behavior of the model is clarified in Section 5 presenting a toy example as well as layouts of real data. Section 9 concludes the paper.

Related Work

The problem of drawing unsigned graphs has been addressed in several works [START_REF] Hall | An r-dimensional quadratic placement algorithm[END_REF][START_REF] Eades | A heuristic for graph drawing[END_REF][START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF][START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF][START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF][START_REF] Noack | Energy models for graph clustering[END_REF]. Energy-based technique is the prevalent approach to graph drawing. This approach has several advantages like good layout quality, ease of implementation and flexibility (easily modifiable codes). It is composed of two components: the energy model and the optimization algorithm. The energy model is a heuristic function defining the energy of layouts. The optimal layout is that with minimum energy. The role of the optimization algorithm is to find the local minimum of the energy function. Energy-based approaches differ in the energy function and the optimization algorithm they use. Two main disadvantages associated with energy models are the difficulty of finding the global minimum of the energy function and high running time for very large graphs. In this approach, vertex coordinates are determined by minimizing a heuristic energy function through an iterative optimization algorithm. The Spring Embedder method [START_REF] Eades | A heuristic for graph drawing[END_REF] was one of the earliest variants of energy models in which a graph is considered as a collection of electrically charged rings connected through spring edges. Therefore, all vertices repulse each other, while the attraction exists uniquely between connected vertices. The equilibrium is sought between all attractive and repulsive forces by iteratively modifying vertex coordinates, minimizing the energy after a number of cycles. The energy minimization algorithm of this work had high complexity rendering it inefficient for large graphs. Fruchterman and Reingold [START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF] refined this algorithm by first computing the net force exerted on each vertex, then moving it in the direction of the net force by an extent limited by a decreasing function of cycle number. The scalability was further enhanced by Tunkelang [START_REF] Tunkelang | Jiggle: Java interactive graph layout environment[END_REF]. The author adopts the algorithm by Barnes and Hut [START_REF] Barnes | A hierarchical o(nlogn) force-calculation algorithm[END_REF] using a quad-tree to approximate the repulsion force of many distant vertices as a single one. In this paper, we also use this algorithm to optimize our energy functions. Kamada and Kawai [START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF] model the graph as a system of springs acting according to Hook's Law. A spring is assumed between every two vertices whose rest length is proportional to the graph-theoretical distance between the end-points and whose spring constant is inversely proportional to the square of this distance. Hall [START_REF] Hall | An r-dimensional quadratic placement algorithm[END_REF][START_REF] Koren | Ace: a fast multiscale eigenvectors computation for drawing huge graphs[END_REF] introduces a quadratic energy function for connected vertices, but puts geometrical constraints on the vertex coordinates in order to prevent them from overlapping on a single point. Lately, Koren and C ¸ivril [START_REF] Koren | The binary stress model for graph drawing[END_REF] have proposed a binary stress model by linking up the stress and the electrical spring models. A survey of force-based models is available in [START_REF] Brandes | Drawing on physical analogies[END_REF].

All these works have the goal of generating layouts in a way that the readability criteria for aesthetic drawing is satisfied. These criteria are in general uniform distribution of vertices, minimum edge crossing and uniform edge length. They lead to increased layout clarity, but prevent the appearance of clusters. Recently, Noack [START_REF] Noack | Energy models for graph clustering[END_REF] has elaborated the problem of clustering energy models. The author argues that energy models are in general not clustering, and suggests the LinLog model as the special model drawing layouts where convex subgraphs are plot separately, and the distance between clusters of a bipartition decreases with the number of connecting edges.

None of the works described above refer to signed graph drawing. To the best of authors' knowledge, there is only [START_REF] Kunegis | Spectral analysis of signed graphs for clustering, prediction and visualization[END_REF] addressing shortly the problem of signed graph drawing using spectral approaches. Though, their approach does not have our desired clustering property.

Definitions

A d-dimensional layout p of a graph G = (V, E) is a mapping of vertices into a Euclidean space M : V -→ R d where ∀v ∈ V is assigned with a coordinate vector p v . The Euclidean distance between u and v is denoted by p u -p v . Here, we clarify the clustering property by introducing the notions of density and distance. We denote unsigned graphs by G = (V, E) where V is the set of vertices and E the set of edges. A subgraph of an unsigned graph is considered as a cluster, if it contains lots of internal edges while few edges to the rest of the graph. There exist many different clusterings for a particular graph. To judge the clustering quality between two disjoint clusters, a coupling measure is defined between them. The best clustering is the one minimizing the coupling. One widely used coupling measure between two clusters V 1 and V 2 is the cut:

cut[V 1 , V 2 ] = E V 1 ×V 2 ,
where E V 1 ×V 2 represents the set of edges between V 1 and V 2 . The cut has the disadvantage of preferring biased clusters, i.e. one huge cluster against a tiny one. The normalized cut also known as density can remove this drawback:

density(V 1 , V 2 ) = cut[V 1 , V 2 ] |V 1 | |V 2 | .
Cut and density are coupling measures for generation of graph bipartitions2 . Other measures like Newman Modularity [START_REF] Newman | Analysis of weighted networks[END_REF] may be used to generate clusterings with more than two clusters. We present three definitions of distance for F ⊂ V (2) and layout p widely used in graph geometry. The arithmetic mean distance is the linear average of the Euclidean distance between all vertex pairs:

arith(F, p) = 1 |F | {u,v}∈F p u -p v .
The geometrical mean distance and the harmonic mean distance of F are non-linear averaging functions to compute distance:

geo(F, p) = |F | {u,v}∈F p u -p v , harm(F, p) = |F | {u,v}∈F 1 pu-pv .
In clustered layouts the vertices of each cluster are plot close to each other. For unsigned graphs with attractive edges the distance between clusters must be in inverse relation with their density. For unsigned graphs with repulsive edges, where a cluster contains vertices having negative edges towards another subset of vertices, the distance between clusters must vary directly with their density.

Here, we generalize the above definitions to signed graphs. We represent signed graphs with G s = (V, E), where

E = E + ∪ E -, E + ∩ E -= ∅.
The set of positive and negative edges are denoted by E + and E -, respectively. In signed graphs, a cluster is a subgraph containing a large number of internal positive edges and few internal negative edges. An optimal bipartition of a signed graph maximizes both the number of positive internal edges of the partitions and the number of negative edges between them. The positive and negative cut between two disjoint clusters V 1 , V 2 ⊂ V indicate the number of connecting positive and negative edges, respectively:

cut + [V 1 , V 2 ] = E + V 1 ×V 2 , cut -[V 1 , V 2 ] = E - V 1 ×V 2 .
Consequently, positive density and negative density between two disjoint clusters are defined as:

density + (V 1 , V 2 ) = cut + [V 1 , V 2 ] |V 1 | |V 2 | , density -(V 1 , V 2 ) = cut -[V 1 , V 2 ] |V 1 | |V 2 | .
In this paper, we also introduce three new definitions of distance for signed layouts appearing further in the theorems. The positive arithmetic mean distance for F ⊂ V (2) and layout p is defined as:

arith + (F, p) = {u,v}∈F λ uv p u -p v E + F + |F | , λ uv = 2 if {u, v} ∈ E + F 1 otherwise = E + F arith(E + F , p) + |F | arith(F, p) E + F + |F |
, where E + F is the set of positive edges of F . It is a linear averaging function where positivelyconnected vertex pairs are counted twice. We define in the same way the negative geometrical mean distance:

geo -(F, p) = E - F +|F | {u,v}∈F λ uv p u -p v , λ uv = 2 if {u, v} ∈ E - F 1 otherwise = E - F +|F | geo(E - F , p) E - F geo(F, p) |F | ,
where E - F is the set of negative edges of F . Finally, the negative harmonic mean distance of F on layout p is defined as:

harm -(F, p) = E - F + |F | {u,v}∈F λ uv pu-pv , λ uv = 2 if {u, v} ∈ E - F 1 otherwise = E - F + |F | E - F harm(E - F ) + |F | harm(F,p) .
Negative edges between V 1 and V 2 are weighted twice as much in geo -(F, p) and harm -(F, p). These definitions can be generalized further (as in Corollary 4.1 and Corollary B.2) to count positive and negative edges or disconnected pairs as many times as desired. In clustered signed layouts, the distance between two clusters increases with negative density and decreases with positive density.

Energy Models for Clustering Signed Graphs

The conventional work line in the designation of energy models is to suppose disconnected vertices repulse each other until infinity. The attraction force exists wherever an edge exists between vertices, and the system rests when the equilibrium between these forces is achieved. For layout p of an unsigned graph G = (V, E + ) with attractive edges, many of the known energy models [START_REF] Noack | Energy models for graph clustering[END_REF][START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF][START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF] have the following form:

U = {u,v}∈E + f ( p u -p v ) + {u,v}∈V (2) g( p u -p v ),
where f ( p u -p v ) represents the attraction energy, and g( p u -p v ) the repulsion energy. In this conventional work line, disconnected subgraphs repulse each other towards infinity. Reminding the small world phenomenon in human societies [START_REF] Milgram | The small world problem[END_REF], this infinite repulsion is questionable in social network visualization, as there is no convincing reason to count two disconnected communities of people as infinitely far from each other. In other words, the absence of interactions between two communities suggests ignorance rather than antagonism.

We introduce a new category of energy models which can be viewed as the dual formulation of the actual models. The idea is that each vertex establishes links to other vertices only based on a distrust relation. In contrast to the conventional models, we assume there is an attraction force between every two different vertices while connected vertices repulse each other. For layout p of an unsigned graph G = (V, E -) with repulsive edges, this dual model has the general form of:

U Dual = {u,v}∈V (2) f ( p u -p v ) + {u,v}∈E - g( p u -p v ).
The particular advantage of this model is to separate clusters of vertices based on their similar dislike habits. In a connected bipartite graph for example, the two partitions of vertices are plot apart from each other, with the vertices of each partition overlapping on the same point. Though, this model may be criticized in the inverse way of conventional models. Namely, there is no reason for two disconnected vertices to be extremely close to, even overlapping, each other. In addition, drawing models are required to avoid vertex overlap as one of the primitive requirements in graph embedding. Fortunately, a linear combination of conventional models with their dual can lift the drawbacks of both, and satisfy the vertex non-overlap condition. In addition, while primary and dual models can handle either positive or negative edges, the combined version upgrades the modeling power to signed graphs. For a signed graph G s = (V, E) we define:

U SignedGraph = {u,v}∈E + f ( p u -p v ) + {u,v}∈E - g( p u -p v ) + (1)
{u,v}∈V (2)

f ( p u -p v ) + g( p u -p v ).
Other possible forms are suggested in Section 6. To have an intuition into the behavior of the model, lets consider the simple example of a graph with two vertices. If the vertices are disconnected, the minimum energy of the system is a solution to f ( p u -p v ) + g( p u -p v ) = 0. In case they are positively or negatively connected, the minimum energy layout would correspond to 2f ( p u -p v )+g( p u -p v ) = 0 and f ( p u -p v )+2g( p u -p v ) = 0, respectively. It is seen from this simple example that the model places disconnected vertices within a neutral distance from each other, while positively/negatively connected vertices are put closer/further w.r.t. the neutral distance. The ability to draw disconnected graphs is an advantage of signed energy models as conventional energy models have difficulties with handling disconnected graphs. Recalling we are interested in clustered layouts, we focus on the Signed LinLog model whose clustering properties of the unsigned version is proven in [START_REF] Noack | Energy models for graph clustering[END_REF]. LinLog [START_REF] Noack | Energy models for graph clustering[END_REF] and Dual LinLog models are defined as follows:

U LinLog = {u,v}∈E + p u -p v - {u,v}∈V (2) ln p u -p v . U DualLinLog = {u,v}∈V (2) p u -p v - {u,v}∈E - ln p u -p v .
Signed LinLog is then defined as:

U SignedLinLog = {u,v}∈E + p u -p v - {u,v}∈E - ln p u -p v + (2)
{u,v}∈V (2)

p u -p v -ln p u -p v .
In the rest of this section we derive the clustering properties of this new model. Theorem 4.1 states that a layout with minimum Signed LinLog energy is the best trade-off between the minimization of the positive arithmetic mean and the maximization of the negative geometrical mean of the whole vertices. The former necessitates putting the vertices close to each other, while the latter is likely to move them away. The point is that positive edges have more weight in arith + (V (2) , p), but negative edges are weighted more in geo -(V (2) , p). Then, shortening positive edges results in more decrease in arith + (V (2) , p) while lengthening negative edges causes more increase in geo -(V (2) , p). Consequently, positive edges become shorter in average than the mean distance between all vertices, and negative edges become longer than that. This results in friends lying close to each other while foes move apart.

Theorem 4.1 If p 0 is a drawing of the signed graph G s = (V, E) with minimum Signed LinLog energy, p 0 also minimizes arith + (V (2) ,p) geo -(V (2) ,p) .
Proof Let p 0 be a layout with minimum Signed LinLog energy.

If {u,v}∈E + p 0 u -p 0 v + {u,v}∈V (2) p 0 u -p 0 v = c, then p 0 is a solution to: minimize(- {u,v}∈E - ln p u -p v - {u,v}∈V (2) ln p u -p v ) subject to {u,v}∈E + p u -p v + {u,v}∈V (2)
p u -p v = c.
The above expression may be reformulated in the form of minimize -ln(geo

E - (E -, p)geo V (2)
(V (2) , p)).

Since E -+ V (2) exp(x) is an increasing function of x, the minimization of this expression is equivalent to minimize exp(ln

1 geo -(V (2) ,p)
). Multiply the numerator by the constant arith + (V (2) , p), and rewriting the restriction, we obtain:

minimize arith + (V (2) , p)
geo -(V (2) , p)

subject to arith + (V (2) , p) = c E + + V (2)
.

Suppose there exists a layout q 0 of G s with minimum Signed LinLog energy for which arith + (V (2) ,q 0 ) geo -(V (2) ,q 0 ) < arith + (V (2) ,p 0 ) geo -(V (2) ,p 0 ) .

We can always define a scaling

q 1 = c (|E + |+ V (2) )arith + (V (2) ,q 0 )
q 0 for which arith + (V (2) , q

1 ) = c |E + |+ V (2)
, but arith + (V (2) ,q 1 ) geo -(V (2) ,q 1 ) = arith + (V (2) ,q 0 ) geo -(V (2) ,q 0 ) < arith + (V (2) ,p 0 ) geo -(V (2) ,p 0 )

. This is a contradiction.

Hence q 0 does not exist and the restriction may always be removed.

Similar theorems exist for LinLog and Dual LinLog models:

Theorem 4.2 Let G = (V, E + ) be a connected graph, and let p 0 be a layout of G with minimum LinLog energy. Then p 0 also minimizes arith(E + ,p) geo(V (2) ,p)

.

Theorem 4.3 If p 0 is a drawing of a graph G = (V, E -)
with minimum Dual LinLog energy,

p 0 also minimizes arith(V (2) ,p)
geo(E -,p)

.

Adding multiplicative constants to the LinLog model has only a zooming effect, but does not change its minimum [START_REF] Noack | Energy models for drawing clustered small-world graphs[END_REF]. However, the minimum of Signed LinLog model depends on the constants. It can be proved in the same way as in Theorem 4.1 that: Corollary 4.1 The minimization of Weighted Signed LinLog energy defined as

U W eigthedSignedLinLog = {u,v}∈E + k 1 p u -p v - {u,v}∈E - k 3 ln p u -p v + {u,v}∈V (2) p u -p v -k 3 ln p u -p v ,
is equivalent to the minimization of arith k 1 + (V (2) ,p) geo k 2 -,k 3 d (V (2) ,p)

.

arith k 1 + (V (2)
, p) is defined similar to arith + (V (2) , p), but positive edges are counted (k 1 + 1) times. In the same way, disconnected pairs are weighted k 3 times as much in geo k 2 -,k 3 d (V (2) , p), while negative edges are counted (k 2 + k 3 ) times. These three constants determine how much positive/negative edges are shorter/longer in average w.r.t. the mean neutral distance between all vertices. Specifically in large sparse graphs, encountered frequently in social networks, the adjustment of these parameters is helpful to improve the revelation of clusters.

While Theorem 4.1 explains why Signed LinLog reveals the clusters, Theorem 4.4 is about the distance interpretability in bipartition layouts. It states that the negative harmonic mean distance between two partitions of a signed graph in a one-dimensional layout with minimum Signed LinLog energy varies directly with the negative density between them, and inversely with their positive density. Theorem 4.4 Let p 0 be a one-dimensional drawing of the signed graph

G s = (V, E). Let (V 1 , V 2 ) be a bipartition of V such that the vertices in V 1 have smaller positions than the vertices in V 2 (i.e. ∀v 1 ∈ V 1 , ∀v 2 ∈ V 2 : p v 1 < p v 2 ). Then: harm -(V 1 × V 2 , p 0 ) = 1 + density -(V 1 , V 2 ) 1 + density + (V 1 , V 2 ) .

Model Minimization equivalence One-dimensional bipartition

LinLog [START_REF] Noack | Energy models for graph clustering[END_REF] minimize arith(E + ,p) geo(V (2) ,p)

harm(V 1 × V 2 , p 0 ) = 1 density + (V 1 ,V 2 )
Dual LinLog minimize arith(V (2) ,p)

geo(E -,p)

harm(E - V 1 ×V 2 , p 0 ) = density -(V 1 , V 2 )
Signed LinLog minimize arith + (V (2) ,p) geo -(V (2) ,p)

harm -(V 1 × V 2 , p 0 ) = 1+density -(V 1 ,V 2 ) 1+density + (V 1 ,V 2 )
Table 1: Summary of the clustering properties of primary, dual and signed LinLog.

Proof Let p 0 be a layout with minimum Signed LinLog energy. If we add d ∈ R to the coordinates of the vertices of V 1 in a way that the largest coordinate of the vertices in V 1 remain less than the smallest coordinate of the vertices in V 2 , the Signed LinLog energy becomes:

U SignedLinLog (d, p 0 ) = {u,v}∈E + V (2) 1 ∪E + V (2) 2 |p u -p v | - {u,v}∈∪E - V (2) 1 ∪E - V (2) 2 ln |p u -p v | + {u,v}∈V (2) 1 ∪V
(2) 2 |p u -p v | -ln |p u -p v | + {u,v}∈E + V 1 ×V 2 (|p u -p v | + d) - {u,v}∈E - V 1 ×V 2 ln(|p u -p v | + d) + {u,v}∈V1×V2 |p u -p v | + d -ln(|p u -p v | + d).
Since p 0 is a layout with minimum energy, the above function has a minimum at d = 0, i.e. U SignedLinLog (d = 0, p 0 ) = 0. Then:

E + V 1 ×V 2 + |V 1 × V 2 | = {u,v}∈E - V 1 ×V 2 1 |p u -p v | + {u,v}∈V 1 ×V 2 1 |p u -p v | .
Replacing the right side with

|V 1 ||V 2 |+ E - V 1 ×V 2 harm -(V 1 ×V 2 ,p 0 )
and

|V 1 × V 2 | with |V 1 | |V 2 |, the result is ob- tained.
Although Theorem 4.4 does not generalize to more than one dimensions, it remains approximately true for 1+ dimensional layouts of clusterizable bipartitions. Refer to Appendix B for more details of the approximation. Notice for graphs containing a higher number of clusters, there is in general no 2D or 3D drawing satisfying the clustering property between every two clusters. Namely, there exists no configuration where the distance between every two clusters follow the clustering criterion, without conflicting the geometrical constraints imposed by the triangle inequality w.r.t. a third cluster. Equivalent theorems for LinLog and Dual LinLog models are: Theorem 4.5 Let G = (V, E + ) be a connected graph, and let p 0 be a one-dimensional drawing of G with minimum LinLog energy. Let (V 1 , V 2 ) be a partition of V such that the vertices in V 1 have smaller positions than the vertices in V 2 (i.e.

∀v 1 ∈ V 1 , ∀v 2 ∈ V 2 : p v 1 < p v 2 ). Then, harm(V 1 × V 2 , p) = 1 density(V 1 ,V 2 ) .
Theorem 4.6 Let p 0 be a one-dimensional drawing of a graph G = (V, E -) with minimum Dual LinLog energy. Let (V 1 , V 2 ) be a partition of V such that the vertices in V 1 have smaller positions than the vertices in V 2 (i.e.

∀v 1 ∈ V 1 , ∀v 2 ∈ V 2 : p v 1 < p v 2 ). Then, harm(E - V 1 ×V 2 , p 0 ) = density(V 1 , V 2 ).
Table 1 summarizes the clustering properties of Signed LinLog with its primary and dual. It is seen that Signed LinLog properties is a trade-off between the properties of its building blocks. Proofs for Dual LinLog theorems are found in Appendix A. This appendix also provides theorems about the relationship between the length of edges with the number of vertices in LinLog, Dual LinLog and Signed LinLog models. Refer to [START_REF] Noack | Energy models for graph clustering[END_REF] for the proofs of LinLog theorems.

Signed LinLog in Action

In this section we present a synthetic layout of Signed LinLog model as well as layouts of real data traces from Epinions [START_REF] Snap | Stanford Large Network Dataset Collection[END_REF], Slashdot [START_REF] Snap | Stanford Large Network Dataset Collection[END_REF], MovieLens [START_REF] Grouplens | MovieLens Datasets[END_REF] and tribal groups of Eastern Central Highlands of New Guinea [START_REF] Read | Cultures of the central highlands, new guinea[END_REF].

Toy Examples

Figure 1b shows the Signed LinLog layout of a graph containing 4 clusters of 5 vertices each. The link probability inside clusters is 0.99 representing groups of close friends. The positive link probability between cluster 1 and 2 is 0.2, i.e. they have some common interests. The negative link probability between clusters 1 and 2 with 3 is 0.2, i.e. they distrust cluster 3 to some extent. Cluster 4 has no relationship with the other clusters. There are also 15 disconnected vertices. All clusters are clearly identifiable. Clusters 1 and 2 lie pretty close to each other, but far from cluster 3. Cluster 4 is found in a place with almost equal distance from the other clusters. Notice disconnected vertices take position in a way that their distance from other vertices remain as uniform as possible. We also implemented the signed versions of Fruchterman and Reingold [START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF] and Davidson and Harel [START_REF] Davidson | Drawing graphs nicely using simulated annealing[END_REF] equations are given in Table 2. As is obvious from Figures 1a and1c, there is no way to detect the clusters once the vertices are discolored.

Here, we investigate the conformance of Signed LinLog layouts with the structural balance theory [START_REF] Heider | Attitudes and cognitive organization[END_REF]. This theory originated in social psychology by F. Heider. It posits that triangles with three positive edges, or two negative edges and one positive edge are more likely to exist between three individuals. Hence, they should be more frequent in real human communities. In other words, "The friend of my enemy is my enemy" and "The friend of my friend is my friend" are more plausible than "The friend of my enemy is my friend" and "the enemy of my enemy is my enemy".

(a) prob + 12 = 0.9 and prob + 23 = 0.9 (b) prob + 12 = 0.9 and prob - 23 = 0.9 (c) prob - 12 = 0.9 and prob - 23 = 0.9 Signed LinLog versus Balance Theory Let a graph with three communities (clusters) of 10 friends (prob + ii = 0.99, prob - ii = 0.0). We triple the attractive and repulsive forces for better layout clarity (k 1 = k 2 = 3, k 3 = 1). In Figure 2a, cluster 1 and cluster 2, and cluster 2 and cluster 3 trust each other (prob + 12 = 0.9, prob + 23 = 0.9). The structural balance theory suggests that cluster 2 and cluster 3 trust each other with high probability. We can see that they are put close to each other suggesting the same idea. In Figure 2b, cluster 1, trusts cluster 2, but cluster 2 distrusts cluster 3. The balance theory predicts distrust between cluster 1 and cluster 3. It is seen that cluster 1 and 3 are far from each other in the layout. In Figure 2c cluster 1 distrusts cluster 2, and cluster 2 distrusts cluster 3. Balance theory predicts trust between cluster 1 and cluster 3. In the Signed LinLog layout however, cluster 3 and cluster 1 are not very close. They seem to keep a neutral position towards each. In other words, "the enemy of my enemy is neither necessarily my friend nor my enemy".

My Enemy takes Her Friends Further from Me Let a graph with three communities of 10 friends (prob + ii = 0.99, prob - ii = 0.0). This graph models three communities of friends. In all three figures there is strong trust between cluster 1 and cluster 2 explaining why they are almost merged. In Figure 3a the two clusters express no attitude towards cluster 3 (prob + 12 = 0.9, prob - 13 = 0.0, prob - 23 = 0.0). Both cluster 1 and cluster 2 lie in a neutral position with the same distance from cluster 3. In Figure 3b cluster 2 expresses distrust towards cluster 3, while there is no link between cluster 1 and cluster 3 (prob + 12 = 0.9, prob - 13 = 0.0, prob - 23 = 0.9). It is seen that both cluster 1 and cluster 2 lie further from cluster 3 in Figure 3b than in Figure 3a, but cluster 1 is still closer to cluster 3. In other words, cluster 1 moves away from cluster 3 although there is no explicit edge between them. This occurs because cluster 1 follows its friend, and this latter distrusts cluster 3. In Figure 3c where both cluster 1 and cluster 2 explicitly express their distrust towards cluster 3 (prob + 12 = 0.9, prob - 13 = 0.9, prob - 23 = 0.9), their distance gets more than the previous two cases. Both cluster 1 and cluster 2 have the same position against cluster 3.

(a) prob + 12 = 0.9 (b) prob + 12 = 0.9 and prob - 23 = 0.9 (c) prob + 12 = 0.9 and prob - 13 = 0.9 and prob - 23 = 0.9 Figure 4a shows the case where there is no link between two clusters (prob + 12 = 0.0, prob - 12 = 0.0). The enemies move away from each other but try to stay in a neutral position against cluster 1 by encircling it. In Figure 4b the enemies have in common that they trust cluster 1 (prob + 12 = 0.6). Then, they get closer to cluster 1 than in Figure 4a, but still try to be as far as possible from each other. It is interesting to note that the users of cluster 1 try to stay away from each other, but at the same time get as close as possible to cluster 2.

Real World layouts

Epinions is a consumer review website where users can express trust or distrust in each other. The dataset consists of 841372 votes by 131828 voters. Slashdot [START_REF] Snap | Stanford Large Network Dataset Collection[END_REF] is a technologyrelated news website where a variety of user-generated information about latest technology and science-related news is circulated. Each user can mark others as friend if she likes their comments or as foe otherwise. The dataset contains 549202 votes by 82140 voters taken on the 21th of February 2009. Our statistical studies show that in the abolute majority of the cases, two users have both given the same vote for each other (either both positive or both negative). Despite, This conflict happens in 1% of two-way votes in Epinions dataset and 2% of them in Slashdot dataset. The layouts of Epinions and Slashdot are predented in Figures 5a and5b, respectively. In the simulations, we first omitted the conflicting votes, then kept vertices with at least 5 positive incident unidirectional edges.

The tribal groups of Eastern Central Highlands of New Guinea is consisted of 16 tribes being in war or peace state with each other. Each cluster has friend or foe relationship with others, but there is no foe state inside the same cluster. The corresponding layout is given is Figure 5c.

MovieLens 100k dataset consists of 100, 000 ratings on 1682 movies by 943 users. Ratings are in a 5-star scale. We establish a positive link between a user and an item if the user has rated the item with a score at least 0.2 larger than her average rating. In the same way, a negative edge is put when the corresponding rating is 0.2 smaller than the user's average rating. The MovieLens layouts are provided in Figure 6.

Energy Models for Drawing Bipartite Graphs

The user/item interaction can be modeled by bipartite graphs in collaborative rating networks. The two partitions of such a graph represent users and items. There exists an edge between a user and an item if the user has done some activity on the item. This is in the form of explicit rating in its less noisiest form, but may also refer to implicit data like clicking history. Real-world examples of collaborative filtering networks are MovieLens and Netflix where users rate movies in a 5-star scale to express their opinion on them. Visualization of these networks leads to detection of user and item clusters, being in turn a helpful asset to recommendation systems and market analysis.

Formally, we show bipartite graphs with

G b = (V 1 , V 2 , E b ), where E b ⊂ V 1 × V 2
is the edge set, and V 1 , V 2 are two disjoint sets of vertices representing the vertex partitions of the graph. Bipartite graphs are different from unipartite graphs in that there is no internal edge in the two partitions, and edges only exist between vertices belonging to two different partitions. Consequently, efficient bipartite graph visualization necessitates proper models. Standard graph visualization tools and libraries (e.g. NodeXL for Excel or Jung library for Java) do not offer such models. In this section we suggest an abstract equation for bipartite energy models. Then, we derive the clustering properties of Bipartite LinLog model. We define the bipartite density between two clusters V l and V r of a bipartite graph, where each cluster contains vertices from both V 1 and V 2 , as:

density b lr = |E lr | |V 1l | |V 2r | + |V 1r | |V 2l | . (3)
The main problem of Equation ( 4) for visualizing bipartite graphs is that the neutral energy g( p u -p v ) exists between every two vertices including (u, v) :

u ∈ V 1 , v ∈ V 2 .
For bipartite graphs, this leads in each partition influencing the configuration of the other out of the interaction set fully stated by edges. In general, the two partitions represent two totally different entities (e.g. users vs. items). Therefore, it is desirable to omit any mutual influence between them unless with the intermediate of edges. Having this idea in mind, we arrive at the following definition for bipartite energy models:

U Bipartite = {u,v}∈E b f ( p u -p v ) + {u,v}∈V (2)
1 ∪V

(2) 2

g( p u -p v ).
The bipartite version of Signed LinLog is defined as:

U BipartiteLinLog = {u,v}∈E b p u -p v - {u,v}∈V (2)
1 ∪V

(2) 2 ln p u -p v .

Theorem 7.1 states that in a layout with minimum Bipartite LinLog energy, the total length of edges is fixed; it is equal to the sum of squares of the cardinality of the two partitions.

Theorem 7.1 If p 0 is a drawing of a bipartite graph G b = (V 1 , V 2 , E b ) with minimum Bipartite LinLog energy, then: {u,v}∈E b p u -p v = |V 1 | 2 + |V 2 | 2 .
Theorem 7.2 Let p 0 be a one-dimensional layout of the bipartite graph

G b = (V 1 , V 2 , E b ).
Let V 1l , V 1r be a partition of V 1 , and V 2l , V 2r a partition of V 2 such that all vertices in V 1l and V 2l have smaller position than vertices in V 1r and V 2r (i.e. ∀v l ∈ V 1l ∪ V 2l , ∀v r ∈ V 2r ∪ V 1r : p v l < p vr ). Then:

harm(V 1l × V 1r ∪ V 2l × V 2r ) = |V 1l × V 1r | + |V 2l × V 2r | |E lr | = 1 density b lr
,

where E lr = E V 1l×V 2r ∪ E V 2l×V 1r , i.e. edges connecting the vertices on the left half-line to the vertices of the right half-line.

Theorem 7.3 Let G b = (V 1 , V
1 ∪V

.

Energy Models for Drawing Signed Bipartite Graphs

We represent bipartite signed graphs with

G bs = (V 1 , V 2 , E bs ),
where signed edge set is represented by

E bs = E + bs ∪ E - bs , E + bs , E - bs ⊂ V 1 × V 2 , E +
bs ∩ E - bs = ∅, and V 1 and V 2 denote the two vertex partitions. We define the positive and negative density for bipartite signed graphs as follows: The abstract form of bipartite signed energy models is defined as:

U BipartiteSignedGraph = {u,v}∈E + bs f ( p u -p v ) + {u,v}∈E - bs g( p u -p v ) + {u,v}∈V (2)
1 ∪V

2) 2 f ( p u -p v ) + g( p u -p v ). (
Bipartite Signed LinLog model is defined as:

U BipartiteSignedLinLog = {u,v}∈E + bs p u -p v - {u,v}∈E - bs ln p u -p v + {u,v}∈V (2)
1 ∪V

(2) 2

p u -p v -ln p u -p v .
The theorems of prior sections may be easily generalized to signed bipartite graphs. The proofs are quite similar to previous ones. Here, we state the results:

Theorem 8.1 If p 0 is a drawing of a bipartite signed graph G bs = (V 1 , V 2 , E bs )
with minimum Bipartite Signed LinLog energy, then:

{u,v}∈V (2) 1 p
u -p v + {u,v}∈V (2)
2 p u -p v + E + b p u -p v = |V 1 | 2 + |V 2 | 2 + E - b .
Theorem 8.2 Let p 0 be a one-dimensional layout of the bipartite signed graph G bs = (V 1 , V 2 , E bs ). Let V 1l , V 1r be a partition of V 1 , and V 2l , V 2r a partition of V 2 such that all vertices in V 1l and V 2l have smaller position than vertices in V 1r and V 2r (i.e. ∀v l ∈ V 1l ∪ V 2l , ∀v r ∈ V 2r ∪ V 1r : p v l < p vr ). Then: .

harm(V 1l × V 1r ∪ V 2l × V 2r ∪ E - bs ) = κ +

Conclusion

The problem of signed graph visualization has been ignored so far. In this paper, we suggested energy models for drawing signed graphs. We focused on preserving the community structure inside sociograms. A dual model was first suggested to draw graphs containing uniquely repulsive edges. An abstract equation for signed energy models was consequently proposed by adding up the primary models by their dual. Signed LinLog was presented as a model preserving the community structure inside graphs. We analytically derived its clustering properties, and argued the effect of force constants. The most important results were as follows. Signed LinLog draws positive edges short, and negative edges long w.r.t the mean neutral distance between vertices. This property renders the revelation of clusters. Signed LinLog generates layouts of graph bipartitions where the negative harmonic mean distance between the partitions increases with the positive density, and decreases with the negative density. Our signed energy models are capable of drawing disconnected graphs. Disconnected vertices are plot in places with distances as uniform as possible from the rest of the vertices.

then:

{u,v}∈E + V 1 ×V 2 k 1 D i=1 (x u i -x v i ) p u -p v + {u,v}∈V 1 ×V 2 D i=1 (x u i -x v i ) p u -p v = {u,v}∈E - V 1 ×V 2 k 2 D i=1 (x u i -x v i ) p u -p v 2 + {u,v}∈V 1 ×V 2 k 3 D i=1 (x u i -x v i ) p u -p v 2 .
Proof If we add some distance vector d = (d 1 , . . . , d D ) to all vertices in V 1 in a way that none of them enter S 2 , i.e. ∀u ∈ V 1 : i a i (x u i + d i ) < b, the energy of the new drawing is:

U new = {u,v}∈E + V (2) 1 ∪E + V (2) 2 k1 pu -pv - {u,v}∈E - V (2) 1 ∪E - V (
+ V 1 ×V 2 k1 D i=1 (x u i -x v i + di) 2 - {u,v}∈E - V 1 ×V 2 k2 ln D i=1 (x u i -x v i + di) 2 + {u,v}∈V 1 ×V 2 ( D i=1 (x u i -x v i + di) 2 -k3 ln D i=1 (x u i -x v i + di) 2 ).
The partial derivative of this function with respect to d i is:

∂Unew ∂di = {u,v}∈E + V 1 ×V 2 k1 x u i -x v i + di D i=1 (x u i -x v i + di) 2 - {u,v}∈E - V 1 ×V 2 k2 x u i -x v i + di D i=1 (x u i -x v i + di) 2 + {u,v}∈V 1 ×V 2 ( x u i -x v i + di D i=1 (x u i -x v i + di) 2 -k3 x u i -x v i + di D i=1 (x u i -x v i + di) 2
).

Since p is a layout with minimum Signed LinLog energy, the application of any non zero vector d must result in increase of energy. Hence, the gradient vector of U new must be zero when d = 0, that is ∀d i : ∂Unew

∂U new ∂d i = {u,v}∈E + V 1 ×V 2 k 1 D i=1 (x u i -x v i ) D i=1 (x u i -x v i ) 2 - {u,v}∈E - V 1 ×V 2 k 2 D i=1 (x u i -x v i ) D i=1 (x u i -x v i ) 2 + {u,v}∈V1×V2 ( D i=1 (x u i -x v i ) D i=1 (x u i -x v i ) 2 -k 3 D i=1 (x u i -x v i ) (x u i -x v i ) 2 ) = 0.
For D-dimensional layouts of graphs clusterizable to some extent, Theorem B.1 leads to the following useful corollary:

Figure 1 :

 1 Figure 1: Signed layouts of the toy example, cluster 1 is black, cluster 2 gray, cluster 3 blue and cluster 4 green (for all three models k 1 = 3, k 2 = 2, k 3 = 2). Positive edges are plot in green, and negative edges by dashed red lines. Signed LinLog has clear superiority in the representation of clusters.

Figure 2 :

 2 Figure 2: Conformance of Signed LinLog with Balance theory, k 1 = k 2 = 3, k 3 = 1.

Figure 3 : 1 (Figure 4 :

 314 Figure 3: Behavior of a cluster against the enemy of its friend, k 1 = k 2 = 3 and k 3 = 1

  (a) Epinions layout. A cluster is detectable lower than the center, slightly to the left. (b) Slashdot users. k1 = 19, k2 = 10, k3 = 10.(c) The tribal groups of Eastern Central Highlands of New Guinea. Three higher order clusters described in[START_REF] Hage | Structural Models in Anthro-pology[END_REF] are revealed. Positive edges are in green. Negative edges are plot by dashed red lines.

Figure 5 :

 5 Figure 5: Epinions and Slashdot Signed LinLog layouts. The users having received a lot of positive votes are in the center. Zooming on the layouts reveals many lower order clusters. k 1 = 19, k 2 = 10, k 3 = 10. In the layout of the tribal groups of Eastern Central Highlands of New Guinea, k 1 = 3, k 2 = 2, k 3 = 2.

Figure 6 :

 6 Figure 6: Signed LinLog Layouts of MovieLens 100k ratings. Active users and popular movies are in the center. Notice the changes in the density of movies. Some areas in the layout are pretty dense while some others are almost empty. Users lie close to the movies they have liked. k 1 = 19, k 2 = 10, k 3 = 10. In large sparse graphs, higher constants are more beneficial.

Figure 7 :

 7 Figure 7: Epinions and Slashdot layouts with the first model (k 1 = 19, k 2 = 10, k 3 = 10) and the second model (k 1 = 2, k 2 = 1, k 3 = 1).

  users movies (a) Users and movies -first model action (b) Action movies -first model thriller (c) Thriller movies -first model users movies (d) Users and movies -second model action (e) Action movies -second model thriller (f) Thriller movies -second model

Figure 8 :

 8 Figure 8: MovieLens 100k ratings visualization with the first and second model, k 1 = 19, k 2 = 10, k 3 = 10.

  |V 1l | |V 2r | + |V 1r | |V 2l |, density|V 1l | |V 2r | + |V 1r | |V 2l | .

Table 2 :

 2 through Equation (1). Exact k 1 |pu -pv| -{u,v}∈E -k 2 ln |pu -pv| + {u,v}∈V (2) |pu -pv| -k 3 ln |pu -pv| Signed Energy Models

	Signed Fruchterman and Reingold U =	+	{u,v}∈E + {u,v}∈V (2) ( 1 k 1 3 |pu -pv| 3 -{u,v}∈E -k 2 ln |pu -pv| 3 |pu -pv| 3 -k 3 ln |pu -pv|)
	Signed Davidson and Harel	U =		{u,v}∈E + k 1 |pu -pv| 2 + {u,v}∈E -	k 2 |pu-pv | 2
			+	{u,v}∈V (2) (|pu -pv| 2 +	k 3 |pu-pv | 2
	Signed LinLog	U =		{u,v}∈E

+

  2 , E b ) be a connected bipartite graph, and let p 0 be a layout of G b with minimum Bipartite LinLog energy. Then p 0 is a layout of G b that minimizes

	arith(E b ,p)
	geo(V

  density |V 1l | |V 1r | + |V 2l | |V 2r | |V 1l | |V 2r | + |V 1r | |V 2l | Theorem 8.3 Let G bs = (V 1 , V 2 , E bs )be a connected bipartite signed graph, and let p 0 be a layout of G bs with minimum Bipartite Signed LinLog energy. Then p 0 is a layout of G bs that minimizes

		b,-
	κ + density	lr lr b,+	,
	where
	κ =
	arith(V 1 ∪V (2) 2 ∪E + (2) bs ,p)
	geo(V 1 ∪V (2) 2 ∪E -(2) bs ,p)

Force is the minus gradient of energy. Hence, the minimum energy in a system is equivalent to the force equilibrium.

(B1, B2) is called a bipartition of G(V, E), if B1 ∩ B2 = ∅ and B1 ∪ B2 = V .

This causes no change to the energy of the system.

Notice such transformation does not exist for the layouts of all graphs.

* This work is supported by the ERC Starting Grant GOSSPLE number 204742.

Two Other Clustering Signed Energy Models

In this section we present two other classes of energy models whose clustering version can cluster graphs in terms of different cuts. In contrast to the model of Section 4, they are not constructed by adding the model to its dual.

Two Clustering Models

The first one is defines as:

{u,v}∈V (2) f ( p u -p v ) + g( p u -p v ).

In this model both negative and positive forces follow the same function. Like our previous model, this one is also capable of drawing disconnected graphs. The only case where the model does not converge is when there exist a subgraph whose each vertex has negative edges to all other vertices of the rest of the graph, i.e. density + (V 1 , V 2 ) = 1. Ignoring this special case that almost never happens in reality, we can state that the model can draw connected and disconnected graphs. In its clustering form it is written in the form of:

Here, we state the similar theorems about the clustering properties of this model. Proofs follow the same techniques as in Section 4. Theorem 6.1 If p 0 is a drawing of a graph G s = (V, E) with minimum Signed Clustering energy then: (2) . Theorem 6.2 Let p 0 be a one-dimensional drawing of the signed graph

.

Theorem 6.3 If p 0 is a drawing of the signed graph G s = (V, E) with minimum Signed Clustering energy, p 0 also minimizes arith + (V (2) \E -,p) geo(V (2) ,p)

.

The second class is defined as:

{u,v}∈V (2) g( p u -p v ).

In this model, the set of positive edges acts as the backbone of the layout rendering convergence. Consequently, this model can not draw graphs disconnected by positive edges. Its clustering form is:

ln p u -p v .

The clustering properties are as follows:

Theorem 6.4 If p 0 is a drawing of the positively connected signed graph G s = (V, E) with minimum Signed Clustering energy then:

Theorem 6.5 Let p 0 be a one-dimensional drawing of the positively connected signed graph

. Then:

Theorem 6.6 If p 0 is a drawing of the positively connected signed graph G s = (V, E) with minimum Signed Clustering energy, p 0 also minimizes arith(E + )

geo -(V (2) ,p) .

Example Layouts

The real world layouts of these models are seen in Figures 7 and8.

A Theorems and Proofs

Proof of Theorem 4. [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] We first suppose that the total distance between all vertices is fixed, and prove the theorem under this restriction. This restriction will be removed at the end of the proof using proof by contradiction. Suppose that p 0 is a drawing minimizing Dual LinLog energy, that is, it is a solution to the problem:

The total distance between all vertices in p 0 would be a positive value, say c:

Hence, p 0 is also a solution to:

.

Since E -exp(x) is an increasing function of its argument, the above expression is equivalent to:

, that is, minimize

subject to arith(V (2) , p) = c V (2) . If we multiply this result by arith(V (2) , p), we have: minimize arith(V (2) , p) geo(E -, p) subject to arith(V (2) , p) = c V (2) .

We now remove the restriction. Suppose there exists a drawing q 0 for which arith(V (2) ,q 0 ) geo(E -,q 0 ) < arith(V (2) ,p 0 ) geo(E -,p 0 )

. We can define a scaling q 1 = c V (2) arith(V (2) ,q 0 ) q 0 for which arith(V (2) , q 1 ) = c V (2) and arith(V (2) ,q 1 ) geo(E -,q 1 ) = arith(V (2) ,q 0 ) geo(E -,q 0 ) < arith(V (2) ,p 0 ) geo(E -,p 0 )

. This contradicts the previous results. Hence, q 0 does not exist, and we can always remove the restriction.

Proof of Theorem 4.6 Suppose that p 0 is a one-dimensional layout minimizing the Dual LinLog energy. Then, adding d ∈ R to the coordinates of all vertices in V 1 in a way that they remain smaller than the coordinates of all vertices in V 2 (i.e. max{p u |u ∈

), the Dual LinLog energy is:

1 ∪V

(2) 2

This function must have a global minimum at d = 0 because p is a layout with minimum Dual LinLog Energy:

Theorem A.1 states that the total length of edges is always fixed in layouts with minimum LinLog energy. The value of this total length is the cardinality of V (2) .

Theorem A.2 If p 0 is a solution to M inimize U DualLinLog , then:

Proof Suppose p 0 is a drawing with minimum Dual LinLog energy. If we multiply all coordinates by some d ∈ R, the energy of the system becomes:

Since p 0 is a drawing with minimum Dual LinLog energy every scaling of p 0 must lead to an increase in the energy of the system. Hence, the above expression has a minimum at d = 1.

26 Theorem A.2 states that the total Euclidean distance of all vertices is always fixed in layouts with minimum Dual LinLog energy. It is equal to the number of edges.

Theorem A.3 If p 0 is a drawing of a graph G s (V, E) with minimum Signed LinLog energy then:

{u,v}∈V (2) p u -p v = E -+ V (2) .

Proof Suppose p 0 is a drawing with minimum Signed LinLog energy. If we multiply all coordinates in p 0 by d ∈ R, the energy of the system is:

Since p 0 is a drawing with minimum energy, this equation has a minimum at d = 1, that is:

Theorem A.3 states that the sum of the total length of positive edges with the total Euclidean distance between all vertices is always a fixed value in the drawings with minimum Signed LinLog energy.

B Distance Interpretability in 1+ Dimensional Signed LinLog Bipartition Layouts

In this appendix we explain the approximate generalizability of Theorem 4.4 to 1+ dimensions. The following theorem holds exactly for layouts with any number of dimensions:

Theorem B.1 Let p be a D-dimensional drawing of G s = (V, E) with minimum Weighted Signed LinLog energy. Let (S 1 , S 2 ) be a bipartition of the drawing space by any hyperplane H defined by i∈I a

Corollary B.1 Let p be a D-dimensional drawing of G s = (V, E) with minimum Weighted Signed LinLog energy. For any non-scaling linear transformation of the coordinate system 3 that partitions the vertices into (V 1 , V 2 ) in a way that in the new coordinate system ∀u ∈

where

i is the Manhatan distance between p u and p v .

We know from Corollary 4.1 that force constants may be adjusted to shorten positive edges and lengthen negative edges as much as necessary. Hence, provided the graph is clusterizable into two convex subgraphs, we may modify the constants to decrease the diameter of clusters (i.e. the maximum Euclidean distance between pairs of a cluster) and increase their distance as much as desired. If the vertices are concentrated and far from each other, the Euclidean and Manhatan distance become almost equal. In this case we can state: Corollary B.2 Let p be a D-dimensional drawing of G s = (V, E) with minimum Weighted Signed LinLog energy. If a bipartition of vertices (V 1 , V 2 ) exists in a way that the diameter of V 1 and V 2 is small compared to their distance, then:

Proof Putting p u -p v ≈ p u -p v M an into Theorem B.1, we obtain:

Replacing the right side by

, where

.

the result is derived.


Fredrik Lundin
email: fredrik.lundin@lio.se

Anders Tisell

Dahlqvist Olof

Mats Leinhard

Carsten Tullberg

Peter Wikkelsö

Göran Lundberg

Leijon

Dahlqvist Leinhard

Reduced Thalamic NAA in Idiopathic Normal Pressure Hydrocephalus A Controlled 1H -MRS Study of Frontal Deep White Matter and the Thalamus Using Absolute Quantification

Keywords: Normal Pressure Hydrocephalus, Magnetic Resonance Spectroscopy, Thalamus, Frontal lobe N-acetylaspartate

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Normal Pressure Hydrocephalus (NPH) is a condition in which disturbed cerebrospinal fluid dynamics cause the typical symptoms of gait disturbance, cognitive impairment and urinary incontinence first described by Hakim &Adams and [START_REF] Adams | Symptomatic occult hydrocephalus with "Normal" cerebrospinal-fluid pressure. A treatable syndrome[END_REF]. [START_REF] Hakim | The special clinical problem of symptomatic hydrocephalus with normal cerebrospinal fluid pressure. Observations on cerebrospinal fluid hydrodynamics[END_REF][START_REF] Adams | Symptomatic occult hydrocephalus with "Normal" cerebrospinal-fluid pressure. A treatable syndrome[END_REF] NPH is classified as idiopathic NPH (INPH), where no cause can be identified, and secondary NPH when it is preceded by a known disease. [START_REF] Ojemann | Further experience with the syndrome of "normal" pressure hydrocephalus[END_REF] The symptoms and signs in INPH are generally recognized as being of subcortical origin. [START_REF] Hellström | The neuropsychology of patients with clinically diagnosed idiopathic normal pressure hydrocephalus[END_REF] Damage to myelin and axons, and signs of arteriosclerosis in these areas have been described. [START_REF] Akai | Normal pressure hydrocephalus. Neuropathological study[END_REF][START_REF] Bigio | Neuropathological changes caused by hydrocephalus[END_REF] Furthermore, the incidence of cardiovascular risk factors is high and these are thought to be of importance for disease development. [START_REF] Krauss | Vascular risk factors 12 and arteriosclerotic disease in idiopathic normal-pressure hydrocephalus of the elderly[END_REF] MR Spectroscopy (MRS) is a well-established method for studying metabolites in the brain noninvasively. The concentrations of a number of metabolites can be analyzed, including total N-acetyl compounds (tNA) consisting of N-acetylaspartate (NAA), and N-acetylaspartateglutamate (NAAG) which is highly concentrated in the mitochondria, and both of these are regarded as neuronal density markers. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF][START_REF] Caramanos | 1H-MRS quantification of tNA and tCr in patients with multiple sclerosis: a meta-analytic review[END_REF][START_REF] Moffett | N-Acetylaspartate in the CNS: from neurodiagnostics to neurobiology[END_REF] NAA also occurs in white matter in an approximately equal amount. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF] Low NAA may be an indication of neuronal loss but may also indicate a reversible state. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF][START_REF] Stefano | Reversible decreases in N-acetylaspartate after acute brain injury[END_REF] Choline (Cho) is found in cell membranes and is believed to be a marker of membrane turnover and myelination. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF] Myo-inositol (mIns) is a constituent of membrane lipids and is also regarded as a marker of glia cells. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF] tCr is divided into creatine and phosphocreatine, the latter being three times higher in astrocytes. [START_REF] Brand | Multinuclear NMR studies on the energy metabolism of glial and neuronal cells[END_REF] Generally tCr is however considered as a marker of energy deposits. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF] Glutamate (Glu) is an amino acid that is highly concentrated in excitatory neurons. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF] Lactate accumulates when energy metabolism is subjected to anaerobic stress. [START_REF] Ross | Magnetic resonance spectroscopy in cognitive research[END_REF] In MRS-NPH studies, different techniques and placements of the voxels have been used, which unfortunately makes a direct comparison very difficult. Data on absolute metabolite concentrations

have not yet appeared in NPH patients. Based on the hypothesis that INPH patients suffer from disturbed basal ganglia-thalamic-subcortical frontal circuits, our aim was to demonstrate that there was a reduced metabolism in the thalamus and the subcortical frontal areas in INPH patients in comparison with HI. Exclusion criteria were: Intracranial pressure (ICP) higher than 18 mmHg, cerebrospinal fluid (CSF) changes not compatible with INPH, infarctions in the thalamus and in the frontal lobes, patients not able to cooperate, and finally, short expected survival time.

Patients

Medication was not a reason for exclusion.

Healthy Individuals

Sixteen healthy elderly people, 7 M, 9 F, mean age 73 (62-89) years were recruited consecutively as HI. They considered themselves healthy and no serious disease could be found by examination.

Reasons for exclusion were clinical obvious gait disturbance, MMSE <21 and infarction in the Volume of Interest (VOI). Periventricular hyperintensities and cortical atrophy were allowed.

Medication and previous diseases not impairing gait and cognition were not reasons for exclusion in HI.

All participants gave written consent the study was performed according to the Declaration of Helsinki.

Clinical assessment

The patients underwent a neurological examination by a neurologist (FL) and later on an MRI was performed. The motor functions were examined by a physiotherapist. Time for 10 metre walk in seconds (w10mt) and number of steps (w10ms) at a self-selected speed with their usual walking aid were registered.(15) Timed up and go test in seconds and steps (TUGt,TUGs), which is a timed test for standing up from a chair, walking 3 metres, turning and walking back to the chair and sitting down.( 16) Gait scale: 1, normal; 2, insecure; 3, insecure with cane; 4, bi-manual support; 5, aided; 6, wheelchair. [START_REF] Larsson | Clinical parameters in 74 consecutive patients shunt operated for normal pressure hydrocephalus[END_REF] The balance test used was Romberg's, slightly modfied from Blomsterwall et al. [START_REF] Blomsterwall | Postural disturbance in patients with normal pressure hydrocephalus[END_REF], and it was performed standing, with the feet together, eyes closed and hands on the chest.

Seconds to correction up to 60 seconds were registered. An occupational therapist performed the MMSE test. Lumbar CSF pressure was measured either manually in the recumbent position or automatically if a computerized lumbar infusion study was performed. Cells, proteins and antibodies against Borrelia burgdorferi were analyzed.

The HI were examined by a neurologist (FL), including the test for 10 metre walking (measured in seconds), number of steps, and Romberg's test. MMSE was performed by an occupational therapist or a neurologist.

MR Acquisitions

All MR measurements were performed using an Achieva 1.5 T MR scanner (Philips, Best, The Netherlands), and an eight-channel SENSE head coil. MRS data were acquired using Point Resolved Spectroscopy (PRESS), with an echo time of 30 ms and a repetition time of 3 s, 128 water-suppressed spectra were averaged, two MRS volumes of interest (VOI), one in the left thalamus and, one in the left FDWM were placed in each subject, each voxel with a volume of ca. 2.50 mL. In addition, spectra without water suppression were also obtained. In a later phase of the study, two additional MRS VOI were acquired, one in the right (1/T 2 ), an axial multi-echo GRASE (ME-GRASE) pulse sequence was used to acquire data on the tissue water signal (= ME-GRASE-Volume). The parameters used for ME-GRASE were: matrix 2

x 2 x 4 mm 3 ; TE was 20, 40, 60, 80, 100, 120, 140, and 160 ms; TR 5.28 s).

To avoid errors due to patient movement the coronal localizer images were re-sampled prior to and after each MRS acquisition. If pre/post-MRS movement was detected and considered to be significant (> 3 mm) the MRS data were discarded, and the data acquisition was repeated.

MRS post processing:

The MRS signals were analyzed using LCModel ver. 6.1-4G. [START_REF] Provencher | Estimation of Metabolite Concentrations from Localized in-Vivo Proton NMR Spectra[END_REF] The unsuppressed water signals were used as an internal reference, and quantified using the water scaling function in LCModel, with the parameter attenuation of the NMR-visible water (ATTH20) = 1.00 (from 0.7). Thus the resulting concentrations were aqueous concentrations compensated for by differences in coil load and temperature, and differences in RF-amplification, etc in different subjects. The concentration values determined in this manner depended then only on differences in the relaxation, and different compartmentalization, between the metabolites and the internal water reference signal.

Estimation of quantitative R2 values:

The R2-values were obtained from the ME-GRASE experiments by fitting an exponential function to the data. The amplitude M0 is a T1 and B1weighted estimate of the proton density and R2 is the transversal relaxation rate.

Correction for CSF content with the MRS VOI:

The fractions of CSF (P CSF ) in the MRS VOIs were determined using the lower tail of the distribution of the R2 values in the VOIs, together with an upper R2-limit of 2.5 s -1 . The concentrations were then scaled with 1/(1-P CSF ).( 19)

Scaling to absolute concentrations:

In order to convert the LCModel estimates to absolute concentrations, we used a modified version of the method described in [START_REF] Brief | Absolute metabolite concentrations calibrated using the total water signal in brain 1 H MRS[END_REF]. The major difference was that the water scaling function in the LCModel was here used to scale the differences between the in-vitro measurements of the basis set, and the in-vivo measurement on the MR scanner used in this investigation.( 21)

Exclusion:

The spectra were inspected for residuals and large artefacts in the spectral region of interest. In order to avoid bias toward high concentrations, no measurements were excluded from the subsequent statistical analysis based only on the SD% values in LCModel.

Statistical Analysis

The statistical analysis used JMP 8.0 (SAS Institute Inc, USA). A full mixed linear model (MLM) was created with the three fixed factors "Group", "Tissue", "Lateral", and the corresponding crossing effects. A random factor "Patient" nested with the "Group" factor was also included. The Restricted Maximum Likelihood (REML) was used to analyze the mixed model. The model gave no significant effects for the "Lateral" effect or any of its crossing effects. Therefore, the model was subsequently reduced to contain only the "Group"', "Tissue"', their crossing effect, and the "Patient"' effect.

Group analysis

From the MLM mean values of the crossing Effect, Group and Tissue were calculated (HI-FDWM, HI-thalamus, INPH-FDWM, and INPH-thalamus). Differences in mean values were tested using a Tukey test, and p-values < 5% was considered significant.

Confounding factors

To avoid any eventual differences in metabolite concentrations or R2 could be due the higher occurrence of vascular risk factors in the INPH than in the HI, six extended MLMs were created by adding fixed factors for Stroke/TIA, Hypertension, Heart disease, Diabetes, Smoking, Risk one by one and all their crossing effects (Risk=1 if any of the risk factors were 1). Factors were considered significant to the model at p < 0.05.

Regression analysis

Linear regression models were created using the motor variables: w10mt, w10ms, TUGt and TUGs as explanation variables for the metabolite concentrations NAA, tNA, Glu, tCr, tCho, Lac, mIns and the mean R2 as response variables. For patients for whom two MRS measurements were made from the same tissue, the mean values were used as response variables. All models were created using the standard least square method in JMP. Variables were considered significantly correlated for p < 0.05.

RESULTS

Subjects

Four out of twenty patients were excluded from the study (due to neuroborreliosis, severe heart failure, unwillingness to participate and MMSE < 21). Sixteen patients (9 males and 7 females) were finally evaluated in the study. Age was similar between patients and HI. Hypertension was more common in the patients. The patients performed worse in motor functions, while MMSE was similar (Table I). One of the 16 HI was excluded as the MRS examination was lost due to data error, thus fifteen remained in the study. Twenty-six voxels were each placed in the FDWM and in the thalamus of the 16 patients; two voxels were excluded in the FDWM due to poor spectral quality. Twenty-one voxels were placed each in the FDWM and in the thalamus of the 15 HI. In the FDWM and in the thalamus one voxel each was excluded due to poor spectral quality. Because of lacunar infarctions in the thalamus in one HI the voxels in the thalamus were excluded. One HI was reinvestigated due to motion artefacts. Cardiovascular risk factors did not influence the metabolic concentrations.

qMRI results

No significant differences between R2 in different tissues and subjects were observed. Estimated mean and standard error R2 for; HI FDWM 10.92 s -1 , (SE = 0.19), thalamus 10.93, (SE = 0.19), for; INPH FDWM = 10.78 s -1 , SE = 0.17, thalamus = 10.66 s -1 , SE = 0.17. This suggests that there was no significant difference in the intracellular aqueous state between the groups and different tissues.

MRS results

The mean thalamic concentration of NAA was 11% lower (p = 0.02) and mean tNA were 6% lower (p = 0.05) in the patients compared to the HI (Table II, III). No significant differences between the groups were observed for the FDWM. Metabolite ratios to tCr were not significant different in either the FDWM or the thalamus compared to HI. An increased tCr in FDWM correlated to a reduced motor function. At a trend level there was a negative correlation, i.e. reduced NAA correlated to a reduced motor function, between NAA and the motor variables in the thalamus (Table IV). Elevated lactate could not be detected either in the thalamus or in the FDWM.

DISCUSSION

The main findings of this study are significant lower concentrations of NAA and tNA in the thalamus in INPH patients compared to HI. Data were obtained from absolute concentrations and indicate a neuronal dysfunction in the thalamus in INPH patients (Table III). Interestingly, no metabolic abnormalities were observed in the FDWM (Table II).

We believe that our patients are representative of the typical form of INPH patients since they showed classical motor symptoms, but cognitively they were relatively well preserved. The patients had approximately half the gait velocity of the HI. The cognitive performance measured with MMSE was similar to that of the HI. The reason for excluding patients with a profound cognitive deficit was to create a homogeneous group of patients representing INPH in a rather pure form and avoid other co-existing pathologies with impaired cognitive function related to FDWM, which would have influenced the results. [START_REF] Ross | Prediction of cognitive decline after stroke using proton magnetic resonance spectroscopy[END_REF][START_REF] Ross | Cognitive correlates of 1H MRS measures in the healthy elderly brain[END_REF] MRS studies in NPH patients have presented conflicting results. In a heterogeneous hydrocephalic population ranging from neonates to the elderly, Braun et al. could not find any metabolic abnormalities in the periventricular white matter nor in the CSF compared to HI. [START_REF] Braun | 1H magnetic resonance spectroscopy in human hydrocephalus[END_REF] In a study by Lenfeldt et al. regarding INPH patients it was shown that patients had a significant lower NAA/Cr in FDWM compared to a control group and they also showed that patients with a positive Elongated Lumbar Drainage (ELD) had a higher NAA/Cr than those with a negative ELD. Their conclusion was that having enough functional neurons was a prerequisite for the CSF drainage to have an effect. [START_REF] Lenfeldt | Improvement after cerebrospinal fluid drainage is related to levels of N-acetyl-aspartate in idiopathic normal pressure hydrocephalus[END_REF] Based on the absolute concentration measurements of NAA and tCr in FDWM (Table II), the hypothesis that the decreased NAA/Cr ratio was due to a lowered concentration of NAA can be rejected. This is particularly interesting as one then can conclude that the observed decreased NAA/Cr ratio can be fully explained by the increase in absolute tCr concentration. A non-controlled study by Del Mar Matarin et al. in INPH focusing on postoperative changes found an increase of NAA/Cr after a shunt operation in the frontal lobe and the postoperative value of NAA/Cr was correlated with the MMSE score. [START_REF] Del Mar Matarín | Post-surgical changes in brain metabolism detected by magnetic resonance spectroscopy in normal pressure hydrocephalus: results of a pilot study[END_REF] They concluded that NAA/Cr may be reversible and that cognitive level is associated with the NAA/Cr levels in the subcortical frontal lobe.

The size of the voxels in FDWM used in our investigations were smaller compared to those used by Lenfeldt et al.(25) The size of the VOI was chosen to include as much of the thalamic area as possible, with a minimal inclusion of other tissues thus avoiding partial volume effects. A larger voxel would result in a better signal to noise ratio (SNR), but we found it impossible to combine larger spectral voxels with a sufficiently accurate tissue selection. Another difference was the placements of the voxels, which in our study were closer to the periventricular zone.

In contrast to all previous NPH-MRS studies we have used absolute quantification of the metabolite concentrations. Such an approach involves a slightly more complex procedure; however, it will provide much more informative results than procedures that are based on creatine ratios. Regional and individual variability of tCr as well as influences from systemic diseases may influence the tCr [START_REF] Soares | Magnetic resonance spectroscopy of the brain: review of metabolites and clinical applications[END_REF][START_REF] Maudsley | Mapping of brain metabolite distributions by volumetric proton MR spectroscopic imaging (MRSI)[END_REF], thereby affecting the concentration ratios. In addition, Li et al. found that the coefficient of variation (CV) in a large series of examined voxels was higher for ratios than for absolute quantification.(29) Schirmer et al. also found that a significantly lower CV, both intra-and interindividually, favoured absolute quantification. [START_REF] Schirmer | On the reliability of quantitative clinical magnetic resonance spectroscopy of the human brain[END_REF] No previous MRS study of NPH patients has involved examination of the thalamus. We detected a significant reduction of NAA and tNA in the thalamus compared to HI. This result of reduced NAA concentrations in the thalamus is very interesting since thalamus is of great importance in movement disorders. Previously the basal ganglia were thought to relay motor circuits to the motor cortex via thalamic slave neurons. We now know that in idiopathic Parkinson there is a significant neuronal loss in the caudal interlamina nuclei while the limbic parts are spared. [START_REF] Halliday | Thalamic changes in Parkinson's disease[END_REF] Thalamus is today regarded as a major regulator of basal ganglia function. [START_REF] Henderson | Loss of thalamic intralaminar nuclei in progressive supranuclear palsy and Parkinson's disease: clinical and therapeutic implications[END_REF] The motor as well as the cognitive symptoms, may from a strict neuro-anatomical point of view, originate from the thalamus.

In schizophrenia as well as in Huntington's disease thalamus has been examined with MRS and NAA has found to be decreased. [START_REF] Jakary | N-acetylaspartate reductions in the mediodorsal and anterior thalamus in men with schizophrenia verified by tissue volume corrected proton MRSI[END_REF][START_REF] Ruocco | Evidence of thalamic dysfunction in Huntington disease by proton magnetic resonance spectroscopy[END_REF] Our results may indicate a primary pathology or secondary to dysfunction elsewhere, e.g. the basal ganglia.

Though we expected to find changes also in the FDWM as Lenfeldt et al. did, this was not observed either using absolute quantification or tCr ratios. The most consistent finding of CBF studies is a decreased CBF in the frontal lobe.(35) However, Owler et al. did not find any changes in the frontal area using positron emission tomography. [START_REF] Owler | Normal pressure hydrocephalus and cerebral blood flow: a PET study of baseline values[END_REF] Even if this is not directly coupled to our findings it is interesting that Owler and colleagues observed a normal CBF in the frontal lobe but a decreased CBF in the thalamus, and this is in line with our results. An alternative explanation for the apparently reduced NAA levels (as deduced from the tCr-ratios) in the frontal lobe compared to Lenfeldt et al. could be that they included patients with a lower cognitive function, who may have had a co-existing pathology, since it has been shown that cognitive function is correlated to NAA in the frontal lobe. [START_REF] Ross | Cognitive correlates of 1H MRS measures in the healthy elderly brain[END_REF] As motor symptoms are of major interest in these patients, we separately performed a regression analysis between motor variables and the absolute concentrations of the metabolites, in addition to tCr ratios. A significant positive correlation of tCr concentrations in FDWM with motor function, i.e. higher tCr concentration was correlated with worse gait function, and no correlation were observed between NAA concentrations in FDWM and gait function. We interpret this result as being due to glial cell increase in the tissue without any effective density loss of neurons, similar to what has been reported by Vrenken.(37) However, more studies will be needed to confirm this important finding, preferably at higher field strengths. In addition, we found a significant negative correlation of NAA/tCr with motor variables in the FDWM. This we concluded was due to the positive correlation of tCr -and not to any change in NAA. This result clearly highlights the importance of using absolute concentrations instead of tCr ratios for investigations of tissue metabolism.

The trends of negative correlation between NAA concentration and motor variables in combinations with the clinical picture of the patients, and also an absolute reduction of NAA concentration in thalamus suggests that the thalamus is linked to the pathogenesis of INPH.

CONCLUSION

We demonstrated significantly lower NAA and tNA concentrations in the thalamus of INPH patients compared to HI, which indicates a neuronal dysfunction in the thalamus. In contrast, we were not able to find any evidence of neuronal dysfunction in the FDWM.

In order to further explore our hypothesis about a dysfunction in basal ganglia-thalamic-subcortical frontal circuits in INPH patients, future studies must also involve the basal ganglia. In addition, it would be valuable to investigate if there is reversibility of the decreased NAA and tNA in the thalamus following surgery.

  Twenty patients, 12 M and 8 F, mean age 74 (49-83) years, consecutively recruited from our outpatient clinic and diagnosed with INPH were included in the study. All fulfilled the following clinical and radiological inclusion criteria, modified from INPH guidelines.(13) Clinical inclusion criteria were: Gait disturbance of both legs, unexplained by other conditions, disturbance of tandem walking, multistep turning, small steps and wide based gait, Mini Mental State Examination (MMSE) (14) score between 21-30, no evident aphasia, apraxia or agnosia, and bladder instability might be present. Radiological inclusion criteria were: Symmetrical communicating quadric-ventricular enlargement without cortical infarcts or other clinical relevant parenchymal lesions except lacunar infarcts (< 1cc), Evan´s index ≥ 0.3 and temporal horns and third ventricle should be relatively enlarged, mild to moderate cortical atrophy and leuco-araiosis might be present.

  thalamus and one in the right FDWM (this was done for the ten final INPH patients and the six final HI). Schematic placements of a single VOI in the FDWM and the thalamus of an INPH patient in the cardinal directions of the localizer images are shown in Fig. 1 and Fig 2 respectively. The MRS VOIs were placed in normal appearing matter avoiding hyperintensities. For quantification of R 2

Figure 1 :

 1 Figure 1: Schematic placement of a single VOI in the FDWM of an INPH patient in the cardinal directions of the localizer images. Assignments: 1. Cr-CH 2 ; 2. Glu a/Gln a; 3. Gln (multiplet from C2-C6); 4. myo-Ins; 5. Gln (multiplet from C2-C6); 6. scyllo-Ins; 7. Cho (CH 3 ) 3 ; 8. Cr (CH3); 9. NAA; 10. NAA; 11. Glu g/b; 12. Gln g/b; 13. NAAG-methyl (singlet); 14. NAA-methyl (singlet); 15. Lac CH 3 ; 16. protein background ('baseline); 17. unassigned.

Figure 2 :

 2 Figure 2: Schematic placement of a single VOI in the thalamus of an INPH patient in the cardinal directions of the localizer images. For assignments, see Fig. 1.

Table I .

 I Clinical results for HI and INPH-patients in the study.

		HI	INPH
	N	15	16
	Male/female	6/9	9/7
	Age, years mean (range)	74 (62-89)	74 (49-83)

Table II .

 II Mean and standard errors (SE) of metabolite concentrations in the FDWM in patients and HI. Concentration values are presented in units of mM aq. and as concentration ratios. LCM CR = LC Models Cramer Rao bounds

	tCho	2.70	0.11	0.20	2.53	0.10	0.21
	Lac	0.40	0.15	0.49	0.71	0.13	0.60
	mIns	7.51	0.36	0.75	7.67	0.34	0.83
	NAA/tCr	1.32	0.05		1.23	0.04
	tNA/tCr	1.45	0.04		1.37	0.03
	tCho/tCr	0.40	0.02		0.35	0.01
	mIns/tCr	1.10	0.05		1.06	0.05
	FDWM	HI (N=15)			INPH (N=16)
		Mean	(SE)	LCM CR	Mean	(SE)	LCM CR
	NAA	8.95	0.28	0.71	8.91	0.25	0.80
	tNA	9.82	0.23	0.65	9.91	0.20	0.71
	Glu	8.76	0.46	1.72	8.73	0.41	1.95
	tCr	6.86	0.19	0.51	7.28	0.17	0.56

Table III :

 III Mean and standard error of metabolite concentrations in the thalamus in HI and patients. Concentration values are presented in units of mM aq. and as concentration ratios. * = significant difference from HI at p<0.05, ** = significant difference from HI at p < 0.025. LCM CR= LC Models Cramer Rao bounds

	TH	HI (N=15)			INPH (N=16)
		Mean	(SE)	LCM CR	Mean	(SE)	LCM CR
	NAA	10.77	0.29	0.96	9.61**	0.24	0.99
	tNA	12.71	0.24	0.77	11.88*	0.20	0.83
	Glu	13.02	0.48	2.00	12.32	0.39	2.12
	tCr	8.08	0.20	0.61	7.87	0.16	0.63
	tCho	2.53	0.11	0.22	2.38	0.10	0.23
	Lac	0.36	0.16	0.63	0.41	0.13	0.51
	mIns	6.47	0.38	0.76	7.13	0.33	0.86
	NAA/tCr	1.34	0.04		1.23	0.04
	tNA/tCr	1.58	0.04		1.52	0.03
	tCho/tCr	0.31	0.02		0.30	0.01
	mIns/tCr	0.79	0.06		0.91	0.05

Table IV :

 IV Correlation coefficient r for linear regression models for gait parameters; w10mt, w10ms, TUGt, TUGs against tCr NAA and NAA/tCr seconds, w10mt=walk 10m steps, TUGt=Timed Up and Go in seconds, TUGs=Timed Up and Go steps

	w10m s	FDWM	0.54	0.03	0.03	0.92	-0.47	0.07
	TUG t	FDWM	0.56	0.02	0.04	0.88	-0.50	0.05
	TUG s	FDWM	0.53	0.04	0.04	0.88	-0.47	0.08
	w10m t	TH	0.20	0.46	-0.36	0.17	-0.48	0.06
	w10m s	TH	0.12	0.66	-0.46	0.07	-0.47	0.07
	TUG t	TH	0.11	0.69	-0.41	0.11	-0.45	0.08
	TUG s	TH	-0.10	0.73	-0.61	0.02	-0.36	0.18
	w10mt=walk 10m in
			tCr		NAA		NAA/tCr
		Tissue	r	p	r	p	r	p
	w10m t	FDWM	0.73	0.00	0.18	0.51	-0.51	0.04

Acknowledgements: Dr L. Davidsson is gratefully acknowledged for clinical radiological evaluations of MR images. Statistical advice was provided by Dr O. Eriksson, and this is also gratefully acknowledged. Dr M. Ljungberg is acknowledged for generously providing a copy of the LCModel metabolite library acquired at Sahlgrenska University Hospital/University of Gothenburg.

Funding: Financial support from the National Research Council (VR/NT), University Hospital Research funds, CMIV, and the University of Linköping.

Competing interests: None

Ethics approval: The study was approved by the Regional Ethical Review Board in Linköping, Licence for Publication:

The Corresponding Author has the right to grant on behalf of all authors and does grant on behalf of all authors, an exclusive licence (or non exclusive for government employees) on a worldwide basis to the BMJ Publishing Group Ltd to permit this article (if accepted) to be published in JNNP and any other BMJPGL products and sublicences such use and exploit all subsidiary rights, as set out in our licence.