Time Constrained Networks

One of the key features of complex networks is that they capture interactions which have no limitations.  In most electronic systems, be they Facebook, emails or web pages, we can make connections across the world with little if any cost.
However what if there are constraints on the links made in a network? Surely we should change the way we study networks if space, time or some other constraint is having a significant effect on the formation or use of the network.  This has been a major interest of researchers over the last few years. Space is one obvious limitation as in some cases long distance are less likely to be made. There has been a lot of work in this area over many decades.
It is only more recently that the role of time in networks has began to receive more attention. A lot of this recent interest in how to deal with networks where the connections, are made at one time.  That is because most communication networks, emails, phone calls and so forth, are of this type.
Yet networks are made of two parts: vertices and edges. The recent work is focussed on the case where it is the vertices, not the edges, which are created at a definite time. In such temporal vertex networks, causality forces the interactions between nodes to always point in one direction. For example consider a citation network formed by academic papers. The nodes in our network are the academic papers and the links are formed by their bibliographies.  So if paper A refers to another paper B then we can be (almost) sure that A was written after B. Information can therefore flow only from B to A. In fact any set of documents can only refer to older ones such networks are common. In law, judges refer to previous judgments to support their arguments.  When registering a patent, prior art needs to be cited, that is other previously granted work which may have some relevance to the current claim.
The same types of structure occur in several other situations.  Any situation where there is a logical flow has the same causal structure.  If we have a project where the nodes represent individual tasks then an edge from task S to task T could represent the fact that task T requires task S to have been completed before task T is started.  This has been the focus of work on temporal vertex networks in computer science. The logical flow of a mathematical argument or an excel spreadsheet show the same properties.  These networks define what is called a partially ordered set or poset and it is under this title that one finds relevant work coming from mathematicians. A final example comes from the Causal Sets approach to quantum gravity.  Here space-time is discrete not continuous, and these discrete points are the nodes of the network.  The nodes are connected by edges only if they are causally connected and causality again gives these a common direction.
All of these temporal vertex networks have a key property.  That is they contain no loops if you always follow the direction on the edges.  You can not go backwards in time. Thus the traditional name for such a network is a directed acyclic networks or DAG for short.
So the question is how can we adapt traditional network measures to deal with the fact that these networks, DAGs, are constrained by causality?  Are there new measures we should employ which give more insights to such networks?
One feature of a DAG we have been exploiting is that if we always follow the direction of the arrows, the direction of time, then not all nodes are connected. If we like we could add edges whenever there is such a path connected a late node to an earlier one, a process known as transitive completion.  On the other hand we could remove as many edges as we can while leaving the causal relationships intact, a process known as transitive reduction. That is, if there is a path between two nodes in the network before transitive reduction, then there will still be a link afterwards.

Example of the transitive reduction (left) and the transitive completion (right) of the directed acyclic graph in the centre.

What we have done (in Transitive Reduction of Citation Networks) is look at how real data from citation networks behaves after transitive reduction.  We find that different types of citation network behave very differently. The citation network formed from academic papers taken from the arXiv repository and the network of US Supreme Court judgments both show that about 80% of the edges are not needed to retain all the causal relationships.  On the other hand the patents network shows the opposite behaviour with all but 15% of edges being essential. The edges removed tend to be the citation to older papers. One interpretation is that academics and and judges may be citing well known early papers and judgments though their current work is only directly related to more recent documents. Perhaps some of these citations do not indicate the early work was needed but reflect other motivations, such as simple copying of popular papers or review in the field which at best only have general relevance.
The number of citations to a document after transitive reduction certainly gives us a different view of the importance of different documents. For instance paper hep-th/9802109 on the arXiv (Gauge Theory Correlators from Non-Critical String Theory by Gubsner et al.) was cited by 1641 papers in the network, but only three citations remained after TR! On the other hand, paper hep-th/9905111 (Large N Field Theories, String Theory and Gravity by Aharony et al.) has also large number of citations in the raw data, 806, yet after transitive reduction it has 77, so retaining far more of its original citations. Perhaps information in the second paper was used more diversely.
We can find similar examples in the US Supreme Court citation network. The case Schneider vs. New Jersey (1939)’ has 144 citations in the original data but this drops to just just one after transitive reduction. Stromberg vs. California (1931) also falls from 132 citations to just one. Conversely, the case Heller vs. New York (1973) only shows a slight fall after transitive reduction, falling from from 68 to 48 citations and has the most citations in our reduced network. The second most cited case after transitive reduction is Hamling vs. United States, which drops from 68 to 38 citations. Wikipedia lists hundreds of Supreme Court cases but the last two are not famous enough to make the Wikipedia list. The analysis suggests they may have more importance than a simple citation count would suggest. At the very least it might be be worth checking out documents that are highly cited in the essential.
Another way to look at citation networks is to see if we can define a dimension to the network.  That is we can try to quantify how much variation there is in the citation process.  A low dimension means that there are few directions , few distinct themes relevant for citation in a document.  A high dimension indicates that there is a wide range of relevant but distinct directions from which a document will draw on for inspiration.  We were often able to assign an interesting value for the dimension of our citation data.  For academic papers, we found that different fields of research have different dimensions.  For papers in the hep-th arXiv section (largely string theory) we generally find a low dimension of around 2 while for theoretical papers closely linked to particle physics experiments we find more variation as indicated by a higher dimension of 3. The quant-ph also around 3 while the astro-ph section had a slightly higher dimension of around 3.5. So clearly despite similarities in the main data using standard measures, our time-aware dimension measures show clear differences in the citation behaviour of different areas. String theory in particular seems to be a tightly knit collection of work with each work largely dependent on all the other work, few independent directions can be pursued. The US Supreme Court judgments were more complicated.  Small samples (usually from modern judgments) showed a dimension of around 2.5 to 3 but larger samples, typically ranging from modern to the earliest judgments, had lower dimensions, closer to 2. We interpreted this as reflecting the way that there were few early judgments compared to the number produced to day.  So that the further back we traced in time to find the influence of judgments on recent ones, the smaller the variation.  Perhaps that is not so surprising and we might expect a similar shape if we could follow scientific papers back to the 18th century! patents on the other hand showed a much higher dimension though again these were involved.
It is clear from just the few studies we have made that time makes a crucial difference to the structure of a network. There is surely much more to find when networks are embedded in time.

References:

Clough, J.R. & Evans, T.S. What is the dimension of citation space?, arXiv:1408.1274

Clough, J. R.; Gollings, J.; Loach, T. V. & Evans, T. S., Transitive Reduction of Citation Networks, J.Complex 

Dowker, F. Causal sets as discrete spacetime, 2006. Contemporary Physics, 47, 1-9

Holme, P. & Saramäki, J. 2012. Temporal Networks Physics Reports, 519, 97-125

Simkin M.V. and Roychowdhury V.P., 2003. Read before you cite! Complex Systems 14 269-274

Social and temporal properties of Apps

Apps are important part of everyone’s lives. They exhibit a rich temporal structure of user adoption and long-term engagement. Also social ecosystem helps in driving the adoption and engagement of apps.

In the first part we will discuss the social properties of apps and how user’s probability of adopting an app depends both on properties of the local network structure and on the match between the user’s attributes, his or her friends’ attributes, and the dominant attributes within the app’s user population. In the second part we will develop a retention model that represents a user’s tendency to return to an app.

We would like to place apps in a low-dimensional space that can provide a view for how they are distributed across the social network of users. To do this, we begin with two basic definitions

•  We say that the popularity of an app, denoted p(x), is the probability that an individual selected uniformly at random from Facebook’s population is a user of the app.
• We say that the sociality of the app, denoted p(x|y), is the probability that a member of Facebook is a user of the app given that they have at least one friend using the app.

Studying the distributions of p(x) and p(x|y), and how they are jointly distributed across apps, allows us to ask a number of questions. In particular, how socially clustered is the app? And how does it depend on the type of app, or characteristics of the app’s users?

Moreover, p(x|y) can in principle be high even when p(x) is low -- this would correspond to an app that is popular in a focused set of friendship circles, but not on Facebook more broadly. On the other hand, if p(x|y) is not much more than p(x), then it says that users of the app are spread out through the social network almost as though each member of Facebook independently flipped a coin of bias p(x) in order to decide whether to become a user of the app -- there would be no effect of the social network at all.

Figure 1: App sociality. Top left: Horizontal axis is app popularity, and vertical axis is the relative increase in adoption likelihood for people who have friends who also use the app. Right panels: Horizontal axis is app popularity, vertical axis is app sociality. The colors represent the number of apps falling within the given bin. The labeled colors indicate the relative frequencies of observations in each bin, such that the lowest values have been normalized to 1.

We see in Figure 1 that the apps fill out a wedge-shaped region in the p(x)-p(x|y) plane.  If the social network had no relationship to app usage, we would see the diagonally sloping line p(x) = p(x|y); in the plot this corresponds to a line that lies slightly below the diagonal lower boundary of the points in the heat map. Thus, there exists a frontier in the space of apps that is almost completely asocial — those apps that lie parallel to this diagonal line — but essentially no apps actually reach the line; even the most asocial apps exhibit some social clustering. We see this in the approximately horizontal top boundary of the points in the heat map — this is a frontier in the space of apps where knowing that a person x has a friend using the app gives you a fixed probability that x uses it, independent of the app’s overall popularity on Facebook. The wedge-shaped region in a sense has to come to a point on the right-hand side, as p(x) becomes very large: once an app is extremely popular, there is no way to avoid having pairs of friends using it almost by sheer force of numbers. And given the crowding of app users into the network, there is also no way for the extent of social clustering to become significantly larger than one would see by chance.

For each app, we consider everyone on Facebook who has friends using the app, but who has not used the app themselves by time t.

Figure 2: Relationship between national identity of potential app adopters, that of their current user friends, and the likelihood of their adopting the app. Blue: Relative adoption rates when a potential user and their current user friend are from the majority to when potential user is in majority and current user friend is in minority. Green: Relative rates when potential user and current user friend are in same minority to when potential user is in minority and current user friend is in majority. Red: Relative rates for when potential user and current user friend are in same minority to when they are in different minorities. The blue curve indicates that when a potential user is from the majority country, their current user friend could be from either the majority or a minority and they are still equally likely to adopt an app more often as less. In contrast, when the potential user is from a minority country, in 75% of apps they adopt more frequently when their current user friend is from the same country as them.

Consider a Facebook user A who does not currently use the app, and suppose that has exactly one friend B who uses the app (that is, A has between 1 and 5000 friends on Facebook, but for our purposes here, exactly one of those friends is an app user). We choose some attribute on users (for example nationality, or age); we let f(A) and f(B) denote the value of this attribute for A and B, and we let f* denote the modal (or median) value of the attribute across all app users.

Suppose that A is different from the typical user in this attribute, in the sense that f(A) not equal to f*. Is A more likely to adopt the app if the friend B is similar to A, or if B is similar to the typical app user? We now say that a(i, j) is the adoption probability of a user A who has one friend B using the app, with f(A) = i and f(B) = j. (Note that f* = 0 according to our notation, since 0 is the most prevalent nationality in the app.) a(i, i)/a(i, 0) > 1, indicating a clear aggregate tendency for the question in the previous paragraph: a user A is more likely to adopt the app in general when A’s one friend using the app is similar to A, not to the typical app user. In contrast, when f(A) = f* , the ratio a(0, 0)/a(0, i) is balanced around 1, so there is no clear tendency in adoption probabilities between the case f(B) = f* and f(B) not equal to f* : for users who have the modal attribute value, the attribute value of their friend does not have a comparably strong effect.

Figure 3: The probability that a user adopts the app given that they have one friend using the app. as a function of (left) the friend’s age offset from the median and (right) the user’s age offset from the median. The left plot indicates no apparent relationship between the age of the friend and that the user adopts. In contrast, the right plot illustrates that young users and users who are aged between 10 and 30 years above the median age are more likely to adopt. Users who are more than 40 years older than the median age are less likely to adopt. The probabilities were binned by age into 20 equally populated bins and the reported adoption probabilities are bootstrap estimates. The thick central line is the median bootstrap estimate of the mean, while the three outer bands indicate the 68%, 95%, and 99.7% confidence-intervals.

For an app to have long term success we expect that it needs to maintain a relatively high level of user retention. We would like to have a model of retention that characterizes not only whether an individual will log into the app the very next day, but for any day subsequent to their first login.

We start with the population of newly installed users, n(0), and assume that at every time step each user has a constant probability of leaving, x₀. This mechanism gives rise to exponential decay:

dn(t)/dt = - x₀n(t) → n(t) = n(0) exp(−x₀ t),

where n(t) is the number of app users at time t. It turns out that this model does not yield a good fit to the data. However, the fit improves if we introduce a second parameter to the model by fitting from the second day; that is, we fit both for the decay rate, x₀ , and the fraction of users that returned on day 2. With this relaxation from fitting day 1, the model becomes

n(t) = An(0) exp(−x₀ t).

It is interesting that the exponential decay model fits the day 2 and onward trend well while not fitting day 1: it is reasonable to expect that there is a discontinuous transition in the probability of returning given an install versus an install and a return the following day. Day 1 users are dominated by those who use the app exactly once, whereas all the other days contain a signal from users who exhibited at least some level of continued interest in the app

There are a number of further aspects of the app ecosystem that would be interesting to take into account in future work. First, app adoption is driven in part by the marketing and other recruitment strategies of the app owners. Although our models incorporate the numbers of new users coming to the app over time, they do not differentiate between organic growth and advertising-driven growth. Furthermore, it is not clear whether sociality of apps might accelerate growth or decline or both. Finally, it is unclear whether some features might be early harbingers of future behavior, e.g. whether the change in retention of long-time or recently acquired users is more useful in forecasting the eventual adoption of the app.

References:

http://arxiv.org/abs/1503.06870 : The Lifecycles of Apps in a Social Ecosystem – [ Isabel Kloumann, Lada Adamic, Jon Kleinberg, Shaomei Wu]

Food and Complex Networks !

In this post we talk about Food network, “Food Pairing Hypothesis” and variants and invariants in food ingredient usage across different cuisine and in different times. Ingredient-flavor networks are bipartite networks describing the association of flavor compounds of food ingredients. This undirected graph consists of two different types of nodes: the ingredients used in the recipes and the flavor compounds that contributes to the flavor of each ingredients.

In the first part we will discuss whether there  are any general patterns that determine the ingredient combinations used in food today or principles that transcend individual tastes and recipes. In 2011, Yong-Yeol Ahn, Sebastian E. Ahnert, James P. Bagrow and Albert-László Barabási investigated the ingredient-flavor networks of North American, Latin American, Western European, Southern European and East Asian cuisines. Based on culinary repository epicurious.com,allrecipes.com and menupan.com, 56,498 recipes has been included in the survey. According to Ahn, in the total number of 56,498 recipes studied, 381 ingredients and 1021 flavor compounds were identified. Averagely each ingredients connect to 51 flavor compounds. It was found that in comparison with random pairing of ingredients and flavor compounds, North American cuisines tend to share more compounds while East Asian cuisines tend to share fewer compounds. It was also showed that this tendency was mostly generated by the frequently used ingredients in each cuisines.

Although many factors such as colors, texture, temperature, and sound play an important  role in food sensation palatability is largely determined by flavor, representing a group of sensations including odors , tastes, and freshness or pungency - all these are mainly due to the internal chemical compounds making them a natural starting point for a systematic search for principles that might underlie our choice of acceptable ingredient combinations.

Let us first describe the “Food Pairing Hypothesis” - A hypothesis, which over the past decade has received attention among some chefs and food scientists, states that ingredients sharing flavor compounds are more likely to taste well together than ingredients that do not. Here they have introduced a network-based approach to explore the impact of flavor compounds on ingredient combinations. Analyzing the data the authors built a bipartite network consisting of two different types of nodes: (i) 381 ingredients used in recipes throughout the world, and (ii) 1,021 flavor compounds that are known to contribute to the flavor of each of these ingredients. A projection of this bipartite network is the flavor network in which two nodes (ingredients) are connected if they share at least one flavor compound.

Following is the Ingredient - flavour network.

After taking the projection we have found the flavour flavour network

Following is The distribution of recipe size, capturing the number of ingredients per recipe, across the five cuisines explored in our study.

The following is the frequency-rank plot of ingredients across the five cuisines show an approximately invariant distribution

The previous image was an approximate visualization of the network, as the actual network has many nodes here we have clustered them for better visualization. Each node denotes an ingredient, the node color indicates food category, and node size reflects the ingredient prevalence in recipes. Two ingredients are connected if they share a significant number of flavor compounds, link thickness representing the number of shared compounds between the two ingredients.

This allows to model the food pairing hypothesis as a topological property: do we more frequently use ingredient pairs that are strongly linked in the flavor network or do we avoid them? The next figure (part D) indicates that North American and Western European cuisines exhibit a statistically significant tendency towards recipes whose ingredients share flavor compounds. By contrast, East Asian and Southern European cuisines avoid recipes whose ingredients share flavor compounds (see Figure D for the Z-score, capturing the statistical significance of ΔNs).

The systematic difference between the East Asian and the North American recipes is particularly clear if we inspect the P(Nrands) distribution of the randomized recipe dataset, compared to the observed number of shared compounds characterizing the two cuisines, Ns. This distribution reveals that North American dishes use far more compound-sharing pairs than expected by chance (Fig.E), and the East Asian dishes far fewer (Fig.F). Finally, we generalize the food pairing hypothesis by exploring if ingredient pairs sharing more compounds are more likely to be used in specific cuisines.

Schematic illustration of two ingredient pairs, the first sharing many more (A) and the second much fewer (B) compounds than expected if the flavor compounds were distributed randomly. (C,D) To test the validity of the food pairing hypothesis, we construct 10,000 random recipes and calculate ΔNs. We find that ingredient pairs in North American cuisines tend to share more compounds while East Asian cuisines tend to share fewer compounds than expected in a random recipe dataset. (E,F) The distributions P(Ns) for 10,000 randomized recipe datasets compared with the real values for East Asian and North American cuisine. Both cuisines exhibit significant p-values, as estimated using a z-test. (G,H) We enumerate every possible ingredient pair in each cuisine and show the fraction of pairs in recipes as a function of the number of shared compounds. To reduce noise, we only used data points calculated from more than 5 pairs. The p-values are calculated using a t-test. North American cuisine is biased towards pairs with more shared compounds while East Asian shows the opposite trend (see SI for details and results for other cuisines). Note that we used the full network, not the backbone shown in Fig. 2 to obtain these results. (I,J) The contribution and frequency of use for each ingredient in North American and East Asian cuisine. The size of the circles represents the relative prevalence . North American and East Asian cuisine shows the opposite trends. (K,L) If we remove the highly contributing ingredients sequentially (from the largest contribution in North American cuisine and from the smallest contribution in East Asian cuisine), the shared compounds effect quickly vanishes when we removed five (East Asian) to fifteen (North American) ingredients. C through H imply that all the recipes aim to pair ingredients together that share (North America) or do not share (East Asia) flavor compounds, or could we identify some compounds responsible for the bulk of the observed effect? We therefore measured the contribution χi (see Methods) of each ingredient to the shared compound effect in a given cuisine c, quantifying to what degree its presence affects the magnitude of ΔNs.

Here we discuss a little about the “Flavour Principle” - According to an empirical view known as “the flavor principle”  the differences between regional cuisines can be reduced to a few key ingredients with specific flavors: adding soy sauce to a dish almost automatically gives it an oriental taste because Asians use soy sauce widely in their food and other ethnic groups do not; by contrast paprika, onion, and lard is a signature of Hungarian cuisine.

In the next figure we organize the six most authentic single ingredients, ingredient pairs and triplets for North American and East Asian cuisines in a flavor pyramid.

Here (A,B) Flavor pyramids for North American and East Asian cuisines. Each flavor pyramid shows the six most authentic ingredients (i.e. those with the largest ), ingredient pairs (largest ), and ingredient triplets (largest ). The size of the nodes reflects the abundance of the ingredient in the recipes of the particular cuisine. Each color represents the category of the ingredient and link thickness indicates the number of shared compounds. (C) The six most authentic ingredients and ingredient pairs used in specific regional cuisine. Node color represents cuisine and the link weight reflects the relative prevalence     of the ingredient pair.

In another work we study the statistics of ingredients and recipes taken from Brazilian, British, French and Medieval cookery books. We find universal distributions with scale invariant behaviour. We propose a copy-mutate process to model culinary evolution that fits our empirical data very well. We find a cultural ‘founder effect’ produced by the non-equilibrium dynamics of the model. Both the invariant and idiosyncratic aspects of culture are accounted for by our model, which may have applications in other kinds of evolutionary processes

For each cookery book database, we counted the number of recipes in which each ingredient appears. The ingredients were ordered according to descending frequency of usage. This allows the representation of the statistical hierarchy of ingredients in a cookery book by a frequency-rank plot, as introduced by Zipf. The next figure gives the frequency-rank plots for the Brazilian (1969 edn), British, French and medieval cookery books, showing a remarkable similarity in their statistical patterns. Time invariance is supported by the data next figure, which give the frequency-rank plots for the editions of the Brazilian cookery book. The structure of ingredient rankage in the Brazilian cookery book remained stable amidst the change from a regional to a more globalized food consumer profile that took place in the last 50 years. All these curves exhibit a power-law behaviour which can be well fitted by a Zipf–Mandelbrot law to capture finite size effects

(a) Cultural invariance. Frequency-rank plot for different cookery books: Pleyn Delit (circles), Dona Benta 1969 (squares), New Penguin (stars) and Larousse Gastronomique (triangles). (b) Temporal invariance. Frequency- rank plot for Dona Benta 1946 (squares), 1969 (lozenges) and 2004 (circles)

In another recent work, we collect a new data set of recipes from Medieval Europe before the Columbian Exchange and investigate the flavor pairing hypothesis historically. A strong determinant of the flavor of foods is the aromatic compounds that reach the olfactory system, either through the nose or through retro-olfaction. Humans are adept at detecting even trace amounts of these compounds and they have a great effect on hedonic perception. Chemically, flavor compounds come from groups such as acetals, acids, alcohols, aldehydes, esters, furans, hydrocarbons, ketones, lactones, and phenols. The primary calculation to understand the flavor pairing hypothesis is to compute the average number of shared flavor compounds among the ingredients in a recipe R. Let R be a set of nR different ingredients. Then the average number of shared compounds is

where Ci is the set of flavor compounds in ingredient i and Cj is the set of flavor compounds in ingredient j.

Medieval recipes were chosen for several reasons. One reason is that they have much historical interest. In fact, reading historical cookbooks as inspiration for new dishes. As we have discussed, we are interested in examining the effect of data sets with different properties, and thus we conduct empirical studies with two different flavor compound databases: VCF and Fenaroli.  They found the following trends in the dataset

For other results please refer to the reference. Now to end the post we can see that in our own country there is so much diversity of cuisines - whose underlying network is worth exploring !

Reference:

• https://www.youtube.com/v/qWAF9PgDg2c&start=271&end=381

• http://arxiv.org/abs/1111.6074  Flavour network and the principles of food pairing [Yong-Yeol Ahn, Sebastian E. Ahnert, James P. Bagrow, Albert-László Barabási]

• http://iopscience.iop.org/1367-2630/10/7/073020/pdf/1367-2630_10_7_073020.pdf   -- The non-equilibrium nature of culinary evolution [Osame Kinouchi, Rosa W Diez-Garcia, Adriano J Holanda, Pedro Zambianchi and Antonio C Roque]
• http://ssg.mit.edu/~krv/pubs/VarshneyVWM_ijcaiw2013.pdf Flavor Pairing in Medieval European Cuisine: A Study in Cooking with Dirty Data - [Kush R. Varshney, Lav R. Varshney, Jun Wang and Daniel Myers]

Measure of systemic risk in Complex banking network

Introduction:    
 The understanding and prediction of world economic downfalls has become very important. After the recession in 2008, the interaction among the financial bodies has become even more complex. Thus it is very difficult to predict. However the prediction is really very important to prevent such economic downfalls in future and take appropriate measures. In this work, it has been shown that directed Clustering coefficient can be used as a measure of systemic risk in Interbank network.
      Understanding the aggregate behaviour of economic and financial systems require tools belonging to the field of econometrics of times series, complex systems, game theory and agent-based models. Banking lending networks are one of the most important financial systems that are subjected to systemic risk, even small shocks constrained only to a few banks can be spread by contagion and affect the entire system.
      In this work a new interpretation of clustering coefficients to measure systematic risk has been developed. These clustering coefficients have also been correlated with interest rates to show that the interbank topology changes with the macroeconomic environment. The Brazilian interbank network has been used in the study.

Clustering coefficients for directed networks

Let A and W be the directed adjacency matrix and directed matrix of weights that represents the network. Let also dⁱⁿ_i , d^out_i and d^tot_i = dⁱⁿ_i +d^out_i be respectively the in-degree of node i, the out-degree of node i, and the total degree of node i. Furthermore, let d↔ =∑ _j≠i a_ija_ji = A²_ii. In binary directed networks, the clustering coefficient of node i for a binary network may be defined as the ratio between all the possible triangles formed by i and the number of all possible triangles that could be formed

C^D_i (A) =(A + A^T )³_ii /(2[d^tot_i (d^tot_i − 1) − 2d^↔_i ])                      (1)                                                    This clustering coefficient defined for the unweighted case. This can be easily extended to the weighted case by replacing the number of directed triangles formed with its weighted counterparts

˜ C^D_i (W)  =[Wˆ + (Wˆ ^T )]³_ii /(2[d^tot_i (d^tot_i − 1) − 2d^↔_i ])            (2)

where Wˆ = W^{[ 1/3]} = [w^1/3_ij ].

However, these two definitions (1) and (2) are not enough to characterize the richness of patterns that take place in a complex directed network. In fact, Eqs. (1) and (2) treat all the possible triangles as if they were the same.However, in directed graphs, edges that point to different directions should be interpreted differently. Thus four definitions are necessary which are represented in Fig. 1. 

(a)  Cycle when there is a cyclical relation among i and its neighbours. The clustering coefficients for binary case is

C^cyc_i= (A)³_ii/(dⁱⁿ_id^out_i- d^↔_I )

and for weighted case is given by

˜ C^cyc_i= (Wˆ)³_ii/(dⁱⁿ_id^out_i- d^↔_I ) .

(b) Middleman, when one of the neighbours of node I holds two outward edges and the other holds two inward edges. In this case the associated clustering coefficient for the binary case is

C^mid_i= (AA^TA)_ii/(dⁱⁿ_id^out_i- d^↔_I )

and for weighted case is given by

˜ C^mid_i=(WW^TW)_ii/(dⁱⁿ_id^out_i- d^↔_I )

(c)  In, when i holds two inward edges. In this case, the associated clustering coefficient for binary case is

     Cⁱⁿ_i= (A^TA²)_ii/ (dⁱⁿ_i(dⁱⁿ_i-1))

  and for weighted case is given by

      ˜ Cⁱⁿ_i= (Wˆ ^T Wˆ ²)_ii/ (dⁱⁿ_i(dⁱⁿ_i-1))

(d) Out, when i holds two outward edges. In this case, the associated clustering coefficient for the binary case is

        C^out_i= (A²A^T)_ii/ (d^out_i(d^out_i-1))

and for weighted case is given by

      ˜ C^out_i= (Wˆ ²Wˆ ^T)_ii/ (d^out_i(d^out_i-1))

Unweighted clustering coefficient counts the number of triangles of a given type. Weighted clustering coefficient is strongly affected by the largest weights.  In the following discussion it is assumed that an edge that arrives to node i coming from node j means that bank i borrowed money from bank j, that is bank j lent money to bank i. The four patterns in Fig. 1 have different interpretations of systematic risk.

          In Fig.1(a), bank i lends to bank j, which lends to bank h, which in turn lends back to bank i. therefore large values do not represent higher risk in this case. In Fig. 1(b) , the counterparts of bank I, bank j and h , are either borrowing or lending from the other two banks . In this case large value imply a higher risk as bank i is at the same time exposed to risk and source of risk of the other banks. Fig. 1 (c) presents the case in which ˜ Cⁱⁿ_i bank i is borrowing from both the banks. Here bank i is increasing the risk of banking system. If bank i fails then it will not pay some or all the loans that is has made and subsequently the other two banks may not be able to meet their obligations with each other. Therefore the loss in the system will increase. In Fig. 1 (d), ˜ C^out_i bank i is increasing it’s own exposure as it is lending to two counterparties. If one of these bank fails, as it may not pay the other bank the losses suffered from bank i may increase. Thus if this clustering coefficient is high, we can say that bank i has a large exposure and higher risk within interbank network. Overall, high values of coefficients ˜ C^mid_i and ˜ Cⁱⁿ_i imply high systemic risk and high value of ˜ C^out_i imply higher exposure of bank i. High clustering coefficients are associated with high exposures, however low coefficients do not mean low exposure, as networks in which banks are interconnected without forming triangles have all their clustering coefficients equal to zero although their exposures are non-zero.

 The data has been collected on daily loans made between financial institutions within Brazilian financial system for all banks and financial institutions that have exposure in interbank market , for the period from January 2004 to November 2007.

   Results

Firstly the frequency of each of the patterns of lending as presented in Fig. 1 is studied, since there is a relation between systemic risk and pattern of lending. Table 1 presents the statistics of averaged clustering coefficients for the period of the sample and for each type of bank. It is observed that there is a large heterogeneity between banks which is evident from the figures which are not Gaussian.

Fig 2 shows the evolution of the clustering coefficients over time, reinforcing that different bank types have different strategies when dealing with the interbank market. Although the clustering coefficients vary strongly over time, most of them vary around their mean value. The Pearson correlation is calculated between the daily clustering coefficients and basic interest rates, employing the daily CDI interbank interest rate as a benchmark for interest rates in Brazil. Here a negative correlation between the ˜ C^mid coefficient and changes of CDI interbank interest rates, which imply that as interest rate increase, banks decrease their relative exposure in the network. The correlation coefficients for all, public, domestic and foreign banks with interest rates are -0.257423,-0.136349,-0.302239 and -0.370078 respectively. This shows that different banks pursue different strategies which may be due to diversity in obtaining funds domestically and internationally.

       

  In this network, the banks in the centre are interconnected in triangular patterns and have high mutual exposures. The non-triangular patterns are rather rare in the centre, where the clustering coefficients are higher, and are not common on the periphery, where there are lower coefficients, which results in a negligible underestimation of them.

          These coefficients can be used to refine results obtained for individual banks as introduced by Brink and Gilles, given by

β^B_i=∑_j(w_ji/∑_kw_jk)   

where w_jk is the exposure’s matrix, in which bank j owes w_ij to bank i. In this case, the bank i’s dominance measure represents the sum of the participations of its debts on their creditors’ exposures; but to measure risk, it would be more useful to take into account the creditors’ provisions for losses or capital, instead of their total exposure, as in

β_i=∑_j(w_ji/E_j)

          Where E_j is the creditor j’s provision for losses or capital. This measure gives the shock provoked by an occasional default of bank i on its creditors. This measure is complemented by the ˜ C^out_i weighted clustering coefficient. A bank with high ˜ C^out_i has large debts and is involved on strong exposure relationships, when compared to the entire banking network. Thus, if a bank possesses high βi and ˜ C^out_i, it is a strong candidate to be a source of systemic risk, which can be further studied.

Conclusion:
In this work the directed clustering coefficient is used as a measure of systemic risk. It has been shown that the clustering coefficients measure vary over banks and are negatively correlated with changing interest rates. More research can be done to exploit in depth how the topology of interbank network changes.
References:
1> Directed clustering coefficient as a measure of systemic risk
in complex banking networks  ,Benjamin M. Tabak, Marcelo Takami, Jadson M.C. Rocha,
Daniel O. Cajueiro , Sergio R.S. Souza, (Physica A 394 (2014) 211–216)
2>F. Allen, D. Gale, The Journal of Political Economy 108 (2000) 1–33

3>R.V.D. Brink, R.P. Gilles, Social Networks 22 (2000) 141–157