Complex Network Analysis Tools

This weekend we had HackU and while searching for ideas, I thought of why not make an app which would visualize a complex network based on various input data, but when I searched for similar apps found many softwares and apps already available, and thus listed few of them:

Why Network Analysis tools required ?

Network analysis tools allow researchers to investigate representations of networks of different size - from small (e.g. families, project teams) to very large (e.g. the Internet, disease transmission). The various tools provide mathematical and statistical routines that can be applied to the network model.

Visual representations of social networks are important to understand network data and convey the result of the analysis. And thus these tools are used to identify, represent, analyze, visualize, or simulate nodes (e.g. agents, organizations, or knowledge) and edges (relationships) from various types of input data (relational and non-relational), including mathematical models of social networks

There are various Network Analysis tools available for specific as well as generic purposes, few are mentioned here :

SocNetV (Social Networks Visualizer) is an open-source graphical application, developed in C++ language and the cross-platform Qt toolkit. The user interface is friendly and simple, allowing the researcher to draw social networks or plain graphs by clicking on a canvas. SocNetV computes basic network properties (i.e. density, diameter, shortest path lengths), as well as more advanced statistics, such as centralities (i.e. closeness, betweeness, graph), clustering coefficient, etc. Various layout algorithms are supported. For instance, nodes can be automatically positioned on circles or levels according to their betweeness centralities. Random networks and small world creation is also supported. SocNetV can handle any number of nodes, although with a speed penalty when nodes are more than 3000 or the graph is quite dense (many edges).

Financial Network Analyzer (FNA) is an application for the statistical analysis of financial networks using methods developed in network science and social network analysis. It differentiates from other tools in that it builds networks from message (payments, trades, etc.) data and that it is geared towards the analysis of network times series.

igraph is a C library for the analysis of large networks. It includes fast implementations for classic graph theory problems and recent network analysis methods like community structure search, cohesive blocking, structural holes, dyad and triad census and motif count estimation. Higher level interfaces are available for R, Python and Ruby.

AutoMap

Text mining tool that supports the extraction of relational data from texts. Distills three types of information: content analysis, semantic networks, ontologically coded networks. In order to do this, a variety of Natural Language Processing/ Information Extraction routines is provided (e.g. Stemming, Parts of Speech Tagging, Named-Entity Recognition, usage of user-defined ontologies, reduction and normalization, Anaphora Resolution, email data analysis, feature identification, entropy computation, reading and writing from and to default or user-specified database).

CFinder is a software for finding and visualizing overlapping dense communities in networks, based on the clique percolation method. It enables customizable visualization and allows easy strolling over the found communities. The package contains a command line version of the program as well, suitable for scripting.

Commetrix is a Software Framework and Tool for Dynamic Network Analysis and Visualization. It provides easy exploratory access to network graphs and has been applied to study co-authorship, Instant Messaging, manual SNA surveys, e-mail, newsgroups, etc. Each node and each linking event can have properties, e.g. types of messages or rank of nodes, but also types, topics, or time stamps. This allows animations of network growth, structural change, and topic diffusion.

iPoint monitors and analyzes Consumer Generated Media, the full privacy of the author is maintained and its reporting dashboard reads from iMediaStreams web services. The analysis is easily viewed and managed from the worldwide, to the state, to the hyper local neighborhood level. It is this aggregation of news and topics, overlaid with sentiment and demographics, which provides a unique research tool into the areas that are uppermost on peoples minds.

Java Universal Network/Graph (JUNG) Framework is a Java API and library that provides a common and extensible language for the modeling, analysis, and visualization of relational data. It supports a variety of graph types (including hypergraphs), supports graph elements of any type and with any properties, enables customizable visualizations, and includes algorithms from graph theory, data mining, and social network analysis (e.g., clustering, decomposition, optimization, random graph generation, statistical analysis, distances, flows, and centrality (PageRank, HITS, etc.)). It has been used to analyze networks in excess of 1 million nodes (although visualizations are currently more limited), and is limited only by the amount of memory allocated to Java.

NodeXL is a free and open Excel 2007 Add-in and C#/.Net library for network analysis and visualization. It integrates into Excel 2007 and 2010 and adds directed graph as a chart type to the spreadsheet and calculates a core set of network metrics and scores. Supports extracting email, Twitter, YouTube and flickr social networks. Accepts edge lists and matrix representations of graphs. Allows for easy manipulation and filtering of underlying data in spreadsheet format. Multiple network visualization layouts. Reads and writes UCINet and GraphML files.

UrlNet is a Python class library for generating networks based on Internet linkages. In the simplest case, UrlNet creates a tree by harvesting the outlink URLs from the page referenced by a root URL (level zero); retrieving each of those pages (level 1), harvesting their outlink URLs; retrieving those pages (level 2), harvesting their outlink URLs; et cetera to a caller-specified depth. UrlNet can also create "forests", the union of multiple tree networks. Specialized classes are provided for generation of networks from search engine result sets (6 search engines are currently supported). UrlNet can also utilize URL-based Web Service APIs to generate networks. Current examples include Technorati's Cosmos API and three types of networks utilizing APIs provided by the National Center for Biological Information (NCBI) .

Cytoscape is an open source bioinformatics software platform for visualizing molecular interaction networks and biological pathways and integrating these networks with annotations, gene expression profiles and other state data.   Although Cytoscape was originally designed for biological research, now it is a general platform for complex network analysis and visualization.   Cytoscape core distribution provides a basic set of features for data integration and visualization.   Additional features are available as plugins.

NetEvo Framework C-Based Development Kit (Cross platform) is a tool to  study the behavior of complex systems, it provides two main functions, simulation and evolution of dynamical networks. To make use of these features, end-users must provide the following to customize the framework for the problem of interest:

Set of component dynamics for nodes and edges,

An initial topology, unless the network can grow,

The evolutionary process that searches for improved system configurations,

The performance measure Q to guide evolution. 

My favorite is the NodeXL as its easy to use and easy to integrate.

Privacy Leaks and Idea of Social Spheres

As with growing online social networking sites (SNS), people want their freedom to express their opinions and share their views with friends or, everyone. However, as with the real world there exists problems with SNS too. People don't want others to use their personal information in a way that they find, violating their personal space, e.g. SNS may help advertisers to target users based on their profile and activity information. Not every user would agree to allow SNS to reveal their information to advertisers. More extreme examples may include spams, sexual predators and stalkers.

Though, many SNS reveal sensitive information about users and their ties, through anonymization for data mining to be used by advertisers, app developers or in research, people have developed de-anonymization algorithm using only the anonymized network topology, e.g. [1] a third of the users who can be verified to have accounts on both Twitter, a popular microblogging service, and Flickr, an online photo-sharing site, can be re-identified in the anonymous Twitter graph with only a 12% error rate.

People may not realize what they share can lead to, e.g. on Twitter, a large number of users who unwittingly post sensitive information. Tweets telling about people's vacation plans may reveal their planned schedule publicly. The z-score of ratio of vacation tweets in the period of January to September 2010. Four vacation spikes are seen at the beginning of January, the end of May, beginning of July, and end of August, where z-score indicates how many standard deviations an observation is above or below the mean.

Well, people are even more out of control when blogging drunk as shown by the comparison between drunk and sober tweets. For drunk tweets, one can perform content analysis to find out all private topics revealed.

 

Another category can relate to people tweeting about what diseases surround them, using words like “disease”,“syndrome”, and “disorder”. Now, such information leaks may be divided into two types of leaks, status leaks and conversation leaks. Further leaks can be classified into primary (user tweeting about herself) and secondary (tweeting about another person).

Above histograms indicate that there are more secondary leaks about Cancer or HIV relative to Diabetes, i.e. though people don't want to reveal their private information about these two diseases, they get revealed through their friends or family.

How to visualize & protect the privacy leaks through social spheres?

We can define something called profile distance of two users, i & j in an N-dimensional profile space P, having a profile vector p for every user given by
p = (e(1), ..., e(N)), where e(i) is a profile parameter, as :

And the personal sphere of a user will not contain user k if

where r is a radius of the sphere quantifying the requirement conforming to the this model. The N-dimensional vector space can be mapped to 2-dimensional space using MDS, multi-dimensional scaling preserving the distances for correct visualization.

Now, a user might want to share sensitive information within this sphere but not caring that this information can continue through their friends' spheres outside the user's original sphere, e.g. through Facebook apps users share their information though as per the privacy setting, but its not easy to see exactly what information will be shared among whom.

To see which application's ideal privacy requirements match with that of a user's privacy profile settings, one can define an application vector and see its distance from the user profile in the N-dimensional space, e.g. making four clusters of applications including Farmville, Phrases, Texas, HoldEm Poker, and other, thereby, taking r = 3, a typical facebook recommended user profile and a restrictive user profile (friends only) are matched.

As seen, the Are You Interested? type applications are far outside the sphere of a restrictive user implying that the future application developers should set app's privacy requirements in such a way that it has a close euclidean distance from even the restrictive users since with growing privacy and security concerns among the SNS, number of such users, who care deeply about their privacy, is likely to increase.

However, a single personal sphere doesn't match the different social spheres of people in real life where we have different circles related to friends, family, or profession.

If we don't take care of this fact, treat all online friends equal in the same personal sphere of a user, it will lead to what's called social tension among the actually different social spheres of users. Users may not realize the actual size of listeners when they share their views or pictures, they may also not notice that unlike the real world, posts, tweets or any other shared data are persistent staying for a long time in the SNS for people to view later.

This kind of social tension arises due to intermixing of strong and weak ties, e.g. people might post relating to their friends but not intended for their family members leading to tension between the family members and user's friends when viewed by the family. Higher tension leads to lesser growth of network even though the users activity may be good enough. Some "cautious" users who care more about their regularity in the network won't be affected by high or low tension, keeping their activity always on top but since most users are not cautious, high tension will have an overall effect of reduction in the network growth rate.

Idea of creating different social spheres online is being used widely by Google+ enabling users to put any other users in different social circles of Friends, Family, Acquaintances, Following and more user created circles, whereas Facebook automatically creates several lists, namely, Close Friends, Acquaintances, Work (based on your employment listing), School (both high school and college), Family and Your city, providing the option to send a post just to a particular list. Not only this, Facebook enables the user to set extended privacy settings or, to share within secret groups.

References :

[1] De-anonymizing Social Networks by Arvind Narayanan and Vitaly Shmatikov, The University of Texas at Austin

[2] Loose Tweets: An Analysis of Privacy Leaks on Twitter, Huina Mao, Xin Shuai, Apu Kapadia, School of Informatics and Computing, Indiana University
[3] Measuring Profile Distance in Online Social Networks, Niklas Lavesson
and Henric Johnson, School of Computing, Blekinge Institute of Technology
[4] Paul Adams @ padday, vtm2010-100701010846-phpapp01
[5] The Problem of Conflicting Social Spheres: Effects of Network Structure on Experienced Tension in Social Network Sites, Jens Binder, Andrew Howes, Alistair Sutcliffe, Manchester Business School, University of Manchester
[6] http://www.socialmediaexaminer.com/five-facebook-changes-and-what-you-need-to-know/

Hierarchical structure in financial markets-Clustering stocks

INTRODUCTION

Financial markets are well-defined complex systems. The paradigm of mathematical finance

is that the time series of stock returns are unpredictable. Within this paradigm, time evolutions of

stock returns are well described by random processes. A key point is if the random processes of stock returns time series of different stocks are uncorrelated or, conversely, if economic factors are present in financial markets and are driving several stocks at the same time.

 FORMULA USED

 In the present analysis, A hierarchical structure present in a portfolio of n stocks traded in a financial market is detected using synchronous correlation coefficient of the daily difference of logarithm of closure price of stocks for all stocks present in the portfolio in a given time period. The goal is to obtain the taxonomy of a portfolio of stocks traded in a financial market by using the information of time series of stock prices only.The degree of similarity between the synchronous time evolution of a pair of stock price is determined by the correlation coefficient

where i and j are the numerical labels of stocks, Yi = ln Pi(t) − ln Pi(t − 1) and Pi(t) is the closure price of the stock i at the day t. The statistical average is a temporal average performed on all the trading days of the investigated  time period

The n x n matrix of correlation coeffcients for daily logarithm price differences is determined. The elements of matrix  can vary from −1 (completely anti-correlated pair of  stocks) to 1 (completely correlated pair of stocks). When it is 0 the two stocks are uncorrelated A metric can be determined using as distance a function of the correlation

coefficient. An appropriate function is

With this choice d(i; j) fulfills the three axioms of a metric distance { (i) d(i; j) = 0 if and only if i = j;

(ii) d(i; j) = d(j; i) and (iii) d(i; j) <= d(i; k) + d(k; j)}.

The distance matrix D is then used to determine the minimal spanning tree connecting the n stocks of the portfolio. The method of constructing a MST linking a set of n objects is direct The MST of a set of n elements is a graph with n − 1 links. Using this matrix D, MST can be constructed using  any of the minimum spanning tree algorithm.

INFERENCE 

a)DOW JONES

 Minimal spanning tree associated with the distance matrix D is of great interest from an economic point of view . The more evident and strongly connected group is the group of stocks CHV, TX and XON namely Chevron, Texaco and Exxon. These three companies are working in the same industry (energy) and in the same subindustry (international oils). AA and IP, namely Alcoa (working in the subindustry sector of nonferrous metals) and International Paper (working in the subindustry sector of paper and lumber) form a second group. Both companies provide raw materials. The third group involves companies which are in industry sectors which deals with consumer nondurables (Procter & Gamble, PG) and food drink and tobacco (Coca Cola, KO).

b)S&P 500

Fig. 3. Main structure of the hierarchical tree of the portfolio of stocks used to compute the S&P 500 index. Groups are labeled with integers ranging from 1 to 44.1. Metals (nonferrous metals, gold); 2. Construction (residentialbuilders); 3. No common industry sector; 4. Travel and transport (trucking and shipping); 5. Consumer nondurables (photography and toys); 6. No common industry sector; 7. Metals (steel); 8. Consumer durables (automotive parts); 9. Travel and transport (airlines); 10. Entertainment and information (broadcasting and cable); 11. Financial services (lease and finance); 12. Energy (oil_eld services); 13. Energy (international

oils); 14. No common industry sector. 15. Capital goods (heavy equipment); 16. Business services and supplies (environmental and waste); 17. Construction (commercial builders); 18. Consumer durables (automobiles and trucks); 19. Food drink and tobacco (tobacco); 20. Entertainment and information (publishing); 21. Forest products and packaging (paper and lumber); 22. Metals (nonferrous materials); 23. Metals (nonferrous materials); 24. Metals (nonferrous materials); 25. Computer and communications (peripherals & equipment or software);26. Electric utilities (regional area); 27. Computer and communications (telecommunications); 28. Retailing (department stores and drug & discount); 29. no common industry sector; 30. Travel and transport (railroads); 31. Food drink and tobacco (food processors); 32. no common industry sector; 33. Insurance (property & casualty and diversi_ed); 34. Health(drugs); 35. Health (drugs); 36. Consumer nondurables (personal products); 37. Food drink and tobacco (beverages); 38.Retailing (no common subindustry sector (SS)); 39. Capital goods (electrical equipment); 40. Financial services (no common SS); 41. Financial services (thrift institutions); 42. Financial services (multinational banks); 43. Financial services (regional banks); 44. Financial services (multinational banks).

 The same investigation is repeated for the set of stocks used to compute the S&P 500 index as shown in fig 2. A group of financial services, capital goods, retailing, food drink & tobacco and consumer nondurables companies is observed in this strongly connected group of stocks.. A detailed inspection of the hierarchical tree associated to the MST provides a large amount of economic information.With only a few exceptions the groups are homogeneous with respect to industry and often also subindustry sectors suggesting that set of stocks working in the same industry and subindustry sectors respond, in a statistical way, to the same economic factors. For example, ores, aluminum and copper are all classified metals as industry and nonferrous metals as subindustry. From the  analysis, it is detected  that they respond to quite different economic factors. Specifically, ores companies are grouped in a cluster, which is the most distant from all the others groups of stocks of the tree, while aluminum and copper companies constitute a subgroup of the group containing raw materials companies.The detection of a hierarchical structure in a broad portfolio of stocks traded in a financial market is consistent with the assumption that the time series of returns of a stock is affected by a number of economic factors . In general, stocks or groups of stocks departing early from the tree (at high values of the distance d<(i; j)) are mainly controlled by economic factors which are specific to the considered group (for example gold price for the stocks of the group 1 of the tree (see Fig. 3) which is composed only by companies involved in gold mining). When departure occurs for (moderately) low values of d<, the stocks are affected  either by economic factors which are common to all stocks  and by other economic factors which are specific to the considered set of stocks. 

  
 The detected hierarchical structure might be  useful in the detection of financial markets and in the search of economic factors affecting specific groups of stocks. The taxonomy associated with the obtained hierarchical structure is obtained by using information present in the time series of stock prices only. This result shows time series of stock prices are carrying valuable (and detectable) economic information.

REFERENCES:

[1] R. N. Mantegna, “Hierarchical structure in financial markets,” Euro.

Phys. J. B, vol. 11, pp. 193–197, 1999.

[2]Detecting Stock Market Fluctuation from Stock Network Structure Variation

     Jing Liu, Chi K. Tse and Keqing He

[3] S.A. Ross, J. Econ. Theo. 13, 341 (1976).

[4] B.B. Mandelbrot, J. Business 36, 394 (1963).

[5] L.P. Kadano , Simulation 16, 261 (1971).

[6] R.N. Mantegna, Physica A 179, 232 (1991).

The game of go as a complex network

Board games are one of the oldest activities of humankind and have been played for millenniums. Besides their inherent interest, they represent a privileged approach to the working of decision-making in the human brain. Some of the board games are very difficult to model or simulate: only recently were computer programs able to beat world chess champions. The old Asian game of go is even less tractable. The game complexity, that is, the total number of legal positions, is about 10171, compared to a mere 1050 for chess ^[2]. It remains an open challenge for computer scientists: while Deep Blue famously beat the world chess champion Kasparov in 1997, no computer program has beaten a very good player even in recent times.

The game of go is played by two players (Black and White) on a board consisting of 19 horizontal and 19 vertical lines. The players alternately place a stone of their own color at an empty intersection on the board. Stones entirely surrounded by the opponent must be removed, and the aim of the game is to delimit large territories. As the game unfolds, local and global properties of stones are involved. A network approach will obviously not be able to capture all features of the game, as the number of possible moves is far too large. Here we follow an approach where only local features are retained. This approach is reminiscent of the one used in the context of language networks ^[3].

 A move consists in placing a stone at an empty intersection (h, v) with 1 <= h, v <= 19. We call ”plaquette” a square of 3 × 3 intersections, that is, a subset of the board of the form {(h + r, v + s),−1 <= r, s <= 1} (to account for edges and corners of the board one can imagine that there are two additional dummy lines at each side of the board). To define our network we only take into account intersections closest to (h, v). Vertices correspond to the different kinds of plaquettes in which a player can put a stone, irrespective of where it has been played on the board. Since each of the 8 neighboring intersections can be either empty, black or white, there are approximately 3⁸ different plaquettes. We choose to consider identical plaquettes that transform to each other under any symmetry of the square (rotation or flip). We also identify patterns with color swapped. That is, a move where Black plays in a given plaquette is considered the same as a move where White plays in the same plaquette with colors swapped. An exact computation taking into account borders and symmetries leaves us with 1107 nonequivalent plaquettes with empty centers, which are the vertices of our network. We note that certain computer programs based on knowledge from real professional games also consider similar 3 × 3 stone patterns ^{[4, 5]}. Considering larger plaquettes is possible and would convey more relevant information; however, the number of vertices then becomes enormously large (approximately 3.1010 for 5 × 5 plaquettes).

This definition of inequivalent moves enables us to investigate the first properties of the databases in term of frequencies of moves. Zipf’s law is an empirical characteristics which has been observed in many natural distributions, such as e. g. word frequency in the English language ^[6], city sizes ^[7], and income distribution of companies ^[8], and chess openings ^[9]. If items are ranked according to their frequency, it predicts a power-law decay of the frequency as a function of the rank. Zipf’s law was observed in the frequency distribution of 5×5 go patterns ^[10]. 

(Color online) Normalized integrated frequency distribution of moves F(n) for Honinbo (black), Meijin (red), Judan (green), Kisei (blue) and amateur (violet) tournaments. The normalized number of occurrences of the 500 most frequent moves (among the 1107 moves described in the text) is shown vs. the ranks of the moves (rankings slightly depend on the database). Slopes are, respectively, −1.058, −1.056, −1.065, −1.067, −1.081. The thick dashed line is y = −x. Inset: the same with moves defined as the position of the stone on the board. Log is decimal.

In above figure[1] we display the integrated frequency distribution for our 1107 moves labeled from the most to the least frequent. The integrated distribution of moves is very similar for all databases and clearly follows a Zipf’s law, with an exponent approximately equivalent to 1.06. In contrast, such a law cannot be seen if one simply takes the 361 possible positions (h, v) as vertices, disregarding local features (inset of Fig. 1). Thus Zipf’s law appears when tactical information is taken into account. For all databases the 10 most frequent moves are the same, but sometimes in a slightly different order.

References :

[1] Georgeot (Universit´e de Toulouse; UPS; Laboratoire de Physique Th´eorique (IRSAMC); F-31062 Toulouse, France and CNRS; LPT (IRSAMC); F-31062 Toulouse, France)  and O. Giraud (Univ. Paris-Sud, CNRS, LPTMS, UMR 8626, Orsay, F-91405, France)

[2] Tromp J. and Farneb¨ack G., Combinatorics of Go, Proc. of the 5th Int. Conf. on Computer and Games, edited by      Van den Herik H. J., Ciancarini P. and Donkers H. H. L. M. Lect. Notes in Comp. Sciences, 4630 (2007) 72 (Springer-Verlag, Heidelberg, Germany)

[3] Ferrer-i-Cancho R. and Sole R. V., Proc. Royal Soc. Lond. B, 268 (2001) 2261; Dorogovtsev S. N. and

Mendes J. F. F., Proc. Royal Soc. Lond. B, 268 (2001) 2603; Masucci A. P. and Rodgers G. J., Phys. Rev. E,

74 (2006) 026102

[4] Coulom R., ICGA Journal, 30 (2007) 199

[5] Huang S.-C., Coulom R. and Lin S.-S., Lect. Notes in Comp. Science, 6515 (2011) 81

[6] Zipf G. K., The Psycho-Biology of Language (Houghton Mifflin, Boston) 1935

[7] Gabaix X., Quart. Jour. of Econ., 114 (1999) 739

[8] Okuyama K., Takayasu M. and Takayasu H., Physica A, 269 (1999) 125

[9] Blasius B. and T¨onjes R., Phys. Rev. Lett., 103 (2009) 218701

[10] Liu Z., Dou Q. and Lu B., Lecture Notes in Computer Science, 5131 (2008) 125

Complex brain networks

Complex brain networks

Graph theoretical analysis of structural and functional systems

Recent developments in the quantitative analysis of complex networks, based largely on graph theory, have been rapidly translated to studies of brain network organization. The brain’s structural and functional systems have features of complex networks — such as small-world topology, highly connected hubs and modularity — both at the whole-brain scale of human neuroimaging and at a cellular scale in non-human animals. In this article, we review studies investigating complex brain networks in diverse experimental modalities. We also highlight some of the technical challenges and key questions to be addressed by future developments in this rapidly moving field.

Structural and functional brain networks can be explored using graph theory through the following four steps (see the figure):

• Define the network nodes. These could be defined as electroencephalography or multielectrode array electrodes, or as anatomically defined regions of histological, MRI or diffusion tensor imaging data.

• Estimate a continuous measure of association between nodes. This could be the spectral coherence or Granger causality measures between two magnetoencephalography sensors, or the connection probability between two regions of an individual diffusion tensor imaging data set, or the inter-regional correlations in cortical thickness or volume MRI measurements estimated in groups of subjects.

• Generate an association matrix by compiling all pairwise associations between nodes and (usually) apply a threshold to each element of this matrix to produce a binary adjacency matrix or undirected graph.

• Calculate the network parameters of interest in this graphical model of a brain network and compare them to the equivalent parameters of a population of random networks.

Figure 2 | cellular and whole-brain networks demonstrate consistent topological features. The top panel shows a cellular functional network constructed from multielectrode- array recordings made in the anaesthetized cat; each node (represented by a circle) corresponds approximately to one neuron and the connections represent high functional connectivity between neurons. The different coloured nodes constitute separate clusters or modules. The plots in each circle illustrate cellular responses to stimuli of different orientations, and the circle size corresponds to the degree (number of functional connections) of each node. The bottom panel shows a whole-brain structural network constructed from histological data on the macaque cortex; each node corresponds to a brain area and the connections represent axonal projections between areas. The network has two main modules, shown here with yellow and grey circles corresponding to mostly dorsal and ventral visual regions, respectively. Both networks exhibit the small-world attributes of high clustering and short path length; both have an exponentially truncated power law degree distribution, associated with the existence of high-degree ‘hubs’ (V4 in the anatomical network); and both have a community structure characterized by sparse connectivity between modules (each module is enclosed by stippled lines) and linked by hubs (nodes circled in red). AITv, anterior inferotemporal ventral area; CITd, central inferotemporal dorsal area; CITv, central inferotemporal ventral area; DP, dorsal preluneate area; FEF, frontal eye field; FST, floor of superior temporal area; LIP, lateral intraparietal area; MT, middle temporal area; PIP, posterior intraparietal area; PITd, posterior inferotemporal dorsal area; PITv, posterior inferotemporal ventral area; PO, parieto-occipital area; TF, area TF; TH, area TH ;V1–4, visual cortical areas 1–4; VIP, ventral intraparietal area; VOT, ventral

occipitotemporal area; VP, ventral posterior area.

Figure 3 | Disease-related disorganization of brain anatomical networks derived from structural Mri data. In both parts, the nodes (circles) represent cortical regions and the connections represent high correlation in grey matter density between nodes. The nodes are arranged vertically by degree and are separated horizontally for clarity of representation. The numbers indicate approximate Brodmann area, and the prime symbols (Œ) denote left-sided regions. The clustering coefficient of each node, a measure of its local connectivity, is indicated by its size: nodes with high clustering are larger. 

a | The brain anatomical network of the healthy volunteers has a hierarchical organization characterized by low clustering of high-degree nodes. 

b | The equivalent network constructed from MRI data on people with schizophrenia shows loss of this hierarchical organization . high-degree nodes are more often highly clustered.

Conclusions: 

It is clear that certain aspects of the organization of complex brain networks are highly conserved over different scales and types of measurement, across different species and for functional and anatomical networks. The archetypal brain network has a short path length (associated with high global efficiency of information transfer), high clustering (associated with robustness to random error), a degree distribution compatible with the existence of hubs, and a modular community structure. Furthermore, anatomical networks are sparsely connected, especially between nodes in different modules, and the ‘wiring length’ (the physical distance that connections span) is close to minimal. This profile of topological and geometric properties is typical not just of brain networks but also of many other complex networks, including transport

systems and intracellular signalling pathways.

References

• Hagmann, P. et al. Mapping the structural core of human cerebral cortex. PLoS Biol. 6, e159 (2008). This paper demonstrated the existence of modules, hubs and a structural core in the human anatomical network derived from DTI.
• Achard, S., Salvador, R., Whitcher, B., Suckling, J. & Bullmore, E. T. A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs.J.  eurosci. 26, 63–72 (2006).
• Yu, S., Huang, D., Singer, W. & Nikolic, D. A small world of neuronal synchrony. Cereb. Cortex 18, 2891–2901 (2008). This paper was one of the first to apply graph theoretical techniques to  map the topology of functionally characterized cortical neuronal circuits.
• Sporns, O. & Kötter, R. Motifs in brain networks. PLoS Biol. 2, 1910–1918 (2004).
• Bassett, D. S. et al. Hierarchical organization ofhuman cortical networks in health and schizophrenia. J. Neurosci. 28, 9239–9248 (2008).

Complex Network Application in Music: Uncovering Universal Properties in Favourable Human Perception of Music

Introduction:
Across cultures and between individuals ,certain musical pieces are consistently rated more favorably than the others and a mathematical analysis of musical perception has a long history. But recently,a data-driven transformation to represent a musical score as a complex network has been tried by network scientist. What has been found is that those musical scores which are widely perceived to be 'good' generate complex network with certain invariant properties: scale-free networks with strong clustering of nodes within the network.They have also tried to generate random musical compositions from these networks and surprisingly found that scores generated in this manner are also perceived to be 'good' and are qualitatively similar to the specific score from which the generating network was produced.

Section of Mozart's Sonata


The network generated from entire Mozart's Sonata
Building the Network:
A musical score , or even the performance of a particular musician can be represented as a MIDI(musical instrument digital interface) file. The MIDI file encodes a musical composition as a series of events ,where each event includes information describing both the pitch and timing of a note.If a MIDI file is transcribed from a musical score, this information will be precise; if the information is derived from an actual performance there will be more variability. The network is then constructed the following way: Each MIDI event (a single musical note) corresponds to a node in the complex network. Two nodes in the network are linked by an edge if they succeed one another in the musical score. Weight is ascribed to a given edge based on the relative frequency with which the two nodes are adjacent. Direction is based on temporal order.
                               
             This transformation was applied to a wide variety of musical composition including the sonatas of Bach and Mozart, Bach's "Well-Tempered Clavier", Chopin's waltzes, Russian folk music and Cantonese pop. In all cases the networks generated by this algorithm exhibit a scale-free distribution (using the maximum likelihood procedure at the 95% confidence interval) on the node degree (that is, the probability of a node having degree k, p(k) = k-gamma ) with degree exponent gamma falling in a narrow range 1 < gamma < 1.7. As a natural consequence of variability in a human performance it was observed that for MIDI files derived from actual rendition, the clustering within the network was much lower (clustering coefficient 0.127 +/- 0.069) in comparison to MIDI derived from musical score (0.37 +/- 0.056). Nonetheless, in all cases the scale exponent falls within a fairly narrow range. Notably, the scale exponents for Russian folk music (1.18) and Cantonese pop (1.01) are significantly lower than those derived from classical music (1.29 ~ 1.67).

Figure on the right: Degree distribution for the same Mozart's sonata network (number of links k versus frequency p(k).








Discussions:
These complex networks therefore encapsulate some features of the underlying musical scores used to generate them. These networks were then used to generate new artificial scores.  A random initial node on the network was chosen and randomly followed one of the links from that node to another based on the relative weight of the links. This procedure was repeated and the sequence of nodes that were traversed were recorded. The corresponding notes (both pitch and duration) gave a random score. If one was to then generate a new network from that score it would (asymptotically) be equivalent to the original. The surprising and intriguing consequence of this procedure was that the random scores were both pleasing and qualitatively similar to the original score. That is, random scores generated from the network derived from Chopin's sonatas also sound like Chopin, those derived from the Cantonese pop network also sound like Cantopop . Of course, these scores lacks the large scale structure of the original . But, this does demonstrate that the complex network encapsulates enough information to quantify basic features of a particular composition or style. As with actual composition, large scale structure can be imposed aposteriori and selection from between many candidate random scores can be used to produce "optimal" compositions.

References:

1. X. Liu, C.K. Tse and M. Small, "Composing music with complex networks," International Conference on Complex Sciences: Theory and Applications, (COMPLEX2009), Shanghai, pp. 2196-2205, February 2009.
2. X. Liu, C.K. Tse and M. Small, "Complex network structure of musical compositions: Algorithmic generation of appealing music," Physica A, vol. 389, no. 1, pp. 126-132, January 2010.