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
- 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. **,**5468-5471.

## No comments:

## Post a Comment