Interactive Brain Graph Visualization (1):  Network analysis

Interactive Brain Graph Visualization (1): Network analysis

Let’s don’t rush into the coding part. Firstly, take a look at the network analysis.

1. What is a graph?

In graph theory, a graph is a representation of  a set of objects where some pairs of objects are connected by links.It is a set of entities (aka vertices or nodes) and the connections (aka edges, links, or ties) among them. There may be an edge between every pair of nodes, no edges at all, or anything in between. You could refer to wikipedia of graph or this lecture note

Figure 1. A drawing of a labeled graph on 6 vertices and 7 edges.

2.  Network analysis: Centrality

Let’s Assume a graph of social web connections. People are nodes in the graph and they connect to each other by relationships. Nodes have weights, as people are influential to others. Therefore, we are concerned about the importance of nodes. There are several ways to calculate the importance of nodes, for example, Degree Centrality, Eigenvector Centrality, Katz Centrality, PageRank, Closeness Centrality, Betweenness Centrality, Transitivity. In the project, we mainly use degree centrality, eigenvector centrality and betweenness centrality to represent the importance of nodes. Degree centrality focuses on individual nodes – it simply counts the number of edges that a node has. High betweenness centrality nodes usually are those that occur on many shortest paths between other nodes in a graph. The eigenvector centrality of a node is proportional to the sum of the centrality scores of its neighbors. For more informations, you could refer to this lecture note concerning social and technological network analysis from University of Cambridge or wikipedia explaining the concept of centrality.

example of a graph with centrality information

Figure 2. example of a graph with centrality information

 

As we are more concerned about eigenvector centrality. Now let’s give a look at its algorithm.(The following comes mainly from wikipedia)

An eigenvector of a square matrix A is a non-zero vector v that, when the matrix multiples v, yields a constant multiple of v, the latter multiplier being commonly denoted by \lambda. That is:(for more informations, please look at wiki or this note)

A v = \lambda v

Eigenvector centrality is a measure of the influence of a node in a network. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. We could use eigenvector adjacent matrix to find eigenvector centrality. For a given graph G:=(V,E) with |V| number of vertices let A = (a_{v,t}) be the adjacency matrix, i.e. a_{v,t} = 1 if vertex v is linked to vertex t, and a_{v,t} = 0 otherwise. The centrality score of vertex v can be defined as:

 

x_v = \frac{1}{\lambda} \sum_{t \in M(v)}x_t = \frac{1}{\lambda} \sum_{t \in G} a_{v,t}x_t

 

where M(v) is a set of the neighbors of v and \lambda is a constant. With a small rearrangement this can be rewritten in vector notation as the eigenvector equation

 

\mathbf{Ax} = {\lambda}\mathbf{x}

 

In general, there will be many different eigenvalues \lambda for which an eigenvector solution exists. However, the additional requirement that all the entries in the eigenvector be positive implies (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.[18] The v^{th}component of the related eigenvector then gives the centrality score of the vertex v in the network. To compute, we use this algorithm:

 

Computation steps

- Calculate the eigendecomposition of the pairwise adjacency matrix of the graph.

- Select the eigenvector associated with largest eigenvalue.

-  Element i in the eigenvector gives the centrality of the i-th node.

In my other blog posts, we will look at its applications in graph visualization, specially, simple graph visualizations on

INTERACTIVE BRAIN GRAPH VISUALIZATION (2): SIMPLE GRAPH VISUALIZATIONS WITH BARBELL GRAPH

INTERACTIVE BRAIN GRAPH VISUALIZATION (3): SIMPLE GRAPH VISUALIZATIONS WITH RANDOM GRAPH

brain visualizations on

INTERACTIVE BRAIN GRAPH VISUALIZATION(4): FROM FMRI TO JSON FILE

Leave a Reply