From Graph Theory To Complex Network Theory

250 Years Long Journey- From Graph Theory To Complex Network Theory

Speaker: Dr. Md Kamrul Hassan
Department of Physics
University of Dhaka


Registration link-

The terminology scale-free network and complex network albeit relatively new, they are actually deeply rooted to the more than two centuries old graph theory. The first work on graph theory can be traced back to the Königsberg’s seven bridge problem. This problem involved the question whether it was possible to make a walk crossing exactly once each of the seven bridges built to connect the two island and its shores across the river Pregel. In 1735 Leonard Euler solved it by mapping it as an abstract graph. It was eventually developed as an active subject of discrete mathematics contributed by many famous mathematicians like Cauchy, Hamilton, Cayley, Kirchhoff and others who dealt with graphs those were highly ordered and deterministic. However, the graph theory that began with the work of Euler witnessed a paradigm shift in 1959 with the seminal work of two mathematicians Paul Erdös and Alfred Rényi who proposed a simple model to generate random graph.

In general, network is a simple or intricate wiring of a set of nodes or vertices by links or edges. Recently, much of the activities on network theory focusing primarily on complex network. So we first need to know what do we mean by complex system. Complex systems typically comprise of a large number of components, building blocks or agents which are capable of interacting with each other that results in a self-organization into a state which have an emergent behaviour. In addition to this complex network, it also have non-trivial topological features in the sense that the wiring patterns resulted from the connection between their constituents are neither regular nor random in character. Nodes in the complex network may represent neurones of brain, molecules of cells of living animals, individuals of society, computer or router of Internet, web-documents of WWW, power-stations of power-grid etc and the corresponding links or edges may represent axons, chemical reactions, friendships or professional ties, cable or wireless connections, URL addresses, transmission lines etc. In the language of network, spatial distance between nodes are disregarded as their distances measured in units of the minimum number of links or edges needed to connect the two nodes.

Just over a decade ago Barabási and Albert revolutionised the notion of the network theory by recognising the fact that natural and man-made networks are not static. Rather they grow by continuous addition of new nodes. They further argued that the new nodes establish links to the well connected existing ones preferentially, rather than randomly – known as the preferential attachment (PA) rule. It essentially embodies the intuitive idea of the rich get richer principle of the Matthew effect in sociology. Barabási and Albert (BA) then presented a simple theoretical model incorporating both the ingredients and showed that the resulting network can reproduce the power-law degree distribution which most real life networks exhibit.

Recently, we present a model in which an incoming node randomly chooses an already connected node, and then connects itself not with that one but with m neighbours of the chosen node at random. This idea is reminiscent of the growth of the weighted planar stochastic lattice (WPSL) in whose dual, an existing node gains links only if one of its neighbours is picked. Seeing that the dual of WPSL emerges as a network with power-law degree distribution, we became curious as to what happens if a graph is grown following a similar rule. We call it the mediation-driven attachment (MDA) rule since the node that has been picked at random from all the already connected nodes acts as a mediator for connection between its neighbour and the new node. Such a rule can embody the preferential attachment process since an already well-connected node has more mediators and through the mediated attachment process, it can gain even more neighbours. Finding out the extent of preference in comparison to the PA rule of the BA model forms an important proposition of this work. There exists a host of networks where the presence of the MDA rule is too obvious. For instance, while uploading a document to a website or writing a paper, we usually find documents to link with or papers to cite through mediators. In social networks such as friendships, co-authorship, Facebook, and movie actor networks, people get to know each other through a mediator or through a common neighbour. Thus the MDA model can be a good candidate for describing social networks.

This event is open for all. However, a preregistration is mandatory. Registration link-

Date: Saturday, May 20, 2017
Time: 11am

Venue: Gallery Lecture Theatre, GLT-101
Dept. of Soil, Water & Environment
Curzon Hall, University of Dhaka
Location Map-

For any query, please post below or get in contact with our representative at +8801512132924

1 thought on “From Graph Theory To Complex Network Theory

Leave a Reply

Your email address will not be published. Required fields are marked *