Increasing the Complications

Lot has been studied for the past few months in complex networks. Some non-trivial topological features in real time networks such as citation network, movie actor network, web graph and many more. All these graphs were having some common features such as they were are simple, undirected, and un-weighted graphs. Network topological features have been studied on lots of other types of graphs too. (I am not saying that the course was less so please don't increase the syllabus). Some other interesting graphs which show some unique behavior or characteristic properties worth studying can be weighted graphs, directed graphs, eulerian graph, hamiltonian graph.

Considering weighted graphs, they are not that complicated if seen superficially but they can be a useful representation to some complicated real-time networks which are not covered by simple graphs or are partially covered in terms of information and thus are unable to study some vital results that are seen in the real-time systems.

Let’s take an example. The movie actor graph can be further made weighted with the weights showing the number of times he/she was on screen or the time for which he/she was on screen. This graph will give a better representation to the actual weightage of an actor in the movie rather than giving equal weight to all the actors (lead/subordinate/extras).

Another example can be Airport Network (Fig 1). This graph in a simple way can represent all the connected airports. However this graph can be extended to weighted graph in order to represent the total number of seats available between two airports in all the flights. The extended information can be well used to study traffic over two places rather than just studying the connectivity of places in case of un-weighted graphs.

 

Fig1. The Airport Network (edge weight denote no. of seats (million/year)

However this new graph will also need some new definitions to the old terms or some new terms may even be coined in.

To study this new attribute, weight of edge, along with the old studies on the undirected graph a new definition coined in the paper by A. Barrat is of vertex strength. Vertex strength (s_i) can aptly cover the degree distribution along with weight of edge. It is defined as summation all the weights of the edges of a vertex. In the case of the Airport Network the vertex strength simply accounts for the total traffic handled by each airport. This certainly is more useful measure rather than just having connectivity of airports.

Here a_ij denote the presence of edge and w_ij denote the weight on the edge.

The strength also gives the degree centrality of the vertex since the degree centrality is not the degree anymore. It also has to cover for the weights on the edges.

Another type of graph can be directed graphs. Here one can think of some unbalanced relations of undirected graphs that have been studied. In those graphs a directed edge will provide a better and accurate view.

One example here that fits here is the citation graph (Fig 2). The graph of research papers with each out-edge denoting a citation of source node. Here again it would be interesting to observe the clusters where the group of papers are cited by most other papers. A more important set of paper can be easily pointed out according to the number of papers to which a certain paper has been cited.

Fig 2. Citation graph (Research papers from the field of biology)

One simplification of directed graph for certain calculation is breaking each vertex into a pair of vertices, one denoted as in-vertex and the other as the out-vertex. The in-vertex shall have edges that were ending into the original vertex. Similarly out-vertex shall have edges that were originating i.e. going out of the original vertex. All the edges in this graph are undirected. This was quite a useful representation for graph attributes. More can be done to find out whether this is useful for complex networks attributes or not.

Lot more is there to explore in complex networks w.r.t. the types of graphs, properties, interpretations etc. A couple of them I tried to present here. The more we discover, the more it is going to be interesting. Though this blog did not cover much but it was just intended to give a brief overview (some of my views) on these topics.

Thank you.

REFERENCES:

•          The architecture of complex weighted networks A. Barrat, M. Barthélemy, R. Pastor-Satorras,  A. Vespignani
•          Albert, R. & Barabási, A.-L. (2002) Rev. Mod. Phys. 74, 47-97.
•          Pastor-Satorras, R. & Vespignani, A. (2001) Phys. Rev. Lett. 86, 3200-3203.
•         Callaway, D. S., Newman, M. E. J., Strogatz, S. H. & Watts, D. J. (2000) Phys. Rev. Lett. 85, 5468-5471.