1. Introduction
Generally, networks are deemed as a collection of certain objects and links joining them. Mathematics through its subfield Graph Theory gives an apt way to define networks and characterizes its properties. The word Graph was coined from the Greek term Graphos that stands for something that is drawn.
1.1. Origin of Graph Theory
Leonhard Euler announced the usefulness of a graphical representation, for comprehending a challenge from a practical life situation. In 1735, Euler lived in the Prussia of erstwhile Russia as a town of Konigsberg. It has 7 bridges along the Pregel River, joining the 2 banks of the river and 2 islands of the river in the middle. See Figure 1. A Challenge at that time was to devise a path that traverses each bridge exactly once Euler established the nonexistence of such a path by denoting the 4 land areas by vertices and the 7 bridges by edges. Euler demonstrated that no more than 2 vertices can have number of edges of odd parity joining them to the other vertices of the graph for the existence of such a path. Number of edges of odd parity incident on all 4 vertices of the Konigsberg bridge graph implied that it is not possible to determine such a path. Euler proved beyond doubt this fact with a crisp two-page argument. This has led to the birth of a branch of mathematics called, Graph Theory.
1.2. Definition of a Graph
Mathematically, a graph is a pair
with V, a non-empty of elements called nodes, where
, E, a set of elements refereed as links, where
, where
stands for edge joining the vertex vr with vertex vs. The set E can be empty set, in which
Figure 1. Euler’s first topological description of a graph. (x) Map of a town of Konigsberg with A - D denoting land areas, joined by seven bridges denoted by p - v. The challenge thwarted by Euler was: prove or disprove the existence of a path that traverses all bridges without traversing any bridge more than once. (y) Euler’s graphical modeling of the challenge. Here vertices stand for land areas and edges stand for bridges. Euler’s brilliant idea was centered around the edge count incident on each vertex.
case, we call the graph
an empty graph. The relation between the elements of V and E are brought forth through a mathematical incidence relation
, where x stands for the cartesian product of V with itself. The incidence relation
associates to each element
an element
such that
. We say that the
joins the vertex vr with the vertex vs. Here × refers to the Cartesian product.
1.3. Matrix Representation of a Graph
It is possible to express a graph in matrix form as a
matrix called adjacency matrix
. For a graph bereft of weight for edges, the un-weighted adjacency matrix A will have for its element
, the value 1 if
, indicating the presence of an edge from
to
and
will take the value 0 if
indicating the absence of an edge between
to
. For a weighted graph, the weighted adjacency matrix A will have for its element
, values other than 0 or 1 to stand for strength or relevance.
1.4. Undirected/Directed Graph and Terminologies
Graphs can be of two types depending on the presence/absence of a direction on their link elements. In the case of a former, we call it a directed graph or diagraph and in the case of latter, we call it an undirected graph. Note that for an undirected graph, its adjacency matrix will be symmetric and for a diagraph, its adjacency matrix will be asymmetric. Suppose no self-loops are present in
, then the cardinality of E or the number of elements in E, denoted
can be a maximum of
in the case of undirected graphs and a maximum of
in the case of a diagraph where
. If set
then we call G, a complete graph.
In
, a sequence of elements of V, denoted,
is said to form a walk W of length r, if
and if
then we call it a closed walk. If all vertices and edges occur in a walk
are distinct and do not repeat then we call it a path
between
and
. By the length
we mean the number of edges between
and
. By a distance
between the vertex
and the vertex
, we mean the length of the shortest path from
to
. If no path exists between
and
then we set
.
A graph
is said to be disconnected if there exists a pair
such that there is no path between them. Note that a path of length 1 between
to
is called the edge joining
and
. If every pair of vertices
,
has a path between them in G, then it is called a connected graph. A network or a diagraph is said to be weakly connected if between each pair of vertices there is an undirected path. A diagraph is called strongly connected if from each vertex to every other vertex there exists a directed path. Figure 2 provide instances of various forms of graphs.
By a bipartite graph, we mean a graph,
, where V is split into
with
in case (
and
) or (
and
). If
Figure 2. Various forms of graphs. (a) Undirected, connected graph; (b) Directed, weakly connected graph; (c) Undirected, disconnected graph; (d) Undirected, complete graph.
multiple edges are present between two vertices, then we call it a multi-edge graph. A graph is called a simple graph if it contains no multiple edges. Along with a vertex set V, a hypergraph comprise a set E of hyper edges where a link can join more than one vertex. A disjoint union of complete graphs forms a cluster and a complete subgraph of a given undirected graph is called a clique. Figure 3 provides instances of some more forms of graphs. One can refer to [1] [2] for graph theory terminologies.
2. Graph Parameters and Methods
By allowing graphs as the underlying model to depict relationships between objects Graph Theory gives a number of ways to study and analyse data. Certain classifications of well tested methods and metrics permit the analysis of topology of networks which are global or local and /or clustered and facilitate propagation of information.
Analysis of topology (global) of graphs enables one to comprehend its network structure, viz., 1) connectivity 2) distribution of edges, 3) magnitude of clustering or 4) distribution of path lengths. The edge density
is a good measure for a network’s overall connectivity. Note that a complete graph emerges when
takes the value 1 and a sparse graph emerges when
is much smaller than 1. We define max
as the diameter D of the graph and
as the mean path length L of the graph. If L varies as
then G is said to denote a small-world network. The small-world attribute conveys the information that any vertex
in the graph can be reached from a given vertex
by making use of only a small number of links.
Degree distribution is a vital parameter to describe a graph. We call a vertex ur is a neighbour of vertex us, if
, and the number of neighbours ur has is refereed as degree centrality (DC) of that vertex. the DC of vertex ur in an undirected graph is
where s = 1 to n and for a digraph we introduce DCin and DCout referred respectively as the in-degree/out-degree and write
where s = 1 to n and
where s = 1 to n. The probability
can be mathematically modelled through power law
Figure 3. (a) A bipartite graph; (b) Complete bipartite graph; (c) A multi edge graph; (d) A hypergraph; (e) A cluster; (f) A clique of size 4.
distribution
and the graph in such an instance is said to be free of any scale. This means that in such a free of any scale network one can find a large number of vertices with small degree and fewer numbers of vertices with large degree. On the other hand if all the vertices of a graph tend to have almost the same degree around a mean degree value “t” then we call such a graph a random graph. A random graph is indicated by
with
and p, a probability for every edge possible. DC then can be described through binomial distribution
and in the case when t is much smaller than n, one can describe it through Poisson distribution
.
A probe on topological (local) properties of graph permits recognition of substructures or vertices with specific features. For example, an innumerable metrics can be seen in literature to set vertex priorities exploiting connectivity pattern. Betweenness centrality (BC) of a vertex
is:
; (
). Here
stands for the path count of least length from
to
and
stands for the path count of least length from
to
that comprise
.
Based on data modelled, edges may be oddly distributed in the graph, yielding an irregular topological network. For example, the graph might show group of vertices called modules that exhibit to each other a high degree of connectivity in comparison with the others in the network. In such cases graph clustering comes in handy. It is concerned with following distinct approaches to locate substructures that partition a given graph into subgraphs.
Characteristic path length L is the estimated path length defined as:
and
, with
and
where
is the estimated distance among vertex i and every other vertex in the network,
is the path of shortest length,
is a join between i and j. The inverse of the characteristic path length is the efficiency
. The clustering coefficient is a proportion of vertex’s neighbors that are neighbors of each other and it is a measure of segregation:
where
is the clustering coefficient of vertex,
and
and ki is the degree count of vertex i,
where
is the status of connection between i and j when an edge joining i and j is present. The small-world effect is
where C and Crandom stands for the un-randomized and randomized mean clustering coefficients, while L and Lrandom stands for the un-randomized and randomized characteristic path lengths. Normalizing the clustering coefficient by determining the proportion of the clustering coefficient to the clustering coefficient computed in 100 simulated random networks and marked by
. Then the path length after normalization was the proportion of the path length to the path length computed in 100 simulated random networks, and marked by
. See Table 1 and Figure 4.
Motifs are subgraphs of a smaller size of a larger graph that appear any number of times in a directed and/or undirected network to capture patterns of interactions between vertices [3]. These are used for many applications in brain networks [4]. Motif analysis is vital to understand building blocks associated with neuronal communication.
Graphs are excellent tools for biomedical research to spell out the associations among biological entities like diseases, drugs, proteins, genes, ligands, small molecules, metabolites etc. They capture both the functions and molecular interactions
Table 1. Indicator for certain graph connectivity parameters/centrality measures.
Figure 4. Graphical visualization of certain Graph/Network properties. (a) Degree; (b) Clustering coefficient, C; (c) Characteristic path length, L; (d) Betweenness.
from or within cells to a complete organ. These are networks pointing to: Sequence Similarity; Gene Regulation; Signal Transduction; Metabolic; Gene Co-expression; Disease etc.
The links among causative genes in a disease network can be formed depending on counsel from OMIM-Online Mendelian Inheritance in Man associations. Bipartite graphs serve as good models [5]. The Disease symptom graphs relate diseases with their symptoms and explain their evolution and aid clinicians to choose appropriate treatment swiftly [6]. By depending on medical records one can generate by employing concept retrieval of cause and effect in traditional sense of disease symptom graphs.
3. First Announcement of AD
We are very grateful to James M. Ellison for nicely describing the history of Alzheimer’s disease in [7]. We provide here a brief outline of his exposition. Emil Sioli brought to the notice of Alzheimer’s, the death of one of his patients Auguste Deter by sending her brain material. Alzheimer’s examined her brain material microscopically with new stains to announce what we coin as amyloid plaques and neurofibrillary tangles.
4. Comprehending Alzheimer’s Disease
“Cholinergic hypothesis” of Alzheimer’s disease was propounded in the late 1970’s. It describes the symptoms of this disease is due to the deficiency of acetylcholine, the neurotransmitter, vital for proper function of the memory. But to our dismay this type of cure has not more than a little impact on progression of disease. The discovery of a protein of beta-amyloid kind in 1987 in Down syndrome noticed patient’s blood vessels and Alzheimer’s disease revealed the chromosome of 21st type and provides us a path to the comprehension of Alzheimer’s disease pathology. Then in 1990’s mutations discovery responsible for excessive secretion of protein of beta-amyloid kind with Alzheimer’s disease led to the “amyloid cascade” hypothesis responsible for inflammatory response and brain cell destruction. Also there are other theories that insist the pertinence of taking into account the “tau” protein abnormalities. But in Alzheimer’s disease the protein named after tau is abnormal and leads to the structural collapse of microtubule. However there are other factors such as lifestyle, infections caused by inflammation, blood-brain barrier alterations and metabolism of erroneous type also contribute to the progression of Alzheimer’s disease.
5. Graph Theory for Brain Modelling
Graph theory essays a crucial role to comprehend the structural/functional pattern of complex systems. Pertinently, brain graphs are created from connectivity matrices that are neural based. Note that here each row/column marks a distinct region of brain in the matrix and is deemed as a vertex and the edges correspond to each entry in the matrix. A huge portion of theory of graphs is the systematic outcome of probe about matrices. Graph theory is a good tool for connectomics. See Figure 5 for general description of the process of Brain network construction.Brain network organization aims to lower cost due to wiring. Features that are topological in nature such as modules are mostly co localized, which preserves material in anatomic sense. Features like short characteristic path length are opted to lower delay in conduction, to increase the rate at which counsel is shared among neurons. Hence connectomics refined laws of conservation among reduction of cost of wiring [8].
Ramon y Cajal’s exertion on connectivity of neurons almost paralleled the seminal endeavour to comprehend interconnected networks of macroscopic cortical areas. Theodor Meynert, Carl Wernicke, and Ludwig Lichtheim drew network diagrams to describe connections due to white matter among areas that are cortical centred and to detail how the brain disorder forewarnings are linked to lesions that are pathological. The language replica due to Wernicke Lichtheim is the sought after early replica in macro scale of brain graph organization, connecting a creation area in the cortex at the front to the medium of understanding area in the cortex that is temporal. Certain features specific to this model contribute for the generation of particular forewarning. Specifically, arcuate fasciculus’s lesion joining medium of communication areas that are both temporal and frontal was determined and demonstrated to induce a challenge to respell words that are heard in spite of conduction aphasia. Wernicke extended these notions of brain function as an associative theory, where cognitive abilities of higher-order were deem to emanate from the integration of cortical areas that are intact with respect to connectivity. The 19th century of brain network organization diagrams consisting of vertices denoting circumscribed areas interlinked by edges that denote tracts of white matter, provided the platform to accord graph
Figure 5. Schema chart for construction of brain networks.
theory touch to nervous systems in the same manner as the theory of neurons set the tune for cellular replicas that are graph based [8].
A vast number of vertices denoting cortical or subcortical areas of brain graphs interlinked by edges that are axonal, depend on cat/monkey data. It measures propagation of a signal that are of the axonal type from the injection site to all other regions of brain. Here every endeavour generates connectivity centric data of injection lots and several trials are joined to assess the link magnitude of the nervous system. To find a solution to this issue, the original connectomes were created by consolidating the findings from published literature. These probes also led to systematic endeavours to consolidate and organize tract-tracing probes, the findings recorded in a connectomic data repository database, the CoCoMac.
It was claimed that the small world attribute could meet a dual function. The brain network’s least path length might vote processing of counsel as a whole and high value clustering could vote separated processing cliques of vertices that are of within type. That is, brain’s small-world architecture provides a substrate that is in topological sense for functional separation and accumulation thereby neutralising the riddle regarding whether it could support a single architecture of these opposing tendencies. Further, by rewiring computationally the edges it was demonstrated that PL is linked to cost of wiring. It is estimated by the Euclidean distance among linked vertices, could be decreased by the link rewiring among vertices to lower its real distance. But this leads to increased characteristic path length. This was the compromise among various attributes of the connectome. Hence other existing graph centric probes showed concept centric proof. It established that the tools induced by theory of graphs were adoptable to nervous systems that are made simple. But, these findings were restricted to facts on the cat/macaque. Connectomics took a wiser step with the introduction of pipeline processing that permitted graph centric techniques’ application to data on human aided by neuroimaging technique [8].
Human brain functional/anatomical networks’ first graph theoretic analyses depend on matrix connectivity estimated from MRI and M/EEG data and on knowhow of MRI data that are diffusion centric and tractographic. So trace tract induced brain graphs, structural/functional/diffusion MRI are quite welcome. It is pertinent to observe that these are distinct concepts in several viewpoints. Graph centric probes of connectivity networks have witnessed activities that are neurophysiological over long period with correlation coefficient. Investigated in this manner the connectivity that is functional is in positive correlation with anatomical connectivity. Figure 6 provides a Flow Diagram of states of network of Brain.
It was established through massive degree count that, in MRI graphs of Alzheimer’s disease that, vertices have higher content of amyloid protein in contrast to less central lots of brain in topologically sense. Among a variety of disorders that are neurodegenerative, vertex degree and centrality measures have been positively correlated assessed using MRI in functional connectivity networks with local grey matter atrophy.
In the last few decades graph theoretical viewpoints depending on MRI, MEG, and EEG have widely grown and most of the step by step improvement of connectomics that is concept centric has centred on knowhow of data of human neuroimaging type denoting networks in macroscale. A latest improvement hoped to be trend setting for the coming decades of connectomics, is the abundance of data of high calibre on brain networks at mesoscales roughly 10,000 m and microscales
Figure 6. Flow diagram showing various network’s states.
roughly 1,000,000 m.
In brain connectivity analysis how to substantiate the utility value of graph centric proceed with the given toolkit?
1) What aspect has been investigated in modelling human cognitive abilities of a human and disorders that are psychiatric after the arrival of graph theory in cognitive neuroscience?
2) In graph-based probe on human connectome what topics are pertinent for further investigation?
6. Further Scope
First we wish to eliminate the factors such as data based on resting-state, the impact of conduction which is volume based in MEG knowhow that are sensor-space centric, and feature selection that has affected the outcome measures and subsequent interpretations done in [9] and we intend to investigate systematically the effect of coupling measures on graph analysis results. Then we wish to apply other measures, explaining network clustering properties. Then we propose to compare the findings obtained in [9] with the spectral results in graphical sense on other measures of connectivity that are functional, datasets on specific tasks, or various conditions for disease. From the view point of clinical sense the criticizing factors are small sample size, disease of heterogenic type, comorbidity and the application of psychoactive medication. We would definitely make changes in these with choice of selection of patients from India. We aim to EEG activity analysis done in [10] to almost double the patients with dementia due to AD and with the help of CC and PL. Then we propose characterization of mechanisms in AD that are neural. In [11] Graph Regression Model depended framework was suggested to know the structure of neuroimaging data. We wish to use other available statistical models to enlarge the knowledge domain of AD. We describe briefly here about the current status of the graph-based probe on human connectome and recommend the readers to [12] for more. One can model the human brain as a network referred as the human connectome) [13]. Here different lots of the brain are the vertices and the relation describing adjacency between them is called as links or the edges. The links can be thought of as diffusion tensor imaging (DTI) obtained through magnetic resonance imaging (MRI), EEG, MEG or functional MRI, fMRI that are arterial spin labelling (ASL) enabled blood flow with dependencies in time series that are statistical. Through this a connection matrix evolves and the concept of small-worldness provides the balance among short-distance and long-distance connectivity. BRAPH is a popular software package widely used off late in brain connectome projects. It is written in Matlab. It is both open source and object oriented. It is applied with a graphical user interface (GUI) for graph theoretical analysis. This software can be employed to assess network topology on Alzheimer’s disease affected patient’s structural MRI data. It can also compute 1) degree distribution of the vertices in such a massive brain graph and such a distribution follows power law as examined on patients largely of European origin and we intend to verify the same by making use of data taken from patients in India 2) the shortest distance among two vertices by which we mean the least number of links required to reach a given vertex from a given vertex 3) the characteristic path length by which we refer to the estimate of the minimum path lengths among one vertex and all other vertices 4) the centrality due to closeness, that stands for the reciprocal of the least path length 5) the betweenness centrality, that denotes the proportion of all least paths that pass through a given vertex in the network. Such computation helps us to determine whether a vertex is a brain hub. If the vertices are close to each other and the path length is shorter than the transfer of information between them will be highly efficient. To determine the efficiency due to communication among a vertex and its close links, the local measure of efficiency can also be found. It can be estimated over all vertices to explain main attributes of the brain network. 6) The C is a vital tool that determines the cliques (complete subgraphs). For each vertex, this can be computed as the ratio of the vertex's adjacencies that are also adjacents of each other. For the network in full, the C of all vertices can be pooled into the mean C. 7) Mean C is the proportion of paths that transverse 2 links by the triangle count. If a vertex is linked to another vertex, and it is in turn linked to a 3rd one, the transitivity property spells the probability that the first vertex is linked to the 3rd. 8) Modularity concept can be employed to find the feasibility to which a network has been grouped into distinct lots and it also bloats the edge count within lots and keep down the number of links among distinct lots. 9) z-score in a module that are of within type to calculate how well a vertex is joined with others 10) the participation coefficient determines whether a vertex has several links with vertices from distinct modules. It is presumed that if a vertex has a large degree count of within-module type then it is named as a temporary fulcrum and in case if it has a large participation value for coefficient then it is called a linker fulcrum.
We very much intend to understand the disruptions in the structural brain networks of Alzheimer’s disease affected patients from Indian hospitals k-cores where one can observe drastic alterations among the white matter integrity in the left hemisphere of affected patients. We propose to establish that graph metric measures can function as a distillation of the brain’s network.
7. Conclusion
So graphs are highly simple models through which the intricacies of the brain are transformed to mere vertices and edges. This feature is a unified choice in “big data” era in the presence of an impending danger of getting drowned by voluminous data. Underlying mathematics of graphs is adoptable and amenable to life scientists who lack quantitative sciences. A graphical view of brain has the possibility of yielding a conceptual model through an easily comprehensible medium of communication.
Abbreviations and Acronyms
PL―Path Length
CC―Central Coefficient
BC―Betweenness Centrality
AD―Alzheimer’s Disease
EEG―Electroencephlography
MRI―Magnetic Resonance Imaging
fMRI―functional Magnetic Resonance Imaging
rsfMRI―resting state functional Magnetic Resonance Imaging
ASL―Arterial Spin Labelling
MEG―Magnetoencephalography
NIBS―Non-Invasive Brain Stimulation