Arts and Sciences, Irving K. Barber School of (Okanagan)
DSpace
UBCO
Soni, Gunjan
Master of Science - MSc
University of British Columbia
Time series have been extensively studied and used in many fields to describe time-dependent observations such as rainfall levels, stock market, and even our brain signals. In this thesis, we extend previous network based approach to the analysis of time series, by introducing signs to the edges that describe the visibility graph. The resulting signed visibility graph contains more information about the properties of time series than standard visibility graphs. We designed a dynamic programming algorithm that creates optimal, non-overlapping and time-respecting clusters/partitions in signed visibility graphs. Our method differs from existing approaches of standard network partitioning or community detection methods that do not take into consideration the time-order in a visibility graph. Our signed visibility graph approach can also be used to define mutual information based measure for comparing the correlation between two time series. By taking into consideration the information of a node due to both positive and negative edges in the graphs, our measure is more accurate than the existing correlation measure. As an application, we applied our framework of signed visibility graph to brain networks and studied the clustering of brain time series for various sets of patients suffering from ADHD, Schizophrenia, Bipolar Disorder, and Epilepsy (with & without seizures), compared with normal human brain signals. For fMRI data, these comparisons are done on various levels: starting from individual Regions of Interest (ROIs) of the brain, to groups of ROIs, and lastly to Resting State Networks (RSNs; brain sub-networks/regions). These comparisons gave some interesting results showing differences in various metrics of brain network. For instance, differences were found in the average number of clusters, cluster size, average mutual information measure, average jaccard index values of clusters, with extreme values in certain sub-networks and in certain disease-sets, etc.
Signed Visibility Graphs of TimeSeries and their application to BrainNetworksbyGunjan SoniB.Tech., Mody University of Science and Technology, India, 2016A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)April 2019c Gunjan Soni 2019The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Signed Visibility Graphs of Time Series and their application to BrainNetworkssubmitted by Gunjan Soni in partial fulfilment of the requirements of thedegree of Master of Science.Dr. Yong Gao, Irving K. Barber School of Arts & SciencesSupervisorDr. Heinz Bauschke, Irving K. Barber School of Arts & SciencesSupervisory Committee MemberDr. Bowen Hui, Irving K. Barber School of Arts & SciencesSupervisory Committee MemberDr. Ying Zhu, Faculty of ManagementUniversity ExamineriiAbstractTime series have been extensively studied and used in many fields to describetime-dependent observations such as rainfall levels, stock market, and evenour brain signals. In this thesis, we extend previous network based ap-proach to the analysis of time series, by introducing signs to the edges thatdescribe the visibility graph. The resulting signed visibility graph containsmore information about the properties of time series than standard visibilitygraphs.We designed a dynamic programming algorithm that creates optimal,non-overlapping and time-respecting clusters/partitions in signed visibilitygraphs. Our method diâµers from existing approaches of standard networkpartitioning or community detection methods that do not take into con-sideration the time-order in a visibility graph. Our signed visibility graphapproach can also be used to define mutual information based measure forcomparing the correlation between two time series. By taking into consid-eration the information of a node due to both positive and negative edgesin the graphs, our measure is more accurate than the existing correlationmeasure.As an application, we applied our framework of signed visibility graphto brain networks and studied the clustering of brain time series for varioussets of patients suâµering from ADHD, Schizophrenia, Bipolar Disorder, andEpilepsy (with & without seizures), compared with normal human brain sig-nals. For fMRI data, these comparisons are done on various levels: startingfrom individual Regions of Interest (ROIs) of the brain, to groups of ROIs,and lastly to Resting State Networks (RSNs; brain sub-networks/regions).These comparisons gave some interesting results showing diâµerences in var-ious metrics of brain network. For instance, diâµerences were found in theaverage number of clusters, cluster size, average mutual information mea-sure, average jaccard index values of clusters, with extreme values in certainsub-networks and in certain disease-sets, etc.iiiLay SummaryTime series is a sequence of values that change with respect to time. Graphsare represented in the form of points and lines, and a line is used to connecttwo points. In order to study the characteristics of time series, they areconverted to data structures called visibility graphs in which points are thetime-series values and lines are drawn based on the type of visibility graphused. We introduced signs to the lines depending on the location of twopoints with respect to each other. We also designed an algorithm to grouppoints in a visibility graph, based on their positive and negative lines, makingsure that points within a group are continuous and groups follow time-constraint. We also created a formula to measure relation between twovisibility graphs. We applied these concepts on the analysis of brain-networkdata (fMRI and EEG).ivPrefaceThe work in this thesis has been accepted for a poster presentation atthe International School and Conference on Network Science (NetSci) 2019,Burlington, Vermont, USA.Two copyrighted figures have been reprinted in this thesis with permis-sion of [25] and [46] respectively.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Graphs & Networks . . . . . . . . . . . . . . . . . . . . . . . 42.2 Time Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Visibility Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Signed Networks . . . . . . . . . . . . . . . . . . . . . . . . . 82.5 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.6 Brain Networks . . . . . . . . . . . . . . . . . . . . . . . . . 102.7 fMRI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.8 EEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Signed Visibility Graphs . . . . . . . . . . . . . . . . . . . . . 133.1 Definition and motivation . . . . . . . . . . . . . . . . . . . . 133.2 Algorithms for creating visibility graphs . . . . . . . . . . . . 15viTable of Contents3.2.1 Basic Algorithm . . . . . . . . . . . . . . . . . . . . . 153.2.2 Horizontal Signed Visibility Graph Algorithm . . . . 173.2.3 Divide and Conquer Algorithm . . . . . . . . . . . . . 204 Partitioning Algorithm . . . . . . . . . . . . . . . . . . . . . . 234.1 Time-respecting Clustering . . . . . . . . . . . . . . . . . . . 234.2 Algorithm for Time-respecting Clustering . . . . . . . . . . . 244.2.1 Dynamic Programming . . . . . . . . . . . . . . . . . 244.2.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . 254.3 Comparison with Louvain Algorithm . . . . . . . . . . . . . 274.3.1 Louvain Algorithm . . . . . . . . . . . . . . . . . . . 274.3.2 Methods and Results of Comparison . . . . . . . . . . 294.4 Importance of Signed Edges and Time-respecting Constraint 335 Multivariate Correlation . . . . . . . . . . . . . . . . . . . . . 365.1 Multivariate Time Series . . . . . . . . . . . . . . . . . . . . 365.2 Interlayer Mutual Information . . . . . . . . . . . . . . . . . 376 Application to Brain Network Analysis . . . . . . . . . . . . 446.1 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . 446.1.1 Data and Preprocessing Techniques . . . . . . . . . . 446.1.2 Neurological Disorders . . . . . . . . . . . . . . . . . 476.2 Analysis of fMRI Data . . . . . . . . . . . . . . . . . . . . . 486.2.1 fMRI data . . . . . . . . . . . . . . . . . . . . . . . . 486.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . 496.3 Analysis of EEG Signals . . . . . . . . . . . . . . . . . . . . 586.3.1 EEG Data . . . . . . . . . . . . . . . . . . . . . . . . 586.3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . 597 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63AppendixA Implementation Programs . . . . . . . . . . . . . . . . . . . . 68viiList of Tables5.1 Comparative results of multivariate correlation equations . . 405.2 Comparative results of values by MI equations . . . . . . . . 43viiiList of Figures3.1 Signed Visibility Graph . . . . . . . . . . . . . . . . . . . . . 143.2 Signed Natural Visibility Graph example . . . . . . . . . . . . 163.3 Signed Horizontal Visibility Graph example . . . . . . . . . . 193.4 Signed Visibility Graph by Divide and Conquer algorithm . . 204.1 Example of Partitioning . . . . . . . . . . . . . . . . . . . . . 284.2 Sample fMRI time series . . . . . . . . . . . . . . . . . . . . . 294.3 Comparison between Louvain algorithm and our algorithm . . 304.4 Louvain Algorithm clustering examples . . . . . . . . . . . . . 314.5 Weak clusters by Louvain algorithm . . . . . . . . . . . . . . 324.6 4 cases of clustering . . . . . . . . . . . . . . . . . . . . . . . 345.1 Multiplex visibility graph from multivariate time series . . . . 375.2 Mutual Information values scatter plots . . . . . . . . . . . . 395.3 Mutual Information between 4 time series . . . . . . . . . . . 426.1 Yeoâs parcellation . . . . . . . . . . . . . . . . . . . . . . . . . 456.2 ROI level plots of avg. number of clusters . . . . . . . . . . . 496.3 Groups of ROIs level plots of avg. number of clusters . . . . . 506.4 Comparison with Louvain algorithm (groups of ROIs) . . . . 526.5 Groups of ROIs level histogram of Jaccard Index values . . . 536.6 Groups of ROIs level violin plots of MI values . . . . . . . . . 546.7 Groups of ROIs level violin plots of MI values (unsigned) . . 566.8 RSN level pirate plots of number of clusters . . . . . . . . . . 576.9 RSN level violin plots of mutual information values . . . . . . 586.10 EEG bar-scatter plot of number of clusters . . . . . . . . . . 596.11 EEG box-scatter plot of Jaccard Index . . . . . . . . . . . . . 606.12 EEG box plot of average cluster-size . . . . . . . . . . . . . . 61ixList of ProgramsA.1 Program for Natural Signed Visibility Graphs . . . . . . . . . 68A.2 Program for Horizontal Signed Visibility Graphs . . . . . . . 70A.3 Program for Divide and Conquer algorithm . . . . . . . . . . 71A.4 Program for Partitioning algorithm . . . . . . . . . . . . . . . 73xAcknowledgementsFirst of all, I would like to thank my supervisor, Dr. Yong Gao for hisesteemed guidance and support from the very beginning of my graduatestudies. His immense knowledge, motivation, enthusiasm and patience hasbeen extremely helpful all the time in the research and writing of this thesis.I am deeply grateful to have him as the advisor and mentor for my mastersstudy.I am thankful to Dr. Daniele Marinazzo, Ghent University, for being soresponsive and helping me learn the aspects of neurological data-processing.I would also like to thank every faculty member in the university whohave taught or guided me in any way. The knowledge given by them hasbeen reflected in this thesis in one way or another.I am also grateful to my fellow graduate students who I have interactedwith, for any help and contribution in my masters program.xiDedicationI would like to dedicate this thesis to my parents Dr. Rekha Soni and Dr.Suresh Chand Soni, and my fiance´ Krishna Gupta. Without their support,I wouldnât have been able to pursue my dreams and interests. They havebeen the wind beneath my wings and I can never thank them enough.I would also like to thank my friends in Kelowna and India for beingthere whenever I needed them.xiiChapter 1IntroductionIn our interconnected world, almost anything within or around us, or anytechnology that we interact with involves a network in one way or another.For instance, there are basic networks such as electricity and roads, so-cial networks, communication networks such as telephones and advertising,organizational networks such as the government, the internet, biological net-works such as our blood vessels, and even our brains [31]. The history of thestudy of networks goes back to the 18th century when they were used forglobal trade and commercial purposes. Since then there has been an expo-nential growth in the discovery and invention of diâµerent types of networks.The field of network science combines ideas from mathematics, physics, biol-ogy, computer science, statistics, social sciences, and many other areas usingmore complex networks in real world.In addition to networks, time series are also frequently used to modelphenomena where properties change over time. A time series is a sequenceof data values taken at successive equally spaced points in time; it is asequence of discrete-time data, for example, rainfall levels, stock market,and our brain signals. In order to analyze and extract meaningful statisticsand other characteristics of time series data, certain methods of analysis areapplied. One of the recent developments of new methods in exploitationand analysis of the time series is visibility graphs [26, 28] by which a timeseries is characterized as and mapped to a network. This approach helps touse the tools of network science for describing the structure and underlyingdynamics of time series.The task of grouping a set of nodes or vertices in such a way that nodes inthe same group or cluster are more similar to each other (according to somenode metric or feature) than to those in other groups, is termed as clusteringor community detection. This problem is computationally hard in generaland is extensively used in many fields, including machine learning, patternrecognition, image analysis, bioinformatics, etc. Cluster analysis can beachieved by various algorithms that diâµer significantly in their understand-ing of what constitutes a cluster and how to eciently find them. Some suchpopular algorithms are Newmanâs Network Modularity algorithm [30] that1Chapter 1. Introductiondefines modularity based on edge-density, taking a diâµerence of fraction ofedges within a partition and fraction of edges incident to a partition; Girvan-Newmanâs method [12] that involves iterative removal of nodes with highvertex-betweenness value to form communities; Neighbour-Joining method[40] which follows a bottom-up approach and creates clusters between nodeswith least distance; and Louvain algorithm [5] that will be discussed later.All these algorithms can be used for partitioning visibility graphs but theydo not take into account the time-dependency of each node in the network,and therefore do not provide with a solution specifically for visibility graphs.Based on graph theory, there have been many recent developments inthe analysis of complex networks quantitatively and these have been rapidlytranslated to studies of both anatomical and functional brain network or-ganization. Human brain networks, derived from MRI and electrophysi-ological data, follow complex network characteristics like small-worldness,have high-degree cortical âhubsâ and modular & hierarchical properties [7].The existence of these hubs have resulted in the division of the whole brainnetwork into several sub-networks that are spatially non-overlapping andfunctionally distinct. Data from the brain, taken in the form of magneticimaging or electrical signals, are in the form of time series, and therefore, isused to apply the aforementioned notions to gain some fruitful results.The main contribution of this thesis is the proposal of signed visibil-ity graphs that generalize the notion of a visibility graph. The conceptof a signed visibility graph is also used to remodel the mutual-informationmeasure for multiplex networks [25]. With the signed-visibility-graph-basedmeasure, we observe diâµerences in the obtained value compared with originalmeasure value, due to the consideration of negative edges. We designed andimplemented a dynamic programming algorithm for partitioning a signedvisibility graph into clusters that respect the temporal constraint imposedby the time series. The implementations and algorithm are then applied todata taken from brain signals (fMRI and EEG) of healthy persons and pa-tients suâµering from ADHD, Schizophrenia, Bipolar Disorder and Epilepsy.The results gathered from each patient-sets are then compared with the re-sults of healthy persons as well as with other patient-sets to generate someinteresting observations.In Chapter 2, we give an overview of the preliminary terminologies re-quired for understanding the ideas discussed in the thesis. In Chapter 3,we discuss the concept of signed visibility graph along with an explanationof the methods involved in its creation and their properties. In Chapter 4,we discuss the visibility graphs partitioning algorithm and its applicability.Chapter 5 sheds light on an application of the signed visibility graphs: mu-2Chapter 1. Introductiontual information in multivariate visibility graphs along with a comparativediscussion of the diâµerence in the correlation value of signed and unsignedvisibility graphs. In Chapter 6, we put forward all the results of the researchand apply the partitioning algorithm and mutual information on brain sig-nals data with a detailed discussion of diâµerences in cluster numbers, clustersizes, mutual correlation measure, and jaccard index values between the clus-ters of healthy persons and patients with considered mental and neurologicaldisorders. In Chapter 7, we summarize our results and mention the futuredirection.3Chapter 2PreliminariesIn this chapter, we explain some background material and notions for un-derstanding the discussions of the chapters to follow.2.1 Graphs & NetworksA network represents mutual interactions/connections among diâµerent ob-jects/members. These objects are called vertices/nodes while the inter-actions are indicated by edges/links. A well known example is ZacharyâsKarate Club, as mentioned in [47], which is a social network with membersof the club represented by nodes and the links between them representingtheir friendship or interactions.Graphs are mathematical abstractions of networks. A graph G = (V,E)is a structure with a set of vertices V and connecting those vertices is a setof edges E [10, 11]. An edge e 2 E between two nodes u, v 2 V can bewritten as e = (u, v). An edge can have a number of attributes that definethe relation between the nodes it is linking, like sign, direction, weight etc.For example, a positive edge between two nodes in a graph used to modelsocial network may indicate friendly relations between the two members, anda negative edge may indicate enmity. Depending on the type of network,there may be multiple interpretations of the same attribute. Edges canhave weights too, which signify either a parameter or the degree of linkbetween the two nodes an edge is connecting, depending upon their usage.For example, in a highway network, the weight of an edge may representdistance, cost to travel that distance or the travel time between two cities.A well-known problem is to minimize either the cost or the time, or to findshortest path between two given cities.Based on the attribute of direction, we have two types of graphs: undi-rected and directed. An undirected graph is simply defined by G = (V,E),where the edges in E are represented as {u, v}, have no direction, form anunordered set, and represent symmetric relationships. In a directed grapheach edge (u, v) 2 E has an added direction attribute with u being the sourcevertex, v being the target vertex and each edge represents an asymmetric42.2. Time Seriesrelationship. If a consecutive pair of nodes are connected to each other byan edge, then they are called neighbours of each other. A path in a graph isa sequence of nodes following the property that each consecutive pair in thesequence is a pair of neighbours. The degree of a vertex u, as denoted by du,is the number of edges incident to it, or the number of distinct vertices it isconnected to. For directed graphs, there are two types of degrees, in-degreeand out-degree. Out-degree is the number of distinct edges having a vertexv as the source and is denoted by dout(v). Similarly, in-degree is the numberof distinct edges having a vertex v as the target and is denoted by din(v).The probability distribution of the degrees over the whole network is calledthe degree-distribution of that network. Mathematically, the degree distri-bution P (k) of a network is defined to be the fraction of nodes with degreek. Therefore, if there are a total of n nodes in a network and nk of themhave degree k then, P (k) = nk/n.A network that evolves with time t is called a dynamic network and isdenoted by Gt = (Vt, Et). A network H = (V 0, E0) is called a subnetwork ofa network G = (V,E) when V 0 â V and E0 â E. A small-world network isa graph in which there are short average path lengths, high clustering andan abundance of hubs [45]. In such networks, most nodes are not adjacentto each another, but there are high chances of the neighbours of a node tobe neighbours of each other and by a small number of hops or steps, mostnodes can be reached from every other node.2.2 Time SeriesA time series is a series of data points that are listed or indexed accordingto time order. Basically, any value that can change with time would form atime series. The analysis of time-series applies to many fields such as eco-nomics (unemployment, consumer price index, population, gross nationalproduct, and production), natural sciences (water level index of a lake, airtemperature, size of natural population, etc.), physical sciences and math-ematics (designs for airplanes and rockets, improvement of radar and otherelectronic devices, and investigation of certain production and chemical pro-cesses) [16], and biological sciences (blood sugar levels, growth of foetus, andbrain signals).There are two types of time series: discrete and continuous. Discretetime series values are recorded or observed at fixed time intervals, for exam-ple, monthly data of lake water levels. Continuous time series are observedcontinuously within a specific time interval, for example, recording of EEG52.3. Visibility Graphsvalues for a span of 60 seconds [6].Based on the number of variables involved, time series are of two types:univariate, and multivariate. A univariate time series has just one variable,that has a changing value with respect to time, for example, the stock valueof a company. A multivariate time series has more than one variables thatare represented in the same series, where each variable has a particular valueat each time point. Multivariate time series can be seen as a combination ofmore than one univariate time series. For example, changing weather con-ditions (involving dew, temperature, pressure, pollution, rain, wind speed,etc.) for a particular location [22].2.3 Visibility GraphsVisibility graphs have been largely used to check âvisibilityâ in polygons:the visibility graph of a simple polygon is a graph whose vertices correspondto the vertices of the polygon and two vertices have an edge between them ifthey can âseeâ each other [14], according to some criteria. The polygon visi-bility graphs have been used in solving a number of real-world problems suchas architecture and urban planning (art-gallery problem). Visibility graphscan also be defined on time series in which the nodes are time points, andtwo nodes are linked if they have a visibility between each other accordingto the type of visibility graph used. Multilayer networks are networks thatincorporate multiple types of interactions between the same nodes. Uni-variate time series are mapped to a single visibility graph, but for mappingmultivariate time series, multilayer visibility graphs are used, which will bediscussed more in Chapter 5.There are diâµerent types of visibility graphs and the following is a briefdescription of a few of them.Natural Visibility GraphGiven a time series of N data, we take any two time points i and j for whichthe measured quantity values are yi and yj , respectively. These two pointsare said to be visible to each other and will become two connected nodes inthe associated Natural Visibility Graph (NVG) if any other data point ykplaced between them fulfills [26]:yk < yi + (yj  yi)k  ij  i . (2.1)62.3. Visibility GraphsA natural visibility graph is defined on time points if they have visibilityaccording to the above condition. The visibility graph associated with atime series is always connected (as each node has a visibility with at least itsnearest neighbors), undirected, and invariant (under several transformationof the time series either by rescaling of the axes or under horizontal andvertical translations).Horizontal Visibility GraphTwo time points i and j, in which the measured quantity takes values yiand yj , respectively, will have Horizontal Visibility if any other data pointyk placed between them is smaller [28]:yk < min{yi, yj},8i < k < j (2.2)In the horizontal visibility graphs (HVGs), if between yi and yj a horizontalline is drawn and it does not intersect with any intermediate data height,then the nodes i and j are connected. The resulting HVG is simply asubgraph of its corresponding NVG.Divide-and-Conquer Visibility algorithmA visibility graph can be constructed by checking inequality (2.1) for eachpair of time points. A more ecient algorithm is based on the idea of divideand conquer technique [27]. Within each time series y1, . . . yn, a node k withmaximum value is found which divides the time series into two separateparts - left and right. In each step, the connections of k with other nodesare created based on its âvisibilityâ with other nodes and there is a recursionof these steps until no further division can happen. Following the above twosteps, all nodes in the time series are considered, and the time complexityof visibility graph creation is highly reduced.Sort-and-Conquer Visibility algorithmA more recent iterative visibility algorithm is proposed in [17] which consistsof two stages. In the first stage, data elements are sorted in a list in descend-ing order according to their y values. In each iteration, one node k taken inorder from the list is considered and is joined with other nodes based on aninterval. This interval includes nodes that are positioned between the nodesk is already joined with (due to previous iterations; null for first iteration).The visibility between k and elements of the interval is then checked, edgesare drawn if it exists, and network is updated accordingly.72.4. Signed Networks2.4 Signed NetworksThe concept of signed networks, or graphs with positive and negative edges,has been popular in the field of social networks, with the ties of friendsdenoting positive edges and ties of enemies denoting negative edges. Thesame concept can be applied to other networks too with diâµerent denota-tions, while the fundamental idea remains the same - adding signs to edges.In these networks, the term switching-a-vertex means negating the signs ofall the edges incident to that vertex and switching-an-edge means negatingthe sign of that edge.There are various notions to define balance of a signed graph, and someof them are quite contrasting. The definition of âstrongâ balance says thatG is a balanced network if, and only if, there are even number of negativeedges in every cycle of G. The âweakâ definition of balance, by contrast,says that a network is balanced if, and only if, there is no cycle that has onlyone negative edge [23]. Another definition given by Harary [20] says that anynetwork that is clusterable, displays perfect strong balance. Which meansthe networkâs nodes can be divided into some number of non-overlappingsets such that all edges within the sets are positive and all edges betweenthe sets are negative. Thus, a network possessing insularity or cliquishnesscan be characterized as a strongly balanced network. We would work on thesame principle of dividing a signed network into clusters to form a weaklybalanced visibility network in Chapter 4.2.5 ClusteringCommunity detection, or clustering, is the term used for organizing ver-tices to clusters, with many edges joining vertices of the same cluster andcomparatively few edges joining vertices of diâµerent clusters. Such clus-ters, or communities, can be considered as fairly independent entities of agraph, being functionally diâµerent from each other. Detecting communitiesis of great importance in sociology, biology and computer science, disciplineswhere systems are often represented as graphs [15]. There exist many formsof clustering in our day to day life - clustering of players to form teams, clus-tering in protein-protein interactions, clustering of hyperlinks in webpages,etc.Clustering is a partition of the vertex-set V into subsets C1, C2, . . . Cn ,where n is the number of clusters in V , such that each positive edge joinstwo nodes in the same subset and each negative edge joins two points from82.5. Clusteringdiâµerent subsets. Since real-world examples do not showcase this strongpartitioning, there is a slight modification to this definition stating, thegraph is divided into subsets such that most of the edges within a subset arepositively signed and most of the edges between two subsets are negativelysigned. In our work, we have used this modified or weakly balanced definitionof clustering.Let us start with a subset C of a graph G. The following details arementioned in [15] but we have modified it a little to suit the explanationfor our work. We define 4 parameters to indicate the internal and externaldegrees of vertex v 2 C, kpintv , the number of positive edges v has internalto the cluster C, kpextv the number of positive edges v has external to thecluster C or with other clusters, knintv the number of negative edges v hasinternal to the cluster C, and knextv the number of negative edges v hasexternal to the cluster C. Now, for v to be a part of the cluster C, it shouldfulfill the following:1. kpintv > kpextv , i.e., the number of positive edges of v should be greaterwithin the cluster2. knextv > knintv , i.e., the number of negative edges of v should be greateroutside the clusterNow considering the cluster C as a whole, we define a few more terms, intra-cluster positive density, pint(C) which is the ratio between the number ofinternal positive edges of C and the number of all possible internal edges,and intra-cluster negative density, nint(C) which is the ratio between thenumber of internal negative edges of C and the number of all possible internaledges, i.e.pint(C) =#+ ve internal edges of Cnc(nc  1)/2 , (2.3)nint(C) =# ve internal edges of Cnc(nc  1)/2 (2.4)Similarly, inter-cluster positive density, pext(C) which is the ratio betweenthe number of positive edges from the vertices of C to the rest of the graphand the maximum number of inter-cluster edges possible, and inter-clusternegative density, next(C) which is the ratio between the number of negativeedges from the vertices of C to the rest of the graph and the maximumnumber of inter-cluster edges possible, i.e.pext(C) =#+ ve inter cluster edges of Cnc(n nc) , (2.5)92.6. Brain Networksnext(C) =# ve inter cluster edges of Cnc(n nc) (2.6)The average positive link density p(G) is the ratio between number of posi-tive edges of G and maximum number of possible edges n(n1)/2. Similarlyfor negative edges we have the average negative link density n(G). Now wehave four conditions for C to be a community or cluster,1. pint(C) > p(G), nint(C) < n(G)2. pext(C) < p(G), next(C) > n(G)The goal of most clustering algorithms, implicitly or explicitly, is search-ing for the best tradeoâµ between a large pint(C) and a small pext(C)and/or a small nint(C) and a large next(C). A simple way to do that is,e. g., maximizing the sum of the diâµerences pint(C)  pext(C) and/ornext(C) nint(C) over all clusters of the partition. More discussion onthis is done in Chapter 4.By observation, visibility graphs have been found to have a modularstructure in which subnetworks are constituted by time points that aremainly adjacent. After partitioning the visibility graph there is a naturaldecomposition of the time series into smaller time intervals.2.6 Brain NetworksThe central organ of the human nervous system is the brain. Despite hav-ing a fixed anatomy, most of the physical and mental actions of the body,processing, integrating, etc. are done by the brain. It also acts as a coordi-nator of the information it receives from the sense organs, deciding all theinstructions sent to the rest of the body as a response to the informationor action-reaction pair. These innumerable functionings may be a result ofbrainâs network architecture being hierarchical and modular, which orga-nizes local interactions and ensures adaptability, damage-resilience, ecientmessage passing, and diverse functionality from a fixed structure [34].The structure of brain is represented by a network, with the nodes beingneurons or brain-regions, depending upon the usage, and the edges beingtheir communication channel or signal-interaction. Our brain is divided intovarious sub-regions that are organized and interconnected as communities.These brain regions are spatially separated, are functionally distinct andeach of them has a relationship of integrated functioning with all others.Studies have shown that brain networks typically have a small-worldtopology with similarities like dense local clustering or cliquishness, short102.7. fMRIpath lengths and relatively few long-range connections. The characteris-tic also explains for both segregated/specialized and distributed/integratedinformation processing of the brain. Moreover, brain networks have beenfound to be economical, tending to minimize wiring costs while supportinghigh dynamical complexity, similar to small-world networks [2].Due to the well arranged and orchestrated communication between thefunctional connectivity networks, all the complex cognitive processes of thehuman brain take place. Explanation about diâµerences in the functioning ofthe brains of patients with mental disorders is a topic with many approachesand we will be discussing one approach in our work of finding the function-ing of the brain-regions in these patients, then comparing it with controls(humans with healthy or normal functioning brains) and finally establish-ing some inter-group diâµerences. These diâµerences will be observed on thebasis of diâµerences that occur in the study of signals like fMRI and EEG ofpatients and controls.2.7 fMRIFunctional magnetic resonance imaging or functional MRI (fMRI) is a mea-sure of brain activity that detects changes associated with cerebral bloodflow based on which it measures activation of neurons. When a region ofthe brain is active or is getting used, there is an increased blood flow to thatregion. The primary form of fMRI uses the blood-oxygen-level dependent(BOLD) contrast, which is a type of specialized brain and body scan of hu-mans or other animals used to map neural activity by showing the changein blood flow related to energy use by brain cells. When there is a task tobe performed, the brain area(s) responsible for performing the task becomeactive, the blood flow in that active area increases, thus increasing the sup-ply of oxygen required for creating the energy required by the cells in thatarea for performing the task. This blood flow is then imaged to form fMRIimages [39]. fMRI data is represented in the form of 2D, 3D and 4D images.One of the types of fMRI imaging is a Resting state fMRI (r-fMRI) whichis used in brain mapping to evaluate interactions within brain regions thatoccur in a resting or task-negative state, a state when an explicit task isnot being performed. Because brain activity is intrinsic, i.e., it is presenteven when an externally prompted task is not performed, any brain regionwill have spontaneous changes in BOLD signal. The resting state fMRIapproach is mainly useful in exploring the brainâs functional organizationand in examining the alterations in this organization in case of neurological112.8. EEGor mental disorders.2.8 EEGElectroencephalography (EEG) is an electrophysiological monitoring methodthat is used for recording electrical activity of the brain, more precisely, formeasuring voltage fluctuations that arise within neurons from ionic currentused for message passing within brain. EEG records brainâs spontaneouselectrical activity over a period of time from multiple non-invasive elec-trodes, which are small metal discs with thin wires, that are placed on apersonâs scalp, and these signals are recorded in the form of wave patterns.The EEG values track brain wave patterns with respect to time and thereforeare a time series. EEG is a popular monitoring test for observing abnormalpatterns in patients that indicate seizures and other problems. It is oftenused to diagnose epilepsy, sleep disorders, depth of anesthesia, coma, etc.EEG is one of the oldest and still continues to be a valuable tool for researchand diagnosis that oâµers millisecond-range temporal resolution. Apart fromclinical uses, EEG is also very popular in the field of artificial intelligence invarious technologies like artificial brain and neo-humanity. In our work, wehave used EEG time series for gaining knowledge of brain functioning.12Chapter 3Signed Visibility GraphsIn this chapter, we will introduce the concept of signed visibility graphs,discuss the motivation and present methods for constructing them usingtime-series.3.1 Definition of Signed Visibility Graphs and itsmotivationOne of the ways in which signs have been introduced into graphs is throughsocial networks wherein, each person belonging to a society is a node. If twopeople are friends then their nodes in the network have a positive link andif two persons are foes then they are connected through a negative link. Agroup of people with only positive links between them, may form a socialgroup or a team. The signs of edges may have diâµerent meanings dependingon the purpose of the network. For team-formation, positive edges maydenote similar interests or complementing knowledge-areas whereas negativeedges may denote dissimilar interests or conflicting knowledge-areas.An important problem in the study of social networks is to understandthe tension between the two signs, which is termed as structural balance.There are many theories of structural balance, but we would focus on oneof them to define balance in our work in next chapter. Weak structuralbalance theory states that if a graph can be divided into groups such thatnodes within each group are friends, or positively tied, and nodes betweengroups are enemies, or with negative ties, then the graph is said to have aweak balance [11].Signed Visibility Graphs is a concept of the combination of signed net-works with visibility graphs. We add signs (or weights) to the edges betweentwo value points or nodes based on the visibility between them. If two nodescan âseeâ each other, they have an edge with positive sign or +1 weight.For adding the negative edges (or edges with -1 weight) we look for invertedvisibility, i.e., those nodes that are not visible to each other in the âgeneralâvisibility graphs but will have a visibility with each other when the graph is133.1. Definition and motivationFigure 3.1: An example of a signed visibility graph.inverted or made upside-down, will have a negative edge.We first create a visibility graph of a given time series using any of thevisibility algorithms - we call this graph the âgeneralâ graph - and assign a+1 weight or a positive sign to all the edges of visibility in this graph. Wethen invert the graph, or make it upside-down without removing the positiveedges - we will call this graph the âinvertedâ graph. Now all the nodes thatdid not have a visibility in the general graph, or donât have a positive edgebetween them, but can see each other in the inverted graph, will have anedge between them that will have a negative sign or a -1 weight.In Figure 3.1, we have a sample time series and have edges to denotea visibility graph. Green edges are for positive visibility and red edges arefor negative or inverted visibility. Almost all the possible edges have beendrawn in the figure.In this work, we have only worked with undirected graphs but this con-cept would work for directed graphs too in a similar fashion, the only diâµer-ence would be that the edges will have 2 attributes: sign and direction. Nowthat we have explained the abstract design of signed visibility graphs, we willsee how they are implemented using three types of visibility graphs: nat-ural visibility graphs, horizontal visibility graphs, and divide-and-conqueralgorithm.14Timey0 2 4 6 83.2. Algorithms for creating visibility graphs3.2 Algorithms for creating visibility graphsThe methods discussed in Chapter 2 have been modified to create signedvisibility graphs, and the algoritms are discussed below3.2.1 Basic AlgorithmThe algorithm is a natural way to create a visibility graph based on thedefinition and Equation (2.1) given in Chapter 2. Below is the descriptionof a customized method to create a signed visibility graph. Each node v 2 Vhas been initialized based on yv, sorted by tv.Algorithm 1 Natural Signed Visibility Graph1: Input: A time series y[0..(n 1)]2: Result: The visibility graph for given time series G(V,Ep, En)3: for each va 2 V do4: for each vb 2 V | tb > ta do5: // Adjacent data points are neighbours6: if tb = ta + 1 then7: Ep = Ep [ (va, vb);8: continue;9: end if10: visible true;11: visible2 true;12: for each vc 2 V | ta < tc < tb do13: value yb + (ya  yb) tb  tctb  ta ;14: if yc > value then15: visible false;16: else if yc < value then17: visible2 false;18: end if19: if visible = false and visible2 = false; then20: break;21: end if22: end for23: if visible2 true then24: if (va, vb) /2 Ep then153.2. Algorithms for creating visibility graphs25: En = En [ (va, vb);26: end if27: else if visible true then28: Ep = Ep [ (va, vb);29: end if30: end for31: end for32: Return G;(a)(b)Figure 3.2: (a) Original time series of the water levels of river Amazon. (b)Signed natural visibility graph obtained from the time series in (a).163.2. Algorithms for creating visibility graphsIn the above algorithm, the output is a visibility graph G with Ep as thepositive edges and En as the negative edges. Each node has a value y (ony-axis) and a time point t (on x-axis). For every pair of nodes we check fortheir visibility by checking the value of the nodes between them and generatea positive, negative or no edge accordingly. The python implementation ofthis algorithm is in the Appendix [Program A.1].The visibility graph [Figure 3.2b] has been generated with a time seriesof high and low water levels of the river Amazon at Iquitos for the years1962-1995 [21]. Positive edges are denoted by colour green and negativeedges are denoted by colour red. The original time series has been shownin Figure 3.2a. The worst case time complexity of this algorithm is O(n3),where n is the number of data or value points in the original time series.3.2.2 Horizontal Signed Visibility Graph AlgorithmIn this section, we will discuss the horizontal visibility graph algorithm,remodelled for creating signed visibility graphs. The algorithm mentionedbelow was referenced from the paper [48] that gave a faster version of con-structing a horizontal VG based on the same concept as original HVG [Equa-tion (2.2)], but with a few changes. The key concept of this âfastâ horizontalVG algorithm is that a maximal value point is always visible to its neighborsmaximal value point, even if the distance between those two maximal pointsis more than two nodes. All the maximal values belonging to the time seriesare stored in a sorting list SortList in the algorithm, which is empty whenthe index is zero. The explanation is more lucid in the algorithm below.Algorithm 2 Horizontal Signed Visibility Graph1: Input: A time series y[0..(n 1)]2: Result: A visibility graph for the given time series G(V,Ep, En)3: // Creation of positive visibility graph: LEVEL 14: SortList.add(y[0])5: for i = 1 to (n 1) do6: Ep = Ep [ (vy[i], vy[i1]);7: if y[i] > y[i 1] then8: Search Loc while SortList[0..Loc] < y[i]9: if Loc > 1 then10: for x = 0 to Loc do11: Ep = Ep [ (vy[i], vSortList[x]);12: Remove SortList[x] from SortList173.2. Algorithms for creating visibility graphs13: end for14: end if15: end if16: SortList.add(y[i])17: end for18: // Creation of negative visibility graph: LEVEL 219: max y max (y) + 1;20: for j = 0 to (n 1) do21: inv y[j] max y  y[j]22: end for23: inv SortList.add(inv y[0])24: for i = 1 to (n 1) do25: if inv y[i] > inv y[i 1] then26: Search Loc while inv SortList[0..Loc] < inv y[i]27: if Loc > 1 then28: for x = 0 to Loc do29: y val max y  inv y[i]30: sort val max y  inv SortList[x]31: if (vy val, vsort val) /2 Ep then32: En = En [ (vy val, vsort val);33: end if34: Remove inv SortList[x] from inv SortList35: end for36: end if37: end if38: inv SortList.add(inv y[i])39: end for40: Return G;In its Level-1, iteratively a maximal point is found and is positively con-nected to all the points in SortList lower in value than itself. All theselower values are then removed from SortList and the new maximal value isadded to the list. In Level-2, we create a new array inv y for storing the newvalue points after the old value points have been subtracted from max y andinv SortList acts as the sorting list for the inverted graph. Similar steps arerepeated for creating negative edges. Finally, the graph G is returned con-taining both positive and negative edges. The Python code implementationfor the algorithm is in Appendix [Program A.2] and below is the generatedgraph [Figure 3.3].183.2. Algorithms for creating visibility graphsFigure 3.3: The figure shows a signed horizontal visibility graph obtainedfrom the same âwater level of river Amazonâ time series.The worst case time complexity to generate a horizontal visibility graphusing Equation (2.2) is O(n3), where n is the number of nodes in the timeseries. But Algorithm 2 follows a faster approach, and as mentioned in [48],has a time complexity of O(n).NVG vs. HVGIt is evident from figures 3.2b and 3.3 that horizontal visibility graphs arejust subgraphs of natural visibility graphs. But there exist certain diâµer-ences that make these two unique. Degree distributions in a graph inheritcorrelations. Natural visibility graphs have more connections, more edgesand a higher degree distribution as compared to the horizontal visibilitygraphs and the former naturally allow for development of hubs, which turnout to be typically associated with extreme events in the data and can cor-relate with data at all scales. NVGs are in principle better suited to handleand extract long-range correlations whereas HVGs have been found to pos-sess exponentially decreasing degree distributions and hence they are goodto be used in processes involving short-range correlations. Horizontal vis-ibility algorithms geometric criterion is more visibility restrictive than thenatural VG, which implies that the nodes within horizontal visibility graph193.2. Algorithms for creating visibility graphsFigure 3.4: Signed visibility graph created by the Divide and Conquer algo-rithm obtained from the same âwater level of river Amazonâ time series.will have less visibility with other nodes as compared to the nodes in NVG.Despite the diâµerences, in both the cases, the n nodes (or time-points)are connected to each other by a trivial Hamiltonian path that originates anatural ordering in the degree sequence. Both the algorithms produce graphsthat are (i) connected, (ii) undirected, and (iii) invariant under ane trans-formations of the series. Both the algorithms originally have the same timecomplexities of O(n3), and their faster versions have similar complexitiesas well - O(n) for HVG and O(nlogn) for NVG (to be discussed in nextsection).3.2.3 Divide and Conquer AlgorithmIn this section, we will discuss a divide and conquer method, which has beenproposed in [27] for creating a visibility graph. As described in the previouschapter, the method first finds a maximum value node of the whole timeseries, connects it to all the nodes it can see and divides the time series intotwo parts: âleftâ and ârightâ. There is a recursive call on both the partsuntil the series cannot be divided anymore. The algorithm is described be-low and has been modified from its original version to best suit our work.203.2. Algorithms for creating visibility graphsAlgorithm 3 Divide and Conquer Algorithm1: Input: A time series y[0..(n 1)]2: Result: The visibility graph for given time series G(V,Ep, En)3: //For the first run left = 0 and right = (n 1)4: TimeSeries2VisibilityGraphFast(y, 0, (n 1))5: function TimeSeries2VisibilityGraphFast(y, left, right)6: if left < right then //There must be atleast two nodes in the time series7: k the index of maximum value of y[left . . . right ]8: TimeSeries2VisibilityGraphFast(y, left, k  1); // the left side of k9: TimeSeries2VisibilityGraphFast(y, k+1, right); // the right side of k10: for each i from left to right do11: visible true;12: visible2 true;13: if i < k then14: a i; b k15: else16: a k; b i17: end if18: for each vc 2 V | ta < tc < tb do19: value yb + (ya  yb) tb  tctb  ta ;20: if yc > value then21: visible false;22: else if yc < value then23: visible2 false;24: end if25: if visible = false and visible2 = false; then26: break;27: end if28: end for29: if visible2 true then30: if (va, vb) /2 Ep then31: En = En [ (va, vb);32: end if33: else if visible true then34: Ep = Ep [ (va, vb);35: end if36: end for37: end if38: End function213.2. Algorithms for creating visibility graphsIn the above algorithm, the function TimeSeries2VisibilityGraphFast isresponsible for generating the visibility graph by taking three parameters,the time series, the index of the leftmost value of the time series, i.e., 0, andthe index of the right most value of the time series, i.e., (n1). We assign theindex of the maximum value to variable k. Then from index left to right thevisibility of the node at k is checked with every other node in this window andsigned edges are drawn according to the criteria. At the end of the functionthere is a recursive call to the function for node kâs left and right handside parts with updated left and right index values. The implementationof this algorithm in Python [Program A.3] is in the Appendix. Figure 3.4below shows the graph created after the implementation. Notice how Figure3.2b and Figure 3.4 are structurally the same, the only diâµerence being thetime complexity to create them. It was observed empirically [27] that thisalgorithm has an average case time complexity of O(n log n).22Chapter 4Partitioning AlgorithmOur main work in this thesis is that of putting forth the idea of forming aclustering algorithm specially for time series (i.e. an algorithm that respectsthe time-feature of a series), using the technique of dynamic programming.As mentioned in Chapter 2, clustering (or partitioning or community detec-tion) is a process of identifying certain collections of objects/nodes/membersthat possess similar properties/characteristics/interests within their collec-tion and have dissimilarities with the objects belonging to other collections.In the case of signed visibility graphs, clustering can be done based on edgesign or weight, i.e. two nodes would belong to the same cluster if they havemore positive ties within the cluster as compared to their ties outside thecluster or if they have more negative ties with other nodes outside the clus-ter than the nodes within the cluster. In this chapter, we will first brieflydescribe time-respecting clustering, followed by dynamic programming andan explanation of our algorithm.4.1 Time-respecting ClusteringA partition of a visibility graph is time-respecting if all the nodes inside itare positioned in the network based on their time-points, and thereby thewhole cluster follows time-constraint imposed by the structure of visibilitygraph. Two partitions are non-overlapping if the intersection between themis null, i.e., they do not have any node common or shared between them.In this work, we have divided a visibility graph G in time-respecting non-overlapping clusters [P0, . . . , P(n1), Pn] in which [t0, . . . , t(n1), tn], or thesets of time-points of nodes belonging to respective clusters, is in the form ofconsecutive time-intervals. For the given definition, we will define a measureof the quality of a time-respecting partition in the next section.The basic scheme behind formation of clusters is that if within a set ofnodes, there are more number of positive edges than negative edges joiningthe nodes and if outside the set, there are more negative edges than positiveedges joining the set with other nodes, then the set forms a cluster. Theaim is to find a solution of non-overlapping clusters such that the number of234.2. Algorithm for Time-respecting Clusteringpositive edges inside and the number of negative edges outside any clusterare maximum values possible for the set of nodes that forms the cluster.Similarly, the number of positive edges outside and the number of negativeedges inside any cluster must be the minimum values possible for the nodesthat the cluster consists of.Similar to the description of inter and intra-cluster positive densities inChapter 2, we would now define a measure for finding the best-possible set ofclusters. Let us take a visibility graph G with clusters (P0, . . . , P(n1), Pn),then the overall quality, Q of the clusters can be calculated as,Q =Positive edges inside clusters(P0, . . . , P(n1), Pn)+Negative edges between clusters(P0, . . . , P(n1), Pn) Positive edges between clusters(P0, . . . , P(n1), Pn)Negative edges within clusters(P0, . . . , P(n1), Pn)And our aim would be to maximize this overall âqualityâ for creating mostecient clusters, following conditions similar to the ones mentioned in Chap-ter 2 for creation of a community.4.2 Algorithm for Time-respecting ClusteringThe main idea behind the algorithm is to exploit the scheme of signed edgesof a visibility graph to form clusters, by following dynamic programming.We will first briefly describe what dynamic programming is, followed by thealgorithm.4.2.1 Dynamic ProgrammingThe technique of Dynamic Programming has been used to solve numerouscomputing problems such as Weighted Interval Scheduling, 0-1 Knapsackproblem, Segmented least-squares, etc [24]. In dynamic programming, thespace of all possible solutions for a problem are explored by decomposingthe problem into a series of subproblems, and then the correct solutionsto larger and larger subproblems are gradually built up. Each of these sub-problems is solved once and their solutions are stored using a memory-baseddata structure (array, map, etc). This technique is used in both mathemat-ical optimization and computer programming. One of the main features ofDynamic Programming is maintaining an array for storing the results ofsubproblems, that can be iteratively computed, so that we do not have to244.2. Algorithm for Time-respecting Clusteringre-compute them later when the need be, which is mainly optimization overplain recursion. In our algorithm, as described in the next section, we usethe same concepts to build the clusters.4.2.2 The AlgorithmWe will first define a measure of quality of the partition in the form of arecursive optimal solution,For any node i (such that ti < tj),OPT [j] = max0ï£¿iï£¿j(q(i,j) +OPT [i 1]) (4.1)and the partition pi, ..., pj is used in an optimal solution for the subproblemif and only if the maximum is obtained using index i.OPT [j] is the maximum optimal quality value of time-respecting par-titions on the subgraph of the first j nodes, q(i,j) is the value of âqualityfactorâ (calculated later in this section) for the cluster (i, j) and OPT [i 1]is the optimal quality measure for clusters before node i, which is neededin this equation because the clusters in the subgraph of first i nodes wouldhave negative and positive edges with the cluster (i, j) which are neededto be considered. These facts form the first crucial component of forminga dynamic programming solution: a recurrence equation that produces theoptimal solution in terms of the optimal solutions to smaller subproblems.For every node j in the visibility graph, we take all the nodes to the leftof it one by one (say, i) and check if there can be a cluster formation withall the nodes between i and j (including these two nodes). The decision forcluster formation is made by checking for the cumulative edge signs withinthe cluster which is done by computing the quality, q(i,j). The equation is,quality = (pos in+ neg out) (neg in+ pos out) (4.2)Here, pos in, the number of positive edges between the nodes within thecluster,neg out, the number of negative edges between the nodes in the clusterand the nodes outside of the cluster,neg in, the number of negative edges between the nodes within the clus-ter,pos out, the number of positive edges between the nodes in the clusterand the nodes outside of the cluster.As per the discussion in previous section, our motto is to maximize(pos in + neg out), but for the quality measurement we need to minimize254.2. Algorithm for Time-respecting Clustering(neg in+ pos out) too and therefore we aim at maximizing Equation (4.2)that considers all the edges involved with a cluster. The higher the valueof quality measure of a cluster, the more favourable are the chances forthe formation of that cluster. If a cluster has negative quality value, itsformation would be very unlikely.For each pair (i, j) in the graph [ti < tj ], we calculate the quality, orq(i,j). If the value of q(i,j) is greater as compared with the quality values ofother nodes to the left of j, then we say that the node i gives us an optimalsolution for the node j. Hence, for the nodes explored so far in the visibilitygraph (till j), one cluster must be formed between i and j, until we explorethe graph more and find either i or j or both to belong to a cluster of anode with higher quality value.Following the two equations is not the only way to be followed in findingthe correct clusters - we need trace-backing, as done in dynamic program-ming, to actually form the clusters. Also, we maintain a globally accessiblearray that stores the values of optimal solutions of partitions that have beenformed, to be used to find optimal solutions for partitions yet to be formed.For creating the array, say M , we start with M [0] = 0, and iteratively com-pute the optimal solution for each node in V and store these solutions to usethem in all future recursive calls. For a node j, we use the value of optimalsolutions to subproblems on interval {1, 2, . . . , j} to define the value of M [j]using Equation (4.1). Below is the pseudo-code for the above explanation.Here, Find clusters is used to trace back through M eciently and returnthe list of partitions.Algorithm 4 Partitioning Algorithm1: Input: A signed visibility graph G(V,Ep, En)2: Result: List of clusters3: for all pairs i ï£¿ j such that i, j 2 V do4: Compute maximum âqualityâ q(i,j) for partition pi, ..., pj using Equa-tion (4.2)5: end for6: for j = 1, 2, ..., n do7: Use Equation (4.1) to compute M [j]8: end for9: Return M [n]10: //Trace-back264.3. Comparison with Louvain Algorithm11: Find clusters(j)12: if j = 0 then13: Output nothing14: else15: Find an i that maximizes q(i,j) +M [i 1]16: Output the partition pi, ...pj and the result of Find clusters(i 1)17: end ifAs an example, we ran the code with a sample data of the fMRI timeseries of a person (more details in Chapter 5) and got the results as shownin Figure 4.1. The Python code [Program A.4] for this implementation ismentioned in the Appendix. In Figure 4.1a the nodes with same colour-mapbelong to the same cluster and there are total 17 clusters generated by thealgorithm for a graph of 236 nodes [details in Fig. 4.1b].4.3 Comparison with Louvain AlgorithmIn this section we will see if the approach of signed visibility graph and par-titioning with our algorithm is more accurate as compared to a clusteringalgorithm, the Louvain Algorithm. We have compared our algorithm withLouvain algorithm because this algorithm was used in [41] for clustering invisibility graphs. We believe that any other standard community detectionmeasure would give the same results of comparison as given by Louvainbecause other community detection algorithms work only on the networkstructure, without considering any other information such as the time con-straint. We first give a brief description of the Louvain algorithm followedby the comparison.4.3.1 Louvain AlgorithmIn [4], the Louvain algorithm is used for community detection which is basedon greedy technique and works on weighted graphs. It has a high modularityand runs in O(n log n) time complexity. It has a number of iterations andin each iteration, it calculates the modularity gain (Q), where modularityis simply a measure of the density of edges inside of the communities com-pared to the edges between communities and has a value between -1 and 1.The gain is the change in modularity when a node is removed from its owncommunity and moved to the community of each of its neighbors. The algo-rithm mainly runs in two phases: in first level, all the vertices of the graph274.3. Comparison with Louvain Algorithm(a)(b)Figure 4.1: (a) An example visibility graph showing diâµerent clustersformed. The time series of this graph is Figure 4.2. (b) The output ofdetails of clusters and number of clusters for the above example.are put into separate communities, so the total communities are equal to thenumber of nodes. Then the Q is calculated for each node and the node ismoved into the community of a neighbour that has highest Q value. Thislast step is looped until no further gains can be achieved in the system. Inthe second phase, partitions done in first phase are termed âsuper-verticesâand if there was at least one edge between the nodes of the correspondingpartitions, then their super-vertices are connected, and the weights of all theedges between the nodes belonging to the 2 partitions are summed to denotethe edge weight of a single edge between the corresponding super-vertices.These two phases are repeated until the system reaches stability.Since the system may reach a diâµerent level of stability each time, this284.3. Comparison with Louvain AlgorithmFigure 4.2: The figure shows a sample fMRI time series with 236 time values.algorithm may give diâµerent clusters in each run and therefore it is ranmultiple times and an average clusters information from all these runs istaken into account.4.3.2 Methods and Results of ComparisonTo compare the performance and eâµectiveness of our algorithm with Lou-vain, we processed and extracted 1300 time-series from a fMRI dataset (moredetails in Chapter 5). A sample time series from the dataset is shown inFigure 4.2. For testing the Louvain algorithm, we used unsigned visibilitygraphs because Louvain algorithm works with positively-weighted graphsand since negative edges in signed visibility graph have negative weights,the algorithm doesnât take those edges into account. For each graph, Lou-vain was ran 50 times and all the observations are the average of 50 runs.Figure 4.3 shows the results of the comparison. The first point of no-ticeable diâµerence was of the range of number-of-clusters values given byboth the algorithms. While our algorithm gives a bigger range of number ofclusters (lowest value being 2 and highest being 28), the Louvain algorithmdoesnât show much extreme variation in this number (lowest being 5 andhighest being 12).After a detailed examination of the clusters formed by Louvain, we havethe following observations, in comparison with our method:294.3. Comparison with Louvain AlgorithmFigure 4.3: The figure shows 2 line-plots for both the algorithms, blue lineindicating the number of clusters for our algorithm and red line indicatingnumber of clusters for Louvain algorithm.â¢ Louvain algorithm does not respect the time-restraint as imposed bytime-series and the structure of visibility graphs. For proving this, wehave a look at Figure 4.4 which shows two examples of how clusteringis done in Louvain algorithm. Figure 4.4a is a visibility graph of one ofthe samples taken from the dataset used for comparison, that showsclusters indicated by diâµerent colors. In this figure, the nodes areplaced according to their time points, i.e., they follow time-restrainedpositioning. When we observe the cluster indicated by color pink, wenotice that it is discontinuous and is divided into three parts over thegraph (the nodes of discontinuous clusters have been slightly enlargedfor better visual observation).A similar observation can be made in Figure 4.4c with the cluster incolor pink, which is disintegrated in two parts in the visibility graph.Another discontinuous cluster is indicated by the color orange whosenodes a and b have a cluster (blue colored) between them. If the nodesin a visibility graph follow a time-order in their positioning, then theirclusters are expected to be continuous (or whole or unbroken) andunder the time-positioning restriction, but it is not followed in theLouvain algorithm. Figures 4.4b and 4.4d show the general networkview of the graphs in figures 4.4a and 4.4c respectively. In these net-works, nodes are not positioned according to their time-points but30Number of clustersIndex4.3. Comparison with Louvain Algorithm(a)(b)(c)(d)Figure 4.4: Two examples of clustering by Louvain algorithm: (a) and (c)show clustering in the visibility graph structure; (b) and (d) show the re-spective generic network views of graphs (a) and (c), without time-constraintpositioning.have been placed according to their connections. The Louvain algo-rithm basically clusters the nodes according to this structure.â¢ The Louvain Algorithm forms weak clusters. After observations of thequantity and integrity of the clusters formed by Louvain algorithm, weobserved a weakness in the quality of the clusters too. The fundamen-tal property of a cluster is that the nodes or elements within a clustershould be highly connected to each other, or must have more numberof connections within the cluster than outside the cluster. A cluster314.3. Comparison with Louvain AlgorithmFigure 4.5: Formation of weak clusters by Louvain Algorithm.that doesnât follow this property is not a strong cluster. Figure 4.5shows a zoomed-in image of the graph in Figure 4.4a. In this graph,we first observe the cluster X (or, cluster (a, c)) containing nodes a, band c. For it to be a strong cluster, the nodes between (a, b) must havehigh number of connections with the nodes between (b, c) but the onlynode from (a, b) connected with the nodes in (b, c) is the node b itself.This doesnât indicate a good cluster and therefore (a, b) and (b, c) mustform two separate clusters (which happens in our algorithm). Anotherexample of a weak cluster is the Cluster Y wherein no nodes in (d, e)except the node e are connected with the nodes in (e, f), thereforemaking (d, f) a weak cluster.The above two observations show that Louvain or any other communitydetection algorithm, that dont take into consideration the time constraint,are not the best options for clustering of VGs. They also explain the reasonwhy Louvain algorithm has such a low modularity, with an average numberof clusters 9.1 for the dataset taken. Such low modularity is not a goodmeasure for time series that have so many highs and lows in their values.Clustering in Louvain algorithm is only based on the weights of the edges,which isnât a very useful factor to consider while partitioning nodes in a324.4. Importance of Signed Edges and Time-respecting Constrainttime-series. Whereas our algorithm strictly follows the time-order of theseries and therefore the clusters are formed with a time-respecting factor inconsideration, in-sync with the structure of the visibility graph, and not justbased on connections.We can thus see that our algorithm is more eâµective in clustering vis-ibility graphs where vertices have an implicitly-defined order as comparedwith Louvain algorithm because our method takes care of the sole featureof the time-series while clustering, the time. Another good feature of thisalgorithm is that it can deal with dynamic data while forming clusters, i.e.,we can use a visibility graph in which the nodes keep adding dynamicallyand still create accurate clusters using our algorithm as it takes one nodeat a time for making decisions on the formation of a cluster involving thatnode. Everytime we need to form and see updated clusters after addition ofone or few new nodes to the graph, we just need to run the trace-backingcode and the clusters would be generated.4.4 Importance of Signed Edges andTime-respecting ConstraintWe will discuss why the concept of signed edges in visibility graphs andour partitioning algorithm give correct results of clusters, and also how theidea of dynamic programming solves such problems correctly. Let us lookat Figure 4.6, which shows 4 of the many possible cases involved in theformation of clusters and analyze these one by one. In all figures, we haveindicated edges by green and red colors to show positive and negative edgesrespectively and the figures are just a part of a bigger graph, used to showhow backtracking aâµects the accuracy. All the edges shown are only toindicate the shape of the sub-graph shown and not all connections betweennodes have been drawn.We first have a look at Figure 4.6a, where we consider j to be the lastnode of this part of the graph. Now, we consider a node j0 that has itshighest quality value with node i (i.e. startj0 = i) then accordingly weshould have a cluster (i, j0). But by observation, this cluster is a wrongformation because the number of positive edges outside the cluster are high.The value of quality for (i, j0+1) would be higher than that for (i, j0) simplybecause the number of positive edges are more in the former and there areno negative edges in either. Now for node j, startj would be i as the cluster(i, j) has only positive edges inside of it and the value of quality with nodei is very high. Now when we trace-back, node j is picked first, forming334.4. Importance of Signed Edges and Time-respecting Constraint(a) (b)(c) (d)Figure 4.6: In this figure we see 4 of many possible cases found in theformation of clustersthe cluster (i, j). If trace-backing wasnât considered, then node j wouldprobably form a cluster with node j0 + 1 as node i would be unavailable toit, because of the formation of cluster (i, j0). When we sum the values ofquality for the two clusters (i, j0) and (j0+1, j), we would find it to be quitelow as compared to the value for cluster (i, j) because of all the positiveedges outside of the cluster that are getting added up in the denominator ofEquation (3.1), decreasing the respective values. Therefore in this case thealgorithm gives us the best possible cluster (i, j) which is a stable choice forj0, j0 + 1 and all other nodes within (i, j).Now we consider Figure 4.6b and see that in this case startj 6= i becauseof a lot of negative edges between them and therefore we would probablyget a cluster (j00, j), if j has the most positive edges or least negative edgesin (j00, j).We now consider the figures with a little bend in the concave or convexshape of the subgraph so that the subgraph has some negative edges insidethe cluster. In Figure 4.6c, considering the node j0 again, startj0 = i but thevalue of quality for (i, j0+1) would be less as compared to quality for (i, j0)because of the negative edges within the cluster. We would again have two344.4. Importance of Signed Edges and Time-respecting Constraintclusters (i, j0) and (j0 + 1, j) but the cumulative value of these two clustersâquality would still be lower than the quality value of the cluster (i, j) becauseeven if there are some negative edges in (i, j), and none in the clusters (i, j0)and (j0 + 1, j), they are outnumbered by the high number of positive edgesthat this cluster has, still giving us a very high quality value and thereforethe algorithm gives us the cluster (i, j). The domination of positive edgesin a cluster with one or more such âbendsâ (that introduce negative edgeswithin the cluster) is because visibility of the nodes that form that bendincreases thereby increasing positive edges within the cluster and giving ahigher value of Equation (4.2). The number of negative edges increasestoo because of the bends but the positive visibility is comparatively higherbecause of the presence of nodes that are taller (higher y value) than thebend(s)âs height(s). This case would be true until the bend height becomesequal to or more than the height of the tallest node in the cluster, i.e., untiland unless y0j  yj , the best cluster formed would be (i, j). If y0j  yj thenthe clusters formed by the algorithm are (i, j0) and (j0 + 1, j).In Figure 4.6d (i, j) would form the worst cluster because of a lot ofnegative edges even if there are some positive edges introduced because ofthe bump. In this case, j may form a cluster with some other node j00, j0and j0+1 would be a part of the same cluster (the small cluster covering thewhole bend) and i would be a part of some other cluster of more positiveedges than negative edges within. Any other cases of cluster formation ingraphs and subgraphs would revolve around these 4 cases.35Chapter 5Multivariate CorrelationIn this chapter we will have a look at one of the applications of signedvisibility graphs, correlation in multivariate visibility graphs.5.1 Multivariate Time SeriesAll the time series examples we have covered in this thesis till now areunivariate time series. A graph involving these only takes two parameters:time as an independent variable, and a single dependent variable. On theother hand, a multivariate time series is composed of more than one time-dependent variables. In a multivariate time series, each observation at atime t is considered to be a vector of values instead of a single value, sinceat each t there are more than one variable under observation. Typically forthese series, there is a close interrelation between the variables in the vector,and this is the reason why they are considered to be a single observation invector form instead of distinct observations from separate time series. Thesevariables could be of diâµerent types and units (for example, the weatherconditions involving pressure, temperature, etc.) or could be of the sametype with diâµerent values at a each time-point (we would see an example ofthis type later).Mathematically, considerM time series variables s1t, ..., sMt, then a mul-tivariate time series involving these variables would be a (M â¥ 1) vector Stwhere its ith row is sit.As far as mapping of time series goes, univariate time series are mappedto a single visibility graph and a multivariate time series is mapped to amultilayer visibility graph M with M layers, where M is the number ofvariables in the multivariate time series. A layer âµ of the multiplex graphM corresponds to the NVG associated with time series of state variable[x[âµ](t)]Nt=1. For every node i in the graph, there is a natural correlation orconsistency across layers of various univariate time series, so the resultingvisibility graph is called a Multiplex Graph. This multiplex visibility graphencodes the complex structure of each time series in the topology of eachlayer. Figure 5.1 shows an example of a multivariate time series withM = 3365.2. Interlayer Mutual InformationFigure 5.1: Example of the construction of a multiplex visibility graph from amultivariate time series withM = 3 components. Reprinted with permissionof [25].variables, which is transformed into a multiplex graph of M = 3 layers(figure taken from [25, 32]).A multivariate series consists of properties of not only the individualseries it is made of, but also cross-relations among those series. Theseindividual series are analyzed jointly in order to understand the dynamicrelationships shared among them over time and also for the purpose of im-provement of accuracy of these individual seriesâ forecasts by making use ofthe additional information available from the joint interdependencies [38].For extracting these complex interdependencies and correlations that mightemerge in the series across variables, certain similarity measures are usedacross layers.5.2 Interlayer Mutual InformationOne of the measures for extracting correlations between layers of a multiplexVG is the Interlayer Mutual Information that characterizes and measuresthe information shared by every two layers based on the similarity of thedegree distributions [25, 32]. Since the degree distribution of any graph isthe most basic metric for capturing the structure of each graph, the measureof mutual information captures the information shared between two layers,which is the information shared across each time series component of themultivariate time series. We would now define the measure of correlation,which has been mentioned in [25] for unsigned multiplex visibility graphs asinter-layer mutual information Ii,j for a given pair of layers i and j of the375.2. Interlayer Mutual Informationgraph M,Ii,j =XkiXkjP (ki, kj) logP (ki, kj)P (ki)P (kj). (5.1)Here, P (ki) and P (kj) are the degree distributions at layers i and jrespectively, P (ki, kj) is the joint probability to find a node with degree kiand kj at layers i and j respectively.Note that the formula in the above equation doesnât consider negativeedges. Since in our work we are working with signed visibility graphs, weadapted the measure in Equation (5.1) to include the degree distributionsof the nodes by negative edges, defined as,Ii,j =XpkiXpkjXnkiXnkjP â¤i,j logP â¤i,jP (pki)P (pkj)P (nki)P (nkj). (5.2)where, P â¤i,j is the term,P â¤i,j = P (pki, pkj , nki, nkj)Here, Ii,j is the inter-layer mutual information or the inter-layer corre-lation measure for signed multiplex VGs,pki, pkj are the positive degrees (or degrees by positive links) of a nodeat layers i and j respectively,nki, nkj are the negative degrees (or degrees by negative links) of a nodeat layers i and j respectively,P (pki), P (pkj) are the positive degree distributions at layers i and jrespectively (or the probability to find a node having degree pki at layer iand degree pkj at layer j respectively),P (nki), P (nkj) are the negative degree distributions at layers i and jrespectively,P â¤i,j or P (pki, pkj , nki, nkj) is the joint probability to find a node havingdegrees pki and nki at layer i and degrees pkj and nkj at layer j respectively.In general, two layers in M will have more correlated degree distribu-tions, if they have higher value of Ii,j and, therefore, the two associated timeseries will have more correlated structures. We implemented the Equations(5.1) and (5.2) on the same dataset we used for the implementation of ourclustering algorithm, and came up with the results in Figure 5.2. We tooka part of the dataset for evaluation with 122 time series, therefore makinga multiplex graph with M = 122. Each value in the plots is the mutual385.2. Interlayer Mutual InformationFigure 5.2: Results of implementation of the two equations: first scatter plotindicates Equation (5.1) and second scatter plot indicates Equation (5.2).information measure between a pair of visibility graphs (layers) from themultiplex graph, and the values from all the visibility graph pairs have beenplotted. These visibility graphs were of time series taken from Regions ofInterest (ROIs) of human brain (more discussion in next chapter).395.2. Interlayer Mutual InformationTable 5.1: Comparative results of multivariate correlation equations.Factors Equation 5.1 Equation 5.2Degree Distributions 2 4(per pair of layers or per I-value)Pâ¤avg 0.00861 0.00429Davg 0.00637 8.871â¥105Number of iterations 504 238.8k(per pair of layers or per I-value)Range of values 0.55 - 1.27 6.1 - 7.68Variance 0.010284 0.073642avg 0.089 0.195In Figure 5.2 we notice the variation in values by both the equations.While Equation (5.1) gives us values within a range of 0.75 (maximum: 1.25,minimum: 0.5), Equation (5.2) gives a broader range of 1.7 (maximum:7.7, minimum: 6). Equation (5.2) gives more varied and diverse values forexactly the same time points for which Equation (5.1) doesnât show muchvariation. We carried out a break-down analysis of the equations, computingvalues of their components and noted the results in Table 5.1 for in-depthexamination of the values obtained in the figure. These numerical results inthe table are specifically for the dataset used, except for the first row of thetable.In Table 5.1, P â¤avg is the average of joint probability value (or the nu-merator in the log function) and Davg is the average value of the productsof degree distributions (or the denominator in log function), taken for eachiteration and averaged for both the equations. avg is the average of dif-ference between two I-values. The average of total number of summations(or the total number of iterations) for calculating I-value between each pairof adjacent layers is also noted. Notice that due to the consideration ofpositive and negative edges, Equation (5.2) has total 4 degree distributionparameters per pair of layers, whereas Equation (5.1) has 2 due to only thepositive edges.From Table 5.1 we have the following observations:â¢ The P â¤avg is quite low (almost half) for Equation (5.2) as comparedto (5.1), which means the joint probability that satisfies the degreesat a particular iteration is lower for the modified Equation. Equation(5.2) has 4 degrees in one run and it becomes rarer to find a node405.2. Interlayer Mutual Informationthat satisfies all the four degrees requirements, thereby decreasing thevalue of joint probability.â¢ The Davg is comparatively quite high for Equation (5.1) (102 times)than (5.2). Although the degree distributions due to positive edgeswill be the same for both the equations, the point of diâµerence isintroduced by low values of the degree distributions due to negativeedges (degrees due to negative edges are lower in value than positiveedges, giving low degree distributions).â¢ There is a huge diâµerence in the number of iterations or number oftimes the calculated values are summed to get one I-value. This re-sult is supported by the fact that there are 4 nested loops due to 4degree summations in Equation (5.2) as compared to 2 nested loopsin Equation (5.1).â¢ Equation (5.1) has a shorter range of values with smaller values as com-pared to (5.2). Although the P â¤avg diâµerence between the two equationsis 0.00432, the major diâµerence in the values is due to extremely lowdenominator of the log function (Davg) in Equation (5.2), that gives alarger log function value. Along with this, Equation (5.2) undergoes474 times more summations for each I-value, thereby giving us theseresults.â¢ Higher Variance (about 7 times) and higher avg (almost double) val-ues of Equation (5.2), along with the visual picture in Fig. 5.2 give usan idea of how spread out the I-values are, due to the considerationof negative edges.We ran an F-test to compare the two variances given by the two equa-tions, getting F-value of 7.16 and p-value < 2.2e-16 for 95 percent confidenceinterval. For the same pair of visibility graphs, the magnitude of informa-tion about correlation given by (5.2) is higher as it has more diverse valuescompared with values given by (5.1) that are not very divergent.To make it clearer, letâs take 4 sample time-series, as shown in Figure 5.3.For the comparison, I-values were calculated between time-series1 and eachof the other three time series, using both the equations and the values arenoted in Table 5.2. We can see that for the 3 same pairs of visibility graphs,Equation (5.1) gave almost similar values: 0.720, 0.719 and 0.721, whereasEquation (5.2) have much more varied values: 6.520, 6.444 and 6.243, re-spectively. The time-series 2, 3 and 4 are very diâµerent from each otherin structure [Fig.5.3] but still, when correlated with time-series1, Equation415.2. Interlayer Mutual InformationFigure 5.3: 4 sample time series used for calculating I-values using both theMI equations.(5.1) gave very similar values for them. Equation 5.2 was able to give usa better idea about the amount of correlation between these time-series asit gave dissimilar values. Using Equation (5.1), we have to observe valuestill hundredth or even thousandth place of decimal to find any significantdiâµerence in the I value, whereas values given by Equation (5.2) only needto be observed till tenth decimal place to see significant diâµerences.As compared to time series 4, time series 1 is structurally more similar totime series 2. The values of I given by Equation (5.1) for mutual informationof time series 1 with time series 2 and 4 respectively are extremely similar,suggesting similar structures, which is not the case. Equation (5.2) on theother hand, gives us a higher I-value between time series 1 and 2, and alower I-value between time series 1 and 4, indicating the correct degree oftheir structural similarities.It is evident that for the same pair of graphs, Equation (5.2) gives valueswith finer or more detailed information about the amount of correlationpresent between the graphs. This measure provides more help in detectingmore subtle correlation structures. This diâµerence supports the fact thatconsidering both positive and negative edges is more informative in terms ofthe level of correlation than considering only the positive edges. The added42Time series 1Time series 3Time series 2Time series 4TimeTimeTimeTimeValueValueValueValue0 50 100 150 200 0 50 100 150 2000 50 100 150 200 0 50 100 150 200-2.0 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5-2.0 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5-2.0 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5-2.0 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.55.2. Interlayer Mutual InformationTable 5.2: Comparison between values given by both equations for the samepairs of visibility graphs.MI calculated between Equation 5.1 Equation 5.2Time-series1 - time-series2 0.7204 6.5206Time-series1 - time-series3 0.7199 6.4442Time-series1 - time-series4 0.7218 6.2433structure feature, the negative edges, have helped in getting better insightinto the structure correlation between two visibility graphs.43Chapter 6Application to BrainNetwork AnalysisIn this chapter, we have applied our framework to study brain networksrepresented in the form of brain images (fMRI) and electric signals (EEG)which are used for detection, diagnosis and study of neurological diseasesand functioning of the brain. In this study, we will use the data generatedby these techniques to find alterations or diâµerences in brain-functioning ofpatients with diâµerent mental disorders, by using the concepts of networkingand graphs.6.1 TerminologiesBefore we go further with the description of the fMRI data, there are severalimportant concepts that need to be put under light.6.1.1 Data and Preprocessing Techniquesâ¢ Parcellations: Defining brain structures of interest is an importantpreliminary step in brain-connectivity analysis. Brain Parcellationsor Atlas are templates that divide the brainâs spatial domain intoa set of non-overlapping regions (ROIs) or modules based on func-tional homogeneity. In a parcellation, the image voxels are groupedinto structurally or functionally homogeneous regions, each of which isrepresented by a node in the corresponding network and connectivityis defined among all voxels in a pair of regions [44].â¢ ROIs (Regions of Interest of Brain): Region of Interest (ROI) analysisin neuroimaging refers to selecting a cluster of voxels or brain regionwhen investigating a region for eâµects. In most simple words, an ROIis simply a part of the brain (or a subnetwork) used for study of specificareas in brain having specific functionality.446.1. TerminologiesFigure 6.1: A 7-network Yeoâs parcellation of the human cerebral cortexbased on 1,000 subjects, reprinted with permission of [46].â¢ RSNs (Resting State Networks): These are brain areas that consistof many ROIs, divided based on functional similarity. According toYeoâs networks, the brain is divided into left and right hemispheres,which are further divided into 7 non-overlapping functionally homoge-neous sub-regions or RSNs namely Visual, Somatomotor, Dorsal At-tention, Ventral Attention, Limbic, Frontoparietal control and Default,as shown in Figure 6.1 taken from [46].â¢ Data Preprocessing: Before the raw functional data can be put touse, a series of operations is typically performed on it, in order to re-duce artifact and noise-related signal components. Some of these oper-ations include slice timing correction, motion correction/realignment,normalization, interpolation, and smoothing, etc. along with some im-age preprocessing operations such as noise reduction, bias correction,brain extraction, and segmentation. Preprocessing is also responsiblefor standardizing the location of brain regions across diâµerent subjectsto achieve validity and sensitivity in group analysis. There are variouspipeline softwares available for this purpose like NIAK (NeuroImag-ing Analysis Kit) and fMRIPrep. NIAK is an open-source library ofpipelines for the preprocessing and mining of connectomes extractedfrom large fMRI data, that performs all the previously mentionedpreprocessing operations along with data-driven functional brain par-cellation. Similarly, fMRIPrep automatically adapts a best-in-breed456.1. Terminologiesworkflow to the distinct datasets, ensuring high-quality preprocessingwithout manual intervention [13].â¢ BIDS (Brain Imaging Data Structure): It is a data organization for-mat especially for neuroimaging experiment data and is designed tofacilitate its transfer, description, and storage. BIDS provides a disci-plined way to arrange the diâµerent data types, is intuitive and easy toadopt. The specification is based on simple folder structures and fileformats to reflect current lab practices and make it widely accessibleto scientists coming from diâµerent backgrounds [19].â¢ MNI-152 (Montreal Neurological Institute-152 ): For the purpose ofanalysis of fMRI data, registration of the data to a reference braintemplate is required in order to identify the activated brain regions. Abrain template is an anatomical representation of the brain depictingfiner anatomical details. The MNI-152 brain template was constructedby averaging 3D brain MRI images of 152 normal subjects. The ad-vantage of MNI-152 brain template is that it provides a full headcoverage, covering the top portion of the brain to the bottom portionof the cerebellum [29].â¢ NIfTI-1 (Neuroimaging Informatics Technology Initiative): It is avery popular file format for storing the fMRI imaging data, whichconsists of a header file .hdr, to store meta-information, and the actualdata file, with extension .img, the two files usually stored as a combinedsingle file, with extension .nii. It also consists of an accompanying filedescribing the orientation in space, usually in .mat format. In the niftiformat, the first three dimensions define the three spatial dimensions- x, y and z -, while the fourth dimension defines the time points - t.â¢ Jaccard Index: The Jaccard index, also known as Intersection overUnion, is a statistical measure or comparison metric of similarity anddiversity in two sample sets, to see which elements of the sets areshared and which are distinct. Higher the Jaccard index value betweentwo sets, more similar they are. Mathematically, it is the size of theintersection divided by the size of the union of the sample sets:J(A,B) =|A B||A [B|â¢ Extracranial and intracranial EEG: As mentioned in Chapter 2,EEG is a monitoring method used in recording electrical activity of466.1. Terminologiesthe brain. It is usually recorded by placing the device electrodes onthe personâs scalp with a conductive gel, and this type of recordingis called extracranial recording. The number of electrodes generallydepends on the device can range from 2 to 256. When the requiredEEG recordings cannot be taken from the surface of the scalp (or,outside the skull), electrocorticography or intracranial EEG is used.In this, electrodes are placed directly on the exposed surface of thebrain (or, inside the skull) for recording from the cerebral cortex.6.1.2 Neurological Disordersâ¢ ADHD (Attention Deficit/Hyperactivity Disorder): ADHD is the mostcommonly diagnosed mental disorder, found in both adults and chil-dren. Children with ADHD may be hyperactive and unable controltheir impulses, or they may have trouble paying attention. Adultswith ADHD may have trouble managing time, being organized, set-ting goals, and holding down a job.â¢ Bipolar Disorder: Bipolar disorder is a brain disorder that causesunusual shifts in mood, energy, activity levels, and the ability to carryout day-to-day tasks. A person with this disorder can either be de-pressed and may feel sad or hopeless and lose interest or pleasure inmost activities, or can suâµer from mania (or hypomania) in which theymay feel euphoric, full of energy or unusually irritable.â¢ Schizophrenia: Schizophrenia is a chronic and severe mental disorderthat interferes with a personâs ability to think clearly, make decisions,manage emotions, and relate to others, along with impairing a personâsability to function to their potential. Unfortunately, no single, simplecourse of schizophrenia treatment exists.â¢ Epilepsy: It is a chronic neurological disorder in which the personhas recurrent, unprovoked seizures, or a brief disruption in normalactivity of brain, interfering with brain function. It involves a loss ofconsciousness and rhythmic jerking movements. It could be causeddue to a brain injury or genetic factors.476.2. Analysis of fMRI Data6.2 Analysis of fMRI Data6.2.1 fMRI dataFor fMRI implementations, we took the data of resting state fMRI of pa-tients. The data was retrieved from 2 online repositories. The first datasetwas taken from NeuroImaging Tools and Resources Collaboratoryâs (NI-TRC) initiative ADHD200, which is a part of its 1000 Functional Connec-tome Project and is described in [9]. This initiative was started for un-derstanding of the neural basis of ADHD through open data-sharing anddiscovery-based science, and is the source of unrestricted publically releasedresting state fMRI data of typically developing individuals with ADHD(ages: 7-21 years) [8]. For this study, the data contributed by Peking Uni-versity and Beijing University was used. The preprocessed data of thesesamples was taken from the repository made available by the Neuro Bureauat [33]. Out of the available options of preprocessing strategies, we usedthe data from the NIAK on CBRAIN, as this technique preprocesses restingstate fMRI data and extracts the time courses, which is our basic require-ment. The data taken was âBeijing 1000 ROI extracted time coursesâ whichis organized in the form of 954 ROIs for each patient, and each ROI has itsown time series.In the data, the term ADHD Index was defined to be a combinationof the measures of âAttentivenessâ and âHyper/Impulsivenessâ and eachpatient was given a score for these measures, maximum values being 36and 30 respectively. Out of the 259 patients, we chose 10 patients whohave the highest ADHD Index value (or the highest âinattentivenessâ andâimpulsivenessâ values) and 10 patients that have the lowest ADHD Indexvalues. All the selected patients have almost similar values for Verbal IQ(range 75-149) and Performance IQ (range 80-135) with an age range of 9-15years.The second dataset was taken from a large online repository openfMRIwith accession number ds000030. This dataset has been contributed by theUniversity of California, Los Angeles for their Consortium for Neuropsychi-atric Phenomics (CNP) LA5c Study, as described in [37] and available at[35]. The dataset includes an extensive set of task-based fMRI assessments,resting fMRI, structural MRI, and other imaging data of 138 healthy sub-jects, as well as samples of individuals diagnosed with schizophrenia (58),bipolar disorder (49), and ADHD (45). For both healthy and patient groups,participants were of ages 21-50 years and the data is formatted according tothe BIDS standard. The preprocessed rs-fMRI data, as described in [18] was486.2. Analysis of fMRI DataFigure 6.2: Comparison between the average number of clusters found inthe patients with high (blue) and low (orange) ADHD index. Each point inthe plot denotes a patientâs value, and each value is the average of numberof clusters formed by 15 randomly chosen ROIs.taken from [36] in the form of NIfTI-1 image files, which was preprocessedusing fMRIprep pipeline with the MNI152 template. For our study, data of10 healthy subjects as well as 10 subjects each from the 3 patients sets wastaken, all subjects randomly chosen.6.2.2 ResultsROI levelFor the most basic ROI level, the data was taken from ADHD200 prepro-cessed databaseâs 1000 ROI time-course for 20 patients, as described before.First to check if any relevant diâµerences exist between the high ADHD-indexpatients and low ADHD-index patients pertaining to our algorithm, we ran-domly chose 15 ROIs out of 954, and formed clusters using the visibilitygraphs of their time-series. We then averaged the total number of clustersin these ROIs for each patient.In Figure 6.2, we plotted the average number of clusters for each patientbelonging to the set of high ADHD-index (set-1, blue plot) and lower ADHD-index (set-2, orange plot), along with regression lines and LOWESS (LocallyWeighted Scatterplot Smoothing) lines. The patients were indexed based onthe values of ADHD-index - descending values for high ADHD patient set49Index of patientsAverage no. of clusters6.2. Analysis of fMRI Dataand ascending values for low ADHD patient set. In the figure, relevantdiâµerences were noted in the average values of these patients. The averageof these values is 15.33 for set-1 and 14.44 for set-2. Overall, the averagenumber of clusters for patients with low ADHD are lower as compared topatients with high ADHD index. Welchâs t-test was applied for equal sampleFigure 6.3: Comparison between the average number of clusters found in thepatients with high (green) and low (pink) ADHD index for the 7 RSNs. Eachpoint in the plot denotes a patientâs value, and each value is the average ofnumber of clusters formed by all the ROIs in the respective RSN.50Index of patientsIndex of patientsIndex of patientsIndex of patientsIndex of patients Index of patients Index of patientsAverage no. of clustersAverage no. of clustersAverage no. of clustersAverage no. of clustersAverage no. of clustersAverage no. of clustersAverage no. of clusters0 2 4 6 80 2 4 6 8 0 2 4 6 8 0 2 4 6 80 2 4 6 8 0 2 4 6 80 2 4 6 813.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.0High ADHDLow ADHDHigh ADHD High ADHDHigh ADHDHigh ADHD High ADHDHigh ADHDLow ADHDLow ADHDLow ADHDLow ADHD Low ADHDLow ADHD6.2. Analysis of fMRI Datasizes, unequal variances with a 95% confidence interval (âµ = 0.05) and theresulting t-value was 2.5177 with the p-value of 0.02436.Groups of ROIs levelIn the same dataset, ROIs were grouped together to form sub-networks orRSNs based on Yeoâs parcellation networks [46] with ROIs that are func-tionally similar belonging to the same RSN. For grouping, we chose the 7networks approach with 1000 parcels. Here, the parcels are actually ROIsand they were divided into 7 RSNs by the method of matching as done in[42]. We matched our ROIs with the parcels of Yeoâs networks by matchingthe ROI number with the parcel number and assigned the network that theparcel is a part of, to the ROI, i.e., the RSN of each ROI was assigned basedon its spatial overlap with the original 7-network parcellations. With themethod of matching, we could group all the ROIs and got 7 groups with aliasCont, Dors, Limbic, Sal, Som, Vis and Default to carry out the evaluations.For each patient, we had 954 time series (one for each ROI) divided into7 RSNs. We considered 18 patients, 9 per set, and used 18â¥954 visibilitygraphs to generate the following results. Figure 6.3 shows the plots of av-erage number of clusters for each RSN, along with regression lines. In eachplot, one point denotes one patient, coloured according to the set it belongsto, and the plotted value is the average of the number of clusters formed byall the ROIs belonging to that RSN. The patients were indexed based ontheir ADHD-index values.In RSNs Vis, Limbic, Dors, Sal, and Som, high ADHD patients showedhigher average values, whereas in Default and Cont, the patient-sets did notshow much diâµerence. We now know which RSNs are majorly responsiblefor the diâµerences found in the previous section. Dorsal Attention (Dors)and Salvent (Sal) are two attention systems of the brain [43], Limbic isresponsible for learning, memory and emotion and these RSNs have showndiâµerences in number of clusters. Welchâs t-test for these three RSNs gavep-values of 0.0055 for Dors, 0.0090 for Sal and 0.0011 for Limbic.Figure 6.4 shows the comparison between the number of clusters gen-erated by the Louvain algorithm and our algorithm for the RSNs Limbic,Dors and Sal - the RSNs responsible for learning, emotion and attentivenessin our brain. As we can observe, the results from Louvain donât show muchdiâµerence in the number of clusters of high ADHD and low ADHD patients.Welchâs t-test for the Louvain algorithm gave p-values of 0.551 for Dors,0.0751 for Sal and 0.498 for Limbic.To find out diâµerences between contents of the clusters of 2 ROIs in516.2. Analysis of fMRI Dataeach patient, we applied Jaccard Index. We first took a patientâs RSN andFigure 6.4: Comparison between the number of clusters generated by ouralgorithm and the Louvain algorithm for RSNs Limbic, Dors and Sal. Leftcolumn represents results from our algorithm, right column represents Lou-vainâs algorithm results.52Index of patientsIndex of patientsIndex of patientsIndex of patientsIndex of patientsIndex of patientsAverage no. of clustersAverage no. of clustersAverage no. of clustersAverage no. of clustersAverage no. of clustersAverage no. of clusters0 2 4 6 80 2 4 6 80 2 4 6 80 2 4 6 80 2 4 6 80 2 4 6 8High ADHDHigh ADHDHigh ADHDHigh ADHDHigh ADHDHigh ADHDLow ADHDLow ADHD Low ADHDLow ADHD Low ADHDLow ADHD13.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.013.5 14.0 14.5 15.0 15.5 16.08.6 8.8 9.0 9.28.6 8.8 9.0 9.28.6 8.8 9.0 9.26.2. Analysis of fMRI DataFigure 6.5: Comparison between the Jaccard Index between clusters of pa-tients with high (blue) and low (orange) ADHD index for the 7 RSNs. Avalue in the histogram denotes the average of number of cluster-pairs, be-tween each ROI-pair, that have Jaccard Index values greater than equal to0.7 (or 70%), calculated for all ROI-pairs of one RSN of one patient.chose 2 ROIs from it. For the ROI-pair, we applied Jaccard index (JI)between the clusters of the ROIs (considering one cluster as one set) andnoted the number of cluster-pairs for which the JI-value is greater than orequal to 0.7 (or the JI-percentage is greater than 70%). We calculated thesenumbers for all the ROI-pairs in the RSN, averaged it and plotted it in thehistogram as one value. Same steps were applied to get the average numberof cluster-pairs with  0.7 JI-value, for all the RSNs of the 9 patients.Figure 6.5 represents the results of implementing above steps, for thetwo patient-sets. The y-axis is the average number of clusters with JI-value 0.7 per RSN per patient and the x-axis denotes the RSNs. Values ofpatients with high ADHD are colored in blue whereas orange color denotesvalues of patients with low ADHD. Regression or trendlines show that theaverage number is higher for patients with low ADHD, more specifically inCont and Sal. Welchâs t-test generated p-value of 0.11 for RSN Cont and0.099 for RSN Sal. It shows that there are clusters between 2 ROIs withhigh Jaccard indexes, and it is likely that during these segments the twoROIs reflect similar neural events [41]. Therefore, neural similarity is morein low ADHD index patients.To check the diâµerences in inter-ROI mutual information between thetwo patient-sets, we first took data from one RSN of one patient and calcu-53Cont Sal Dors Limbic Som Vis DefaultHigh ADHD Low ADHD Low ADHD Trendline High ADHD Trendline6.2. Analysis of fMRI DataFigure 6.6: Comparison between the average inter-ROI mutual informationbetween patients with (a) high and (b) low ADHD index for the 7 RSNs.54Cont Default Dors Limbic Sal Som VisRSNsCont Default Dors Limbic Sal Som VisRSNs6.56.57.07.0ContDefaultDorsLimbicSalSomVisContDefaultDorsLimbicSalSomVis6.2. Analysis of fMRI Datalated the interlayer mutual information between all the ROIs of that RSNusing Equation (5.2). We then plotted the average of the calculated values,9 values (one per patient) per RSN, for the two sets. The number of ROIpairs per RSN depends upon the number of ROIs the RSN has, for example,RSN Vis has 162 ROIs, RSN Som has 194, etc.Figure 6.6 shows the results in the form of violin plots. For each set,each circle corresponds to < MI >, the average mutual information value,of a given subject. Random average shifted histograms that show statisticalmeasures like kernel-density estimates, median of Harrell-Davis estimator,and the 95% high density intervals using a Bayesian bootstrap are alsoshown in the figure, generated using ggplotâs violin plot in R programminglanguage. The density estimator has higher value for RSNs of low-ADHDpatients, and there is a clear diâµerentiation in all the RSNs. T-test for theRSNs gave p-values of 0.0034 for Sal, 0.044 for Limbic and 0.010 for Som.Figure 6.7 shows the results of average inter-ROI mutual informationbetween patients with high and low ADHD index for the 7 RSNs, usingEquation (5.1). There is not much diâµerence that can be observed in thestructure of violin plots between low and high ADHD data values. T-testfor the RSNs gave p-values of 0.1495 for Sal, 0.2676 for Limbic and 0.3373for Som.RSN levelFor carrying out implementation at RSN level, we used data from the UCLACNP study of healthy individuals and patients suâµering from Schizophrenia,ADHD and Bipolar Disorder. As mentioned earlier, the preprocessed datawas in the form of NIfTI-1 image files, out of which the time series wereextracted using Yeo atlas, as described in [46]. For the implementation,we first parcellated the data following Yeo parcellation into 7 subregions (orRSNs), using the python library ânilearnâ which is a module for fast and easystatistical learning on NeuroImaging data. Then we used NiftiLabelsMaskerin Python to generate the time series, one series per RSN. These 7 time-series were then used to generate the RSN-specific results, for each of the40 individuals.Our data has 4 sets: Controls, Schizophrenia, ADHD and Bipolar Dis-order and we will observe how these sets diâµer from each other in termsof number of clusters and mutual information. Each patient has 7 visibil-ity graphs (one per RSN), and for each graph, clusters were generated andtheir number was plotted in a pirate plot in Figure 6.8, in the order of eachpatient set and each RSN. A point in the plot corresponds to the number556.2. Analysis of fMRI DataFigure 6.7: Comparison between the average inter-ROI mutual information(using Equation (5.1) between patients with (a) high and (b) low ADHDindex for the 7 RSNs.56Cont Default Dors Limbic Sal Som VisCont Default Dors Limbic Sal Som VisRSNsRSNsContDefaultDorsLimbicSalSomVisContDefaultDorsLimbicSalSomVis0.50.51.01.06.2. Analysis of fMRI DataFigure 6.8: Comparative pirate plot showing diâµerent number of clustersfor each patient-set (A: ADHD, BD: Bipolar Disorder, C: Controls and S:Schizophrenia), per RSN.of clusters in the visibility graph of one RSN of one patient. The plot hasmean-value marker, full-densities and 95% Highest Density Intervals (HDIs)for each group. In most of the cases, the set Schizophrenia has the highestnumber of clusters, and Controls mostly has higher or almost similar valuesthan Bipolar, based on the mean values. We got a p-value of 0.046 of valuesfor controls and schizophrenics for RSN Dors.Figure 6.9 shows the diâµerence in mutual information values within eachof the RSNs, for the four groups of subjects considered, in the form of a vio-lin plot. Each point in the plot corresponds to mutual information betweenvisibility graphs of two patients belonging to the same set, considering thesame RSN. As it can be observed, all the RSNs from all the sets show dif-ferent densities and estimator values, with more diâµerences shown in Limbicand Sal, and lesser diâµerences shown in Cont.576.3. Analysis of EEG SignalsFigure 6.9: Comparison of mutual information between Controls and pa-tients with Schizophrenia, ADHD and Bipolar Disorder for the 7 RSNs.6.3 Analysis of EEG SignalsWe will now observe alterations or diâµerences between patient-sets and con-trols using EEG signal time series.6.3.1 EEG DataThe data was retrieved from [1] which is a study on healthy individuals andpatients with Epilepsy, as mentioned in [3]. The data has 5 sets, and each setconsists of EEG values from 100 individuals recorded for a duration of 23.6seconds. Each time series has 4096 value points. Below is a brief descriptionof the sets:â¢ Set A: Extracranial recording of healthy subjects with eyes open.â¢ Set B : Extracranial recording of healthy subjects with eyes closed.58Bipolar Disorder ADHDCont Default Dors Limbic Sal Som VisControls SchizophreniaCont Default Dors Limbic Sal Som VisCont Default Dors Limbic Sal Som VisCont Default Dors Limbic Sal Som VisRSNsRSNsRSNsRSNsMIMIMIMI1010 1010888866 666.3. Analysis of EEG SignalsFigure 6.10: Comparison between number of clusters for the 5 sets of EEGvalues.â¢ Set C : Intracranial recording of epileptic patients from the hippocam-pal part of the brain, without seizures.â¢ Set D : Intracranial recording of patients from within the epileptic zoneof the brain, without seizures.â¢ Set E : Intracranial recording of patients from within the epileptic zoneduring seizures.The data was already preprocessed and we used all the 500 time series forour implementations.6.3.2 ResultsThe first implementation towards finding any diâµerences between the patient-sets and healthy individuals was to create signed visibility graphs of the EEGtime series and form clusters according to our methods, for all the time seriesbelonging to the 5 sets. After creating the clusters, we noted their quantityin each time series and plotted the graph in Figure 6.10.In the figure, the bar denotes mean values for each set with Â± standarderror of the mean. The mean values are also mentioned at the bottom of eachbar for the particular set. Each point in the scatter plot denotes numberof clusters in one time series belonging to the respective set. Set B has the59Patient-setsNumber of clusters6.3. Analysis of EEG SignalsFigure 6.11: Comparison between Jaccard Indexes for the 5 sets. A smalljitter in the values was added for clearer visual representation.highest number of clusters, but set E has more spread-out or diverse values(higher variance). Higher the number of clusters, smaller the cluster sizesince the number of value points are same. Smaller the cluster size, morethe number of high and low (or extreme) value points in the data. Patientswith epilepsy (without seizures) showed lower number of clusters, suggestingthat they have smaller variation in their value points. P-value of Welchâst-test between set B and set D came out to be 2.2e-16, with a t-value of18.835. Since set E was recorded during seizures, the EEG values wouldhave been highly fluctuating, therefore giving these results.To examine the similarities or diâµerences within the clusters, we calcu-lated Jaccard Index. For each pair of time series belonging to a set, theJaccard Index values were calculated, so as to know which set has moresimilar elements in the clusters.Figure 6.11 shows a comparative box-plot scatter chart for the JaccardIndexes in the 5 sets. Each point in the plot denotes JI-value between twotime-series belonging to same set. Set B has the highest average JI-value,showing that the time-series in this set have highest similarities with eachother. Set E has high mean JI-value too, but it consists of a lot of outlier606.3. Analysis of EEG SignalsFigure 6.12: Comparison between average cluster sizes for the 5 sets of EEGvalues.values, probably due to the fact that seizures introduce a lot of randomnessin the EEG values. Sets C and D have almost similar and low JI-values,indicating that the time series are more diâµerent in these sets.For our final result, we calculated the cluster sizes for each time series ineach set, expecting opposite results from Figure 6.10, i.e., higher the numberof clusters, lower the clustersâ sizes. Figure 6.12 shows the results and asexpected, we see that sets B and E, that had the highest number of clusters,have the lowest average cluster size values.61Size of clustersPatient-setsChapter 7ConclusionIn this thesis, we introduced a new concept of signed visibility graphs thatcan be used to improve the eâµectiveness of graph-theoretical approach toanalyse time series data. We also studied about partitioning in visibilitygraphs and designed a new clustering algorithm based on signed visibil-ity graphs and dynamic programming, that creates disjoint time-respectingclusters.We compared our algorithm with the Louvain algorithm of communitydetection to find that our algorithm gives more reliable results in termsof clustering of visibility graphs. We also redefined the mutual correlationmeasure between two time-series by including the degree distributions dueto negative edges. Comparison between the original mutual correlation mea-sure and the redefined measure showed that our measure is more informativein terms of the amount of correlation between any two visibility graphs.We then applied our methods to datasets of fMRI and EEG signals ofhealthy individuals and patients suâµering from certain neurological disordersand found diâµerences in the results of implementations.For future study, the methods and concepts discussed in this work couldbe applied to many other fields to get some useful insights. The resultsnoted in last chapter could be used to find reasons behind the diâµerencesobserved, adding to the knowledge of these disorders for better identificationand diagnosis. This work could also be a source of reference for creatingmore time-respecting clustering algorithms using other notions in networkscience.62Bibliography[1] Ralph G. Andrzejak, Klaus Lehnertz, Florian Mormann, ChristophRieke, Peter David, and Christian E. Elger. Indications of nonlineardeterministic and finite-dimensional structures in time series of brainelectrical activity: Dependence on recording region and brain state.Phys. Rev. E, 64:061907, Nov 2001.[2] Danielle Smith Bassett and Ed Bullmore. Small-world brain networks.The Neuroscientist, 12(6):512â523, 2006. PMID: 17079517.[3] Susmita Bhaduri and Dipak Ghosh. Electroencephalographic data anal-ysis with visibility graph technique for quantitative assessment of braindysfunction. Clinical EEG and neuroscience, 46, 04 2014.[4] Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Eti-enne Lefebvre. Fast unfolding of communities in large networks. Journalof Statistical Mechanics Theory and Experiment, 2008, 04 2008.[5] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Eti-enne Lefebvre. Fast unfolding of communities in large networks. J. Stat.Mech. (2008) P10008, 2008.[6] Peter J. Brockwell and Richard A. Davis. Time Series: Theories andMethods. Springer, second edition, 1991.[7] Ed Bullmore and Olaf Sporns. Complex brain networks: graph theo-retical analysis of structural and functional systems. Nature ReviewsNeuroscience, 10, 2009.[8] Neuro Bureau. Adhd 200. http://fcon_1000.projects.nitrc.org/indi/adhd200/. Accessed: 2018-08-16.[9] Q Cao, YF Zang, L Sun, M Sui, X Long, Q Zou, and YF Wang. Ab-normal neural activity in children with attention deficit hyperactivitydisorder: a resting-state functional magnetic resonance imaging study.Neuroreport, pages 1033â1036, 2006.63Bibliography[10] Fan Chung and Linyuan Lu. Complex Graphs and Networks. AmericanMathematical Society, 2006.[11] David Easley and Jon Kleinberg. Networks, Crowds, and Markets.Cambridge University Press, 2010.[12] Mark E.J. Newman and Michelle Girvan. Finding and evaluating com-munity structure in networks. Physical review. E, Statistical, nonlinear,and soft matter physics, 69:026113, 03 2004.[13] Oscar Esteban, Christopher Markiewicz, Ross W Blair, Craig Moodie,Ayse Ilkay Isik, Asier Erramuzpe Aliaga, James Kent, MathiasGoncalves, Elizabeth DuPre, Madeleine Snyder, Hiroyuki Oya, Satra-jit Ghosh, Jessey Wright, Joke Durnez, Russell Poldrack, andKrzysztof Jacek Gorgolewski. Fmriprep: a robust preprocessingpipeline for functional mri. bioRxiv, 2018.[14] H. Everett. Visibility Graph Recognition. PhD thesis, University ofToronto, Toronto, Ont., Canada, Canada, 1990. UMI Order No.[15] Santo Fortunato. Community detection in graphs. Physics Reports,486(3):75 â 174, 2010.[16] Wayne A. Fuller. Introduction to Statistical Time Series. John Wiley& Sons, 2009.[17] Saptorshi Ghosh and Amlan Dutta. An ecient non-recursive algorithmfor transforming time series to visibility graph. Physica A: StatisticalMechanics and its Applications, 514(C):189â202, 2019.[18] KJ Gorgolewski, J Durnez, and RA Poldrack. Preprocessed consortiumfor neuropsychiatric phenomics dataset. F1000Research, 2017.[19] Krzysztof J. Gorgolewski and et al. The brain imaging data struc-ture, a format for organizing and describing outputs of neuroimagingexperiments. Scientific Data, 2016.[20] Frank Harary. On the notion of balance of a signed graph. MichiganMath. J., 2(2):143â146, 1953.[21] Hipel and McLeod. High and low water levels of the amazonat iquitos, 1962 1978. https://datamarket.com/data/set/22u5/high-and-low-water-levels-of-the-amazon-at-iquitos-1962-1978#!ds=22u5&display=column. Accessed: 2018-03-19.64Bibliography[22] I. A. Iwok and A. S. Okpe. A comparative study between univariate andmultivariate linear stationary time series models. American Journal ofMathematics and Statistics, 6, 2016.[23] Alec Kirkley, George T. Cantwell, and M E. J. Newman. Balance insigned networks. Physical Review E, 99, 01 2019.[24] Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson Education,2006.[25] L. Lacasa, V. Nicosia, and V. Latora. Network structure of multivariatetime series. Scientific Reports, 2015.[26] Lucas Lacasa, Bartolo Luque, Fernando Ballesteros, Jordi Luque, andJuan Carlos NunËo. From time series to complex networks: The visibilitygraph. Proceedings of the National Academy of Sciences, 105(13):4972â4975, 2008.[27] Xin Lan, Hongming Mo, Shiyu Chen, Qi Liu, and Yong Deng. Fasttransformation from time series to visibility graphs. Chaos (Woodbury,N.Y.), 25:083105, 08 2015.[28] B. Luque, L. Lacasa, F. Ballesteros, and J. Luque. Horizontal visibilitygraphs: Exact results for random time series. Phys. Rev. E, 80:046103,Oct 2009.[29] P. K. Mandal, R. Mahajan, and I. D. Dinov. Structural brain atlases:design, rationale, and applications in normal and pathological cohorts.Journal of Alzheimerâs disease : JAD, 2012.[30] M. E. J. Newman. Modularity and community structure in networks.Proceedings of the National Academy of Sciences, 103(23):8577â8582,2006.[31] Mark Newman. Networks: An Introduction. Oxford University Press,2010.[32] Vincenzo Nicosia, Lucas Lacasa, and Vito Latora. From multivariatetime series to multiplex visibility graphs. Scientific Reports, 08 2014.[33] NITRC. The neuro bureau adhd 200 preproc. https://www.nitrc.org/frs/?group_id=383. Accessed: 2018-08-16.[34] Hae-Jeong Park and Karl Friston. Structural and functional brain net-works: From connections to cognition. Science, 342(6158), 2013.65Bibliography[35] R. A. Poldrack, E. Congdon, W. Triplett, K. J. Gorgolewski, K. H.Karlsgodt, J. A. Mumford, F. W. Sabb, N. B. Freimer, E. D. London,T. D. Cannon, and R. M Bilder. Ucla consortium for neuropsychiatricphenomics la5c study. https://openneuro.org/datasets/ds000030/versions/00016. Accessed: 2018-07-28.[36] R. A. Poldrack, E. Congdon, W. Triplett, K. J. Gorgolewski, K. H.Karlsgodt, J. A. Mumford, F. W. Sabb, N. B. Freimer, E. D. London,T. D. Cannon, and R. M Bilder. Ucla consortium for neuropsychi-atric phenomics la5c study. https://legacy.openfmri.org/dataset/ds000030/. Accessed: 2018-07-28.[37] R. A. Poldrack, E. Congdon, W. Triplett, K. J. Gorgolewski, K. H.Karlsgodt, J. A. Mumford, F. W. Sabb, N. B. Freimer, E. D. London,T. D. Cannon, and R. M Bilder. A phenome-wide examination of neuraland cognitive function. Scientific data, 12 2016.[38] Gregory C. Reinsel. Elements of Multivariate Time Series Analysis.Springer Science & Business Media, Dec. 6, 2012, 2012.[39] Peter A Rinck. Magnetic Resonance in Medicine. BoD, 2017.[40] NM Saitou and Masatoshi Nei. The neighbor-joining method: A newmethod for reconstructing phylogenetic trees. Mol Biol Evol, 24:189â204, 07 1987.[41] Speranza Sannino, Sebastiano Stramaglia, Lucas Lacasa, and DanieleMarinazzo. Visibility graphs for fmri data: Multiplex temporal graphsand their modulations across resting-state networks. Network Neuro-science, 1(3):208â221, 2017.[42] A Schaefer, R Kong, EM Gordon, TO Laumann, XN Zuo, AJ Holmes,SB Eickhoâµ, and Yeo BTT. Local-global parcellation of the human cere-bral cortex from intrinsic functional connectivity mri. Cerebral Cortex,page 30953114, 9 2018.[43] Simone Vossel, Joy J. Geng, and Gereon R. Fink. Dorsal and ventralattention systems: Distinct neural circuits but collaborative roles. TheNeuroscientist, 20(2):150â159, 2014. PMID: 23835449.[44] Qi Wang, Rong Chen, Joseph Ja´Ja´, Yu Jin, L. Elliot Hong, and EdwardHerskovits. Connectivity-based brain parcellation. Neuroinformatics,14:83â97, 2015.66[45] Duncan Watts and Steven H. Strogatz. Collective dynamics of smallworld networks. Nature, 393:440â2, 07 1998.[46] B. T. Yeo, F. M. Krienen, J. Sepulcre, M. R. Sabuncu, D. Lashkari,M. Hollinshead, J. L. Roâµman, J. W. Smoller, L. Zllei, J. R. Polimeni,B. Fischl, H. Liu, and R. L. Buckner. The organization of the humancerebral cortex estimated by intrinsic functional connectivity. Journalof Neurophysiology, pages 1125â1165, 2011.[47] Wayne W. Zachary. An information flow model for conflict and fissionin small groups. Journal of Anthropological Research, 33(4):452â473,1977.[48] Guohun Zhu, Yan Li, and Peng Paul Wen. An ecient visibility graphsimilarity algorithm and its application on sleep stages classification.In Fabio Massimo Zanzotto, Shusaku Tsumoto, Niels Taatgen, andYiyu Yao, editors, Brain Informatics, pages 185â195, Berlin, Heidel-berg, 2012. Springer Berlin Heidelberg.67Appendix AImplementation ProgramsWe will list all the Python codes for the implementations done in this thesishere.Following is the program for creating natural signed visibility graphsfollowing Algorithm 1, mentioned in Chapter 3.Program A.1 Program for Natural Signed Visibility Graphsimport networkx as nximport matplotlib.pyplot as plty = [25.82, 25.35, 24.29, 24.05, 24.89, 25.35, 25.23, 25.06, 27.13,27.36, 26.65, 27.13, 27.49, 27.08, 27.51, 27.54, 26.21, 18.24,16.5, 20.26, 20.97, 19.43, 19.31, 20.85, 19.54, 20.49, 21.91,22.51, 18.81, 19.42, 19.1, 18.8, 18.8, 17.57]t = list(range(0, len(y)))nodes = list(range(0, len(y)))v1 = [] #v1 consists of first set of nodesv2 = [] #v2 consists of the nodes which have an edge with nodes inv1, stored in the same order as v1inv_v1 = []inv_v2 = []posn = {}for a in range(0, len(y)):v3 = []for b in range(0, len(y)):visible = Truevisible2 = Trueif(t[b]> t[a]):if(t[b] == t[a] + 1):v1.append(a)v3.append(b)else:for c in range(0, len(y)):if (t[c] < t[b] and t[c] > t[a]):68Appendix A. Implementation Programsvalue = y[b] + ((y[a] - y[b]) * ((t[b] -t[c]) / (t[b] - t[a])))if(y[c] > value):visible = Falseelif(y[c] < value):visible2 = Falseif(visible== False and visible2==False):breakif visible == True:if b not in v3:v1.append(a)v3.append(b)elif visible2 == True:if b not in inv_v3:inv_v1.append(a)inv_v3.append(b)v2.extend(v3) #merge the newly found nodesinv_v2.extend(inv_v3)#Code for creating the graphG=nx.Graph()G.add_nodes_from(nodes)for i in range(0, len(v1)):G.add_edge(v1[i], v2[i], weight = 1, color = âgâ)for i in range(0, len(inv_v1)):if(G.has_edge(inv_v1[i], inv_v2[i])==False):G.add_edge(inv_v1[i], inv_v2[i], weight = 0, color = ârâ)for node in nodes:posn[node] = (t[node], y[node])edges = G.edges()colors = [G[u][v][âcolorâ] for u,v in edges]position = nx.spring_layout(G, pos = posn, fixed = nodes)nx.draw(G, pos=position, edge_color=colors, with_labels=True,node_color = âbâ)plt.show()69Appendix A. Implementation ProgramsFollowing is the Python code for implementing Algorithm 2 as mentionedin Chapter 3, for creating a horizontal signed visibility graph.Program A.2 Program for Horizontal Signed Visibility GraphssortList.append(y[0])for i in range(1, len(y)):G2.add_edge(y[i], y[i-1], weight = 1, color = âgâ)if(y[i]>y[i-1]):loc = -1for g in sortList:if(g<y[i]):loc = loc+1else:breakif(loc>-1):counter = 0while(counter<=loc):G2.add_edge(y[i], sortList[0], weight = 1, color =âgâ)del sortList[0]counter = counter+1sortList.append(y[i])sortList.sort()#Code for FHVG (Negative edges)max_y2 = max(y)inv_y2 = []inv_sortList = []for i in range(0,len(y)):inv_y2.append((max_y2+1)-y[i])inv_sortList.append(inv_y2[0])for i in range(1, len(inv_y2)):if(inv_y2[i]>inv_y2[i-1]):loc = -1for g in inv_sortList:if(g<inv_y2[i]):loc = loc+1else:breakif(loc>-1):counter = 0while(counter<=loc):70Appendix A. Implementation Programsy_val = (max_y2+1)-inv_y2[i]sort_val = (max_y2+1)-inv_sortList[0]if(G2.has_edge(y_val, sort_val)==False):G2.add_edge(y_val, sort_val, weight = 0, color =ârâ)del inv_sortList[0]counter = counter+1inv_sortList.append(inv_y2[i])inv_sortList.sort()#Code for creating the graphfor node in nodes:posn[y[node]] = (t[node], y[node])edges = G2.edges()colors = [G2[u][v][âcolorâ] for u,v in edges]position = nx.spring_layout(G2, pos = posn, fixed = y)nx.draw(G2, pos=position, edge_color=colors, with_labels=True,node_color = âbâ)plt.show()Following is the program for implementing the divide and conquer algo-rithm (Algorithm 3) for creating a signed visibility graph.Program A.3 Program for Divide and Conquer algorithmTS = list(y)def TStoVGfast(TS2, left, right):if(left<right):k = TS2.index(max(TS2))k = k+leftfor i in range(left, right+1):if(k==i+1 or i==k+1):G.add_edge(k, i, weight = 1, color = âgâ)else:visible = Truevisible2 = Truefor j in range(left, right+1):if(k<i):if(j<i and j>k):value = y[i] + ((y[k] - y[i]) * ((t[i] -t[j]) / (t[i] - t[k])))71Appendix A. Implementation Programsif(y[j] > value):visible = Falseelif(y[j] < value):visible2 = Falseif(visible== False and visible2==False):breakif(i<k):if(j<k and j>i):value = y[k] + ((y[i] - y[k]) * ((t[k] -t[j]) / (t[k] - t[i])))if(y[j] > value):visible = Falseelif(y[j] < value):visible2 = Falseif(visible== False and visible2==False):breakif(visible==True and k!=i):G.add_edge(k, i, weight = 1, color = âgâ)elif(visible2==True and k!=i and G.has_edge(k,i)==False):G.add_edge(k, i, weight = 0, color = ârâ)if(len(TS2)==2):return NoneTS_left = TS[left:k]TS_right = TS[k+1:right+1]TStoVGfast(TS_left, left, k-1)TStoVGfast(TS_right, k+1, right)left1 = 0right1 = len(y)-1TS1 = list(y)TStoVGfast(TS1, left1, right1)72Appendix A. Implementation ProgramsFollowing is the Python implementation of the partitioning algorithmmentioned in Chapter 4. In the code the quality func contains both thecases if i = j  1 or not equal. The variable clusters is a list of lists thatconsists of all the clusters of the graph.Program A.4 Program for Partitioning algorithmweight=nx.get_edge_attributes(G,âweightâ)mini = []i_min = []clusters = []memo = []memon = [] #memo numeratormemod = [] #memo denominatorfor z in range(0, len(y)):memo.append(0)memon.append(0)memod.append(0)mini.append(0)i_min.append(0)def quality_func(j2, i2, memon1, memod1):nin = 0pout = 0nout = 0pin = 0change = 0if(i2==j2-1):for a in range(0, len(y)):if(G.has_edge(a, i2) == True):if(a<i2):edgeweight = weight[a, i2]else:edgeweight = weight[i2, a]if(a==j2):if(edgeweight == 0):memod1 = memod1+1 #ninelse:memon1 = memon1+1 #pinelse:if(edgeweight == 0):memon1 = memon1+1 #nout73Appendix A. Implementation Programselse:memod1 = memod1+1 #poutfor a in range(0, len(y)):if(a==i2 and i2==j2-1):continueif(G.has_edge(a, j2) == True):if(a<j2):edgeweight = weight[a, j2]else:edgeweight = weight[j2, a]if a in range(i2, j2+1):if(edgeweight == 0):nin = nin+1memon1 = memon1-1else:pin = pin+1memod1 = memod1-1else:if(edgeweight == 1):pout = pout+1else:nout = nout+1memon[i] = pin + nout + memon1memod[i] = nin + pout + memod1if(memod[i] == 0):change = memon[i]else:change = memon[i]-memod[i]return change;for j in range(1, len(y)):quality = 0for i in range(0, j):if(i==j-1):quality = quality_func(j, i, 0, 0);else:quality = quality_func(j, i, memon[i], memod[i]);memo[i]=qualityif(i==0):mini[j] = qualityi_min[j] = iif(quality>=mini[j]):mini[j] = qualityi_min[j] = i74Appendix A. Implementation Programsj = len(y)-1 #last node in the graphwhile(j>=0):i = i_min[j]clusters.append(list(range(i, j+1)))j = i-1if(j==1 and clusters[-1] != [0,1]):clusters.append([0,1])75
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Signed visibility graphs of time series and their application to brain networks
Text