A parallel data generator for efficiently generating “realistic” social streams

Abstract

A social stream refers to the data stream that records a series of social entities and the dynamic interactions between two entities. It can be employed to model the changes of entity states in numerous applications. The social streams, the combination of graph and streaming data, pose great challenge to efficient analytical query processing, and are key to better understanding users’ behavior. Considering of privacy and other related issues, a social stream generator is of great significance. A framework of synthetic social stream generator (SSG) is proposed in this paper. The generated social streams using SSG can be tuned to capture several kinds of fundamental social stream properties, including patterns about users’ behavior and graph patterns. Extensive empirical studies with several real-life social stream data sets show that SSG can produce data that better fit to real data. It is also confirmed that SSG can generate social stream data continuously with stable throughput and memory consumption. Furthermore, we propose a parallel implementation of SSG with the help of asynchronized parallel processing model and delayed update strategy. Our experiments verify that the throughput of the parallel implementation can increase linearly by increasing nodes.

Keywords

social stream / data generator / SSG / parallel generation

References

[1] Zhou A, Qian W, Ma H. Social media data analysis for revealing collective behaviors. In: Proceedings of the 18th ACM International Conference on Knowledge Discovery and Data Mining. 2012, 1402

[2] Olston C, Reed B, Srivastava U, Kumar R, Tomkins A. Pig latin: a not-so-foreign language for data processing. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. 2008, 1099–1110

[3] Thusoo A, Sarma J S, Jain N, Shao Z, Chakka P, Anthony S, Liu H, Wyckoff P, Murthy R. Hive: a warehousing solution over a mapreduce framework. Proceedings of the VLDB Endowment, 2009, 2(2): 1626–1629

[4] Engle C, Lupher A, Xin R, Zaharia M, Franklin M J, Shenker S, Stoic I. Shark: fast data analysis using coarse-grained distributed memory. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. 2012, 689–692

[5] Pujol J M, Erramilli V, Siganos G, Yang X, Laoutaris N, Chhabra P, Rodriguez P. The little engine(s) that could: scaling online social networks. ACM Special Interest Group on Data Communication, 2010, 40(4): 375–386

[6] Silberstein A, Terrace J, Cooper B F, Ramakrishnan R. Feeding frenzy: selectively materializing users’ event feeds. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. 2010, 831–842

[7] Erling O, Averbuch A, Larribapey J, Chafi H, Gubichev A, Prat-Pérez A, Pham M, Boncz P A. The LDBC social network benchmark: interactive workload. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015, 619–630

[8] Ma H, Wei J, Qian W, Yu C, Zhou A. On benchmarking online social media analytical queries. In: Proceedings of the 1st International Workshop on Graph Data Management Experiences and Systems. 2013, 10

[9] Pham M, Boncz P A, Erling O. S3G2: a scalable structure-correlated social graph generator. In: Proceedings of Technology Conference on Performance Evaluation and Benchmarking. 2012, 156–172

[10] Chung F R, Lu L. The average distances in random graphs with given expected degrees. the National Academy of Sciences of the United States of America, 2002, 99(25): 15879–15882

[11] Chung F R, Lu L. Connected components in random graphs with given expected degree Sequences. Annals of Combinatorics, 2002, 6(2): 125–145

[12] Ma H, Qian W, Xia F, He X, Xu J, Zhou A. Towards modeling popularity of microblogs. Frontiers of Computer Science, 2013, 7(2): 171–184

[13] Ross S M. Introduction to Probability Models. New York: Academic Press, 2010

[14] Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998, 20(1): 359–392

[15] Broder A Z, Kumar R, Maghoul F, Raghavan P, Rajagopalan S, Stata R, Tomkins A, Wiener J L. Graph structure in the Web. In: Proceedings of the 9th International World Wide Web Conferences. 2000, 309–320

[16] Newman M E J. The structure and function of complex networks. Siam Review, 2003, 45(2): 167–256

[17] Dorogovtsev S N, Mendes J F. Evolution of networks. Advances in Physics, 2002, 51(4): 1079–1187

[18] Albert R, Barabasi A. Statistical mechanics of complex networks. Reviews of Modern Physics, 2001, 74(1): 47–97

[19] Strogatz S H. Exploring complex networks. Nature, 2001, 410(6825): 268–276

[20] Newman M E J. Networks: an introduction. Astronomische Nachrichten, 2010, 327(8): 741–743

[21] Chakrabarti D, Faloutsos C. Graph mining: laws, generators, and algorithms. ACM Computing Surveys, 2006, 38(1): 2

[22] Newman M E J. Power laws, Pareto distributions and Zipf’s law. Contemporary Physics, 2005, 46(5): 323–351

[23] Clauset A, Shalizi C R, Newman M E J. Power-law distributions in empirical data. Siam Review, 2009, 51(4): 661–703

[24] Coan J A, Sbarra D A. Social baseline theory: the social regulation of risk and effort. Current Opinion in Psychology, 2015, 1: 87–91

[25] Abello J, Buchsbaum A L, Westbrook J. A functional approach to external graph algorithms. Algorithmica, 2002, 32(3): 437–458

[26] Redner S. How popular is your paper? An empirical study of the citation distribution. European Physical Journal B, 1998, 4(2): 131–134

[27] Kwak H, Lee C, Park H, Moon S B. What is Twitter, a social network or a news media? In: Proceedings of the 19th International World Wide Web Conferences. 2010, 591–600

[28] Ebel H, Mielsch L, Bornholdt S. Scale-free topology of e-mail networks. Physical Review E, 2002, 66(3): 035103

[29] Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine. In: Proceedings of the 19th International World Wide Web Conferences. 2010, 431–440

[30] Pandurangan G, Raghavan P, Upfal E. Using pagerank to characterize Web structure. In: Proceedings of the 8th International Conference on Computing and Combinatorics. 2002, 330–339

[31] Tauro S L, Palmer C R, Siganos G, Faloutsos M. A simple conceptual model for the Internet topology. In: Proceedings of Global Communications Conference. 2001, 1667–1671

[32] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. ACM Special Interest Group on Data Communication, 1999, 29(4): 251–262

[33] Albert R. Diameter of the World Wide Web. Nature, 1999, 401(6749): 130–131

[34] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks. Nature, 1998, 393(6684): 440–442

[35] Srisaard S. Mining the Web: discovering knowledge from hypertext data. Online Information Review, 2003, 27(4): 291

[36] Gkantsidis C, Mihail M, Zegura E W. Spectral analysis of Internet topologies. In: Proceedings of the 22nd International Conference on Computer Communications. 2003, 364–374

[37] Tangmunarunkit H, Govindan R, Jamin S, Shenker S, Willinger W. Network topologies, power laws, and hierarchy. ACM Special Interest Group on Data Communication, 2002, 32(1): 76

[38] Casteigts A, Flocchini P, Quattrociocchi W, Santoro N. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 2012, 27(5): 387–408

[39] Santoro N, Quattrociocchi W, Flocchini P, Casteigts A, Amblard F. Time-varying graphs and social network analysis: temporal indicators and metrics. In: Proceedings of the 3rd AISB Social Networks and Multiagement Systems Symposium. 2011, 32–38

[40] Ferreira A. Building a reference combinatorial model for MANETs. IEEE Network, 2004, 18(5): 24–29

[41] Holme P, Saramki J. Temporal networks. Physics Reports, 2012, 519(3): 97–125

[42] Krapivsky P L, Redner S, Leyvraz F. Connectivity of growing random networks. Physical Review Letters, 2000, 85(21): 4629

[43] Quattrociocchi W, Amblard F, Galeota E. Selection in scientific networks. Social Network Analysis & Mining, 2012, 2(3): 229–237

[44] Leskovec J, Kleinberg J M, Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the 11th ACM SIGKOD International Conference on Knowledge Discovery and Data Mining. 2005, 177–187

[45] Leskovec J, Kleinberg J M, Faloutsos C. Graph evolution: densification and shrinking diameters. ACM Transactions on Knowledge Discovery From Data, 2007, 1(1): 2

[46] Erdos P, Rényi A. On the evolution of random graphs. Transactions of the American Mathematical Society, 2011, 286(1): 257–274

[47] Aiello W, Chung F, Lu L. A random graph model for massive graphs. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 2000, 171–180

[48] Newman M E J, Strogatz S H, Watts D J. Random graphs with arbitrary degree distributions and their applications. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2001, 64(2): 026118

[49] Simon H A. On a class of skew distribution function. Biometrika, 1955, 42(3/4): 425–440

[50] Barabasi A, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509–512

[51] Albert R, Barabasi A. Topology of evolving networks: local events and universality. Physical Review Letters, 2000, 85(24): 5234–5237

[52] Kleinberg J M, Kumar R, Raghavan P, Rajagopalan S, Tomkins A. The Web as a graph: measurements, models, and methods. In: Proceedings of International Computing and Combinatorics Conference. 1999, 1–17

[53] Kumar R, Raghavan P, Rajagopalan S. Stochastic models for the Web graph. In: Proceedings of the 41st Annual Symosium on Foundations of Computer Science. 2000, 57–65

[54] Dorogovtsev S N, Mendes J F, Samukhin A N. Structure of growing networks with preferential linking. Physical Review Letters, 2000, 85(21): 4633–4636

[55] Chen Q, Chang H, Govindan R, Jamin S, Shenker S, Willinger W. The origin of power laws in Internet topologies revisited. In: Proceedings of the 51st International Conference on Computer Communications. 2002, 608–617

[56] Bianconi G, Barabási A L. Competition and multiscaling in evolving networks. Physics Letters, 2000, 30(1): 37–43

[57] Barabási A, Jeong H, Néda Z, Ravasz E, Schubert A, Vicsek T. Evolution of the social network of scientific collaborations. Physica Astatistical Mechanics and Its Applications, 2002, 311(3): 590–614

[58] Aiello W, Chung F, Lu L. Random evolution in massive graphs. Computer, 2001, 510: 519

[59] Borgs C, Chayes J, Riordan O. Directed scale-free graphs. In: Proceedings of the 14th Acm-Siam Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics. 2003, 132–139

[60] Waxman B M. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 2002, 6(9): 1617–1622

[61] Looz M V, Staudt C L, Meyerhenke H, Prutkin R. Fast generation of complex networks with underlying hyperbolic geometry. 2015, arXiv preprint arXiv:1501.03545

[62] Chakrabarti D, Zhan Y, Faloutsos C. R-MAT: a recursive model for graph mining. In: Proceedings of the 2004 SIAM International Conference on Data Mining. 2004, 442–446

[63] Leskovec J, Faloutsos C. Scalable modeling of real graphs using kronecker multiplication. In: Proceedings of the 24th International Conference on Machine Learning. 2007, 497–504

[64] Dominguez-Sal D, Urbón-Bayes P, Giménez-Vaó A, Gómez-Villamor S, Martínez-Bazan N, Larriba-Pey J. Survey of graph database performance on the HPC scalable graph analysis benchmark. In: Proceedings of the International Conference on Web Age Information Management. 2010, 37–48

[65] Gleich D F, Owen A B. Moment-based estimation of stochastic kronecker graph parameters. Internet Mathematics, 2012, 8(3): 232–256

[66] Miller B A, Bliss N T, Wolfe P J. Subgraph detection using eigenvector L1 norms. In: Proceedings of the 23rd International Conference on Neural Information Processing Systems. 2010, 1633–1641

[67] Miller B A, Stephens L H, Bliss N T. Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs. In: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. 2012, 3265–3268

[68] Mir D J, Wright R N. A differentially private estimator for the stochastic kronecker graph model. In: Proceedings of the 2012 Joint EDBT/ICDT Workshops. 2012, 167–176

[69] Leskovec J, Chakrabarti D, Kleinberg J M, Faloutsos C, Ghahramani Z. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research, 2010, 11(Feb): 985–1042

[70] Seshadhri C, Pinar A, Kolda T G. An in-depth study of stochastic kronecker graphs. In: Proceedings of the 11th IEEE International Conference on Data Mining. 2011, 587–596

[71] Sala A, Cao L, Wilson C, Zablit R, Zheng H, Zhao B Y. Measurementcalibrated graph models for social network experiments. In: Proceedings of the 19th International Conferences onWorldWideWeb. 2010, 861–870

[72] Akoglu L, Mcglohon M, Faloutsos C. RTM: laws and a recursive generator for weighted time-evolving fraphs. In: Proceedings of the 8th IEEE International Conference on Data Mining. 2008, 701–706

[73] Hakimi S L. On Realizability of a set of integers as degrees of the vertices of a linear graph. I. Journal of the Society for Industrial and Applied Mathematics, 1962, 10(3): 496–506

[74] Seshadhri C, Kolda T G, Pinar A. Community structure and scale free collections of Erdös-Rényi graphs. Physical Review E, 2012, 85(5): 056109

[75] Du N, Wang H, Faloutsos C. Analysis of large multi-modal social networks: patterns and a generator. In: Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery. 2010, 393–408

[76] Armstrong T G, Ponnekanti V, Borthakur D, Callaghan M. LinkBench: a database benchmark based on the Facebook social graph. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013, 1185–1196

[77] Kolda T G, Pinar A, Plantenga T D, Seshadhri C. A scalable generative graph model with community structure. SIAM Journal on Scientific Computing, 2014, 36(5): C424–C452

[78] Yoo A, Henderson K. Parallel generation of massive scale-free graphs. Computer Science, 2010, 7: 123–136

[79] Alam M M, Khan M, Marathe M V. Distributed-memory parallel algorithms for generating massive scale-free networks using preferential attachment model. In: Proceedings of the IEEE International Conference on High Performance Computing Data and Analytics. 2013, 1–12

[80] Lo Y C, Lai H, Li C T, Lin S S. Mining and generating large-scaled social networks via MapReduce. Social Network Analysis and Mining, 2013, 3(4): 1449–1469

[81] Hadian A, Nobari S, Minaeibidgoli B, Qu Q. ROLL: fast in-memory generation of gigantic scale-free networks. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 1829–1842

[82] Barabási A. The origin of bursts and heavy tails in human dynamics. Nature, 2005, 435(7039): 207–211

[83] Cho J, Garciamolina H. Estimating frequency of change. ACM Transactions on Internet Technology, 2003, 3(3): 256–290

[84] Cho J, Garciamolina H. Synchronizing a database to improve freshness. International Conference on Management of Data, 2000, 29(2): 117–128

[85] Eubank S, Guclu H, Kumar V S, Marathe M V, Srinivasan A, Toroczkai Z, Wang N. Modelling disease outbreaks in realistic urban social networks. Nature, 2004, 429(6988): 180–184

[86] Brewington B E, Cybenko G. How dynamic is the Web. In: Proceedings of the 9th International World Wide Web Conferences. 2000, 257–276

[87] Oliveira J G, Barabási A. Human dynamics: Darwin and Einstein correspondence patterns. Nature, 2005, 437(7063): 1251

[88] Li N, Zhang N, Zhou T. Empirical analysis on temporal statistics of human correspondence patterns. Complex System & Complexity Science, 2008, 387(25): 6391–6394

[89] Hong W, Han X P, Zhou T, Wang B H. Heavy-tailed statistics in short-message communication. Chinese Physics Letters, 2009, 26(2): 028902

[90] Candia J, González M C, Wang P, Schoenharl T, Madey G, Barabási A. Uncovering individual and collective human dynamics from mobile phone records. Journal of Physics A: Mathematical and Theoretical, 2008, 41(22): 224015

[91] Dezsö Z, Almaas E, Lukács A, Rácz B, Szakadát I, Barabási A L. Dynamics of information access on the Web. Physical Review E, 2006, 73(6): 066132

[92] Vázquez A, Oliveira J G, Dezsö Z, Goh K, Kondor I, Barabási A. Modeling bursts and heavy tails in human dynamics. Physical Review E, 2005, 73(2): 036127

[93] Gabrielli A, Caldarelli G. Invasion percolation and critical transient in the Barabási Model of human dynamics. Physical Review Letters, 2007, 98(20): 208704

[94] Han X P, Zhou T, Wang B H. Modeling human dynamics with adaptive interest. New Journal of Physics, 2008, 10(7): 073010

[95] Goncalves B, Ramasco J J. Human dynamics revealed through Web analytics. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2): 026123

[96] Malmgren R D, Stouffer D B, Campanharo A S L O, Amaral L A N. On universality in human correspondence activity. Science, 2009, 325(5948): 1696–1700

[97] Sia K C, Cho J, Hino K, Chi Y, Zhu S, Tseng B L. Monitoring RSS feeds based on user browsing pattern. In: Proceedings of International Conference on Weblogs and Social Media. 2007

[98] Sia K C, Cho J, Cho H K. Efficient monitoring algorithm for fast news alerts. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(7): 950–961

[99] Gruhl D, Guha R V, Liben-Nowell D, Tomkins A. Information diffusion through blogspace. In: Proceedings of the 13th International World Wide Web Conferences. 2004, 491–501

[100] Bollen J, Mao H, Pepe A. Modeling public mood and emotion: Twitter sentiment and socio-economic phenomena. In: Proceedings of the International Conference on Weblogs and Social Media. 2011, 450–453

[101] Malmgren R D, Stouffer D B, Motter A E, Amaral L A N. A Poissonian explanation for heavy tails in e-mail communication. the National Academy of Sciences of the United States of America, 2008, 105(47): 18153–18158

[102] Vazquez A. Impact of memory on human dynamics. Physica Astatistical Mechanics and its Applications, 2007, 373: 747–752

[103] Stewart W J. Probability, Markov Chains, Queues, and Simulation: the Mathematical Basis of Performance Modeling. Princeton: Princeton Univers Press, 2009

[104] Pennock D M, Flake G W, Lawrence S, Glover E J, Giles C L. Winners don’t take all: characterizing the competition for links on the Web. the National Academy of Sciences of the United States of America, 2002, 99(8): 5207–5211

[105] Bi Z, Faloutsos C, Korn F. The “DGX” distribution for mining massive, skewed data. In: Proceedings of the 7th ACM SIGKOD International Conference on Knowledge Discovery and Data Mining. 2001, 17–26

[106] Welch M J, Schonfeld U, He D, Cho J. Topical semantics of twitter links. In: Proceedings of the 4th ACM International Conference on Web Search and Data Mining. 2011, 327–336

[107] Galuba W, Aberer K, Chakraborty D, Despotovic Z, Kellerer W. Outtweeting the twitterers — predicting information cascades in microblogs. In: Proceedings of the 3rd Conference on Online Social Networks. 2010, 3–11

[108] Asur S, Huberman B A. Predicting the future with social media. In: Proceedings of the 2010 IEEE International Conference on Web Intelligence and Intelligent Agent Technology. 2010, 492–499

[109] Martin T, Ball B, Karrer B, Newman M E J. Coauthorship and citation in scientific publishing. 2013, arXiv preprint arXiv:1304.0473

[110] Xie J, Zhang C, Wu M. Modeling microblogging communication based on human dynamics. In: Proceedings of the 8th International Conference on Fuzzy Systems and Knowledge Discovery. 2011, 2290–2294

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature