Properties of Stochastic Kronecker Graph
The stochastic Kronecker Graph model can generate large random graph that closely resembles many real world networks. For example, the output graph has a heavy-tailed degree distribution, has a (low) diameter that effectively remains constant over time and obeys the so-called densification power law [1]. Aside from this list of very important graph properties, one may ask for some additional information about the output graph: What will be the expected number of isolated vertices? How many edges, self loops are there in the graph? What will be the expected number of triangles in a random realization? Here we try to answer the above questions. In the first phase, we bound the expected values of the aforementioned features from above. Next we establish the sufficient conditions to generate stochastic Kronecker graph with a wide range of interesting properties. Finally we show two phase transitions for the appearance of edges and self loops in stochastic Kronecker graph.
Keywords: Stochastic Kronecker Graph, Isolated vertex, Edge count, Self loops, triangles, Phase transitions.
Download Full-Text
ABOUT THE AUTHORS
Ahmed Mehedi Nizam
Ahmed Mehedi Nizam has obtained his B.Sc. Engineering degree from Bangladesh University of Engineering and Technology (BUET), Dhaka 1000, on February 2011 and is currently a M.Sc. Engg. Student in the same.
Md. Nasim Adnan
Md. Nasim Adnan received his M.Sc. in CSE from Bangladesh University of Engineering and Technology (BUET) and B.Sc. in CSE from Khulna University. Currently he is working as an Adjunct Assistant Professor at the Dept. of Computer Science and Engineering in University of Liberal Arts Bangladesh (ULAB). He also served as a Deputy Director in the Dept. of ITOCD, Bangladesh Bank. His research interest includes Data Mining, Database Systems, Software Engineering, Software and Systems Testing, and E-Commerce.
Md. Rashedul Islam
Md. Rashedul Islam received his M.Sc. in IT from RWTH-Achen and B.Sc. in CSE from Khulna University. Currently he is working as a Senior Lecturer at the Dept. of Computer Science and Engineering in University of Liberal Arts Bangladesh (ULAB).
Mohammod Akbar Kabir
Mohammod Akbar Kabir received his M.Sc. and B.Sc. (Hons.) in Computer Science from the University of Dhaka in 2000 and 1998 respectively. Currently he is working as an Assistant Professor in the Dept. of Economics, University of Dhaka. He also served as an Assistant Programmer in the Dept. of ITOCD, Bangladesh Bank and as a Lecturer in the Dept. of Computer Science, Dhaka City College. His research interests are in the area of VLSI Design and E-Commerce.
Ahmed Mehedi Nizam
Ahmed Mehedi Nizam has obtained his B.Sc. Engineering degree from Bangladesh University of Engineering and Technology (BUET), Dhaka 1000, on February 2011 and is currently a M.Sc. Engg. Student in the same.
Md. Nasim Adnan
Md. Nasim Adnan received his M.Sc. in CSE from Bangladesh University of Engineering and Technology (BUET) and B.Sc. in CSE from Khulna University. Currently he is working as an Adjunct Assistant Professor at the Dept. of Computer Science and Engineering in University of Liberal Arts Bangladesh (ULAB). He also served as a Deputy Director in the Dept. of ITOCD, Bangladesh Bank. His research interest includes Data Mining, Database Systems, Software Engineering, Software and Systems Testing, and E-Commerce.
Md. Rashedul Islam
Md. Rashedul Islam received his M.Sc. in IT from RWTH-Achen and B.Sc. in CSE from Khulna University. Currently he is working as a Senior Lecturer at the Dept. of Computer Science and Engineering in University of Liberal Arts Bangladesh (ULAB).
Mohammod Akbar Kabir
Mohammod Akbar Kabir received his M.Sc. and B.Sc. (Hons.) in Computer Science from the University of Dhaka in 2000 and 1998 respectively. Currently he is working as an Assistant Professor in the Dept. of Economics, University of Dhaka. He also served as an Assistant Programmer in the Dept. of ITOCD, Bangladesh Bank and as a Lecturer in the Dept. of Computer Science, Dhaka City College. His research interests are in the area of VLSI Design and E-Commerce.
