Speaker: Dr. Kamrul Hassan, Professor, Department of Physics, Dhaka University
In this talk, he will discuss how Graph Theory was born and grown for more than 200 years and remained a part of Discrete Mathematics only. The first paradigm shift occurred when Paul Erdos and Alfred Renyi 1959 proposed a random graph model. Its construction starts with a fixed number of isolated nodes and thereafter at each step one labeled link from N(N-1)/2 is picked at random that connects a pair of nodes as labeled on either end of the link.
In this talk, he will also give a comprehensive account of the Erdos-Renyi (ER) model from the perspective of percolation theory. One of the recent highlights of percolation, in general, is that it is a transition from a disordered phase to an ordered phase where the former is characterized by order parameter P=0 and the latter by maximally high entropy H and vice versa for the latter case. To this end, he will show that ER transition is not accompanied by the order-disorder transition. In 2009, Achlioptas et al. proposed a new variant of the ER model in which two links are picked randomly instead of one at each step although ultimately only one of the links is added at each step and the other is discarded. The link to add is chosen following the Achlioptas process (AP) that encourages the smaller cluster to grow faster than the larger clusters. Inevitably it delays the transition but eventually, when it reaches near the critical point it is so unstable that the occupation of one or two links triggers an explosion of growth. It leads to the emergence of a giant cluster with a bang and hence it is called “explosive percolation” (EP). He will give an entropic argument to explain why the link that minimizes the product is the most energetically favorable choice which also explains the physics behind the powder keg effect. In 1999 Barabasi and Albert revolutionized the notion of the network theory by recognizing the fact that real networks are not static, but rather grow by the addition of new nodes establishing links preferentially, known as the preferential attachment (PA) rule, to the nodes that are already well connected. Incorporating both the ingredients, growth, and the PA rule, Barabasi and Albert (BA) presented a simple theoretical model and showed that such a network self-organizes into a power-law degree distribution. The phenomenal success of the BA model lies in the fact that it can capture, at least qualitatively, the key features of many real-life networks.
