Tweets to the Twitter

From Cohen Courses
Jump to navigationJump to search


We wish to study many complex phenomena in their richness using a simple model, local activities like message passing to the occasional appearance of a globally influential event. In that end, we motivate a general model of generating realistic graphs in a socially grounded manner, which is possibly the first such attempt. Then we show how this model can be used for modeling more richer activities and give insights to different contentions in the area of local navigation. We also cover the role of influentials in message passing and more generally cascades. Our work gives several insights or is consistent with the many experimental results in social science and networks.


While our work was purely based on simulation, a graph fitting work we compare with uses the following disparate datasets to evaluate their method:

Interesting related work

Appearance of power laws through different perspectives

Power laws can come from more complicated phenomena than meets the eye, nothing new today, but this paper was written before concepts like emergence were well known.

  • Simon, H. A. 1955. "On a Class of Skew Distribution Functions". Biometrika 42: 425–440.

Zipfian distribution is a subset of the family of power law distributions. Mandelbrot later generalized it and explained it using constraints based on the length of words and the intelligibility or coherence.

  • Zipf, George Kingsley. 1932. Selected Studies of the Principle of Relative Frequency in Language. Cambridge, MA: Harvard University Press.
  • Mandelbrot, Benoît. 1965. "Information Theory and Psycholinguistics". in B.B. Wolman and E. Nagel. Scientific psychology.

Realistic graph generation and fitting

Graph generation and fitting using Kronecker product and Metropolis-Hastings sampling. Broadly the idea is to find an appropriate seed graph and perform Kronecker product over it to generate somewhat realistic graphs. It is also mathematically proven that properties of Kronecker product allows one to model many properties visible in the real world.

  • Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication by J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos. European Conference on Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), 2005.
  • Scalable Modeling of Real Graphs using Kronecker Multiplication by J. Leskovec, C. Faloutsos. International Conference on Machine Learning (ICML), 2007.
  • Kronecker Graphs: An approach to modeling networks by J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, Z. Ghahramani. Journal of Machine Learning Research (JMLR)