A parallel data generator for efficiently generating “realistic” social streams
Chengcheng YU1, Fan XIA2, Weining QIAN2(), Aoying ZHOU2
1. College of Computer and Information Engineering, Shanghai Polytechnic University, Shanghai 201209, China 2. School of Data Science and Engineering, East China Normal University , Shanghai 200062, China
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.
A Zhou, W Qian, H Ma. Social media data analysis for revealing collective behaviors. In: Proceedings of the 18th ACM International Conference on Knowledge Discovery and Data Mining. 2012, 1402 https://doi.org/10.1145/2339530.2339746
2
C Olston, B Reed, U Srivastava, R Kumar, A Tomkins. 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 https://doi.org/10.1145/1376616.1376726
3
A Thusoo, J S Sarma, N Jain, Z Shao, P Chakka, S Anthony, H Liu, P Wyckoff, R Murthy. Hive: a warehousing solution over a mapreduce framework. Proceedings of the VLDB Endowment, 2009, 2(2): 1626–1629 https://doi.org/10.14778/1687553.1687609
4
C Engle, A Lupher, R Xin, M Zaharia, M J Franklin, S Shenker, I Stoic. 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 https://doi.org/10.1145/2213836.2213934
5
J M Pujol, V Erramilli, G Siganos, X Yang, N Laoutaris, P Chhabra, P Rodriguez. The little engine(s) that could: scaling online social networks. ACM Special Interest Group on Data Communication, 2010, 40(4): 375–386 https://doi.org/10.1145/1851182.1851227
6
A Silberstein, J Terrace, B F Cooper, R Ramakrishnan. Feeding frenzy: selectively materializing users’ event feeds. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. 2010, 831–842 https://doi.org/10.1145/1807167.1807257
7
O Erling, A Averbuch, J Larribapey, H Chafi, A Gubichev, A Prat-Pérez, M Pham, P A Boncz. The LDBC social network benchmark: interactive workload. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015, 619–630 https://doi.org/10.1145/2723372.2742786
8
H Ma, J Wei, W Qian, C Yu, A Zhou. On benchmarking online social media analytical queries. In: Proceedings of the 1st International Workshop on Graph Data Management Experiences and Systems. 2013, 10 https://doi.org/10.1145/2484425.2484435
9
M Pham, P A Boncz, O Erling. S3G2: a scalable structure-correlated social graph generator. In: Proceedings of Technology Conference on Performance Evaluation and Benchmarking. 2012, 156–172
10
F R Chung, L Lu. 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
F R Chung, L Lu. Connected components in random graphs with given expected degree Sequences. Annals of Combinatorics, 2002, 6(2): 125–145 https://doi.org/10.1007/PL00012580
12
H Ma, W Qian, F Xia, X He, J Xu, A Zhou. Towards modeling popularity of microblogs. Frontiers of Computer Science, 2013, 7(2): 171–184 https://doi.org/10.1007/s11704-013-3901-9
13
S M Ross. Introduction to Probability Models. New York: Academic Press, 2010
14
G Karypis, V Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998, 20(1): 359–392 https://doi.org/10.1137/S1064827595287997
15
A Z Broder, R Kumar, F Maghoul, P Raghavan, S Rajagopalan, R Stata, A Tomkins, J L Wiener. Graph structure in the Web. In: Proceedings of the 9th International World Wide Web Conferences. 2000, 309–320 https://doi.org/10.1016/S1389-1286(00)00083-9
A Clauset, C R Shalizi, M E J Newman. Power-law distributions in empirical data. Siam Review, 2009, 51(4): 661–703 https://doi.org/10.1137/070710111
24
J A Coan, D A Sbarra. Social baseline theory: the social regulation of risk and effort. Current Opinion in Psychology, 2015, 1: 87–91 https://doi.org/10.1016/j.copsyc.2014.12.021
25
J Abello, A L Buchsbaum, J Westbrook. A functional approach to external graph algorithms. Algorithmica, 2002, 32(3): 437–458 https://doi.org/10.1007/s00453-001-0088-5
26
S Redner. How popular is your paper? An empirical study of the citation distribution. European Physical Journal B, 1998, 4(2): 131–134 https://doi.org/10.1007/s100510050359
27
H Kwak, C Lee, H Park, S B Moon. What is Twitter, a social network or a news media? In: Proceedings of the 19th International World Wide Web Conferences. 2010, 591–600 https://doi.org/10.1145/1772690.1772751
S Brin, L Page. The anatomy of a large-scale hypertextual Web search engine. In: Proceedings of the 19th International World Wide Web Conferences. 2010, 431–440
30
G Pandurangan, P Raghavan, E Upfal. Using pagerank to characterize Web structure. In: Proceedings of the 8th International Conference on Computing and Combinatorics. 2002, 330–339 https://doi.org/10.1007/3-540-45655-4_36
31
S L Tauro, C R Palmer, G Siganos, M Faloutsos. A simple conceptual model for the Internet topology. In: Proceedings of Global Communications Conference. 2001, 1667–1671 https://doi.org/10.1109/GLOCOM.2001.965863
32
M Faloutsos, P Faloutsos, C Faloutsos. On power-law relationships of the Internet topology. ACM Special Interest Group on Data Communication, 1999, 29(4): 251–262 https://doi.org/10.1145/316188.316229
D J Watts, S H Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 1998, 393(6684): 440–442 https://doi.org/10.1038/30918
35
S Srisaard. Mining the Web: discovering knowledge from hypertext data. Online Information Review, 2003, 27(4): 291
36
C Gkantsidis, M Mihail, E W Zegura. Spectral analysis of Internet topologies. In: Proceedings of the 22nd International Conference on Computer Communications. 2003, 364–374 https://doi.org/10.1109/INFCOM.2003.1208688
37
H Tangmunarunkit, R Govindan, S Jamin, S Shenker, W Willinger. Network topologies, power laws, and hierarchy. ACM Special Interest Group on Data Communication, 2002, 32(1): 76 https://doi.org/10.1145/510726.510750
38
A Casteigts, P Flocchini, W Quattrociocchi, N Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 2012, 27(5): 387–408 https://doi.org/10.1080/17445760.2012.668546
39
N Santoro, W Quattrociocchi, P Flocchini, A Casteigts, F Amblard. 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
W Quattrociocchi, F Amblard, E Galeota. Selection in scientific networks. Social Network Analysis & Mining, 2012, 2(3): 229–237 https://doi.org/10.1007/s13278-011-0043-7
44
J Leskovec, J M Kleinberg, C Faloutsos. 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 https://doi.org/10.1145/1081870.1081893
45
J Leskovec, J M Kleinberg, C Faloutsos. Graph evolution: densification and shrinking diameters. ACM Transactions on Knowledge Discovery From Data, 2007, 1(1): 2 https://doi.org/10.1145/1217299.1217301
46
P Erdos, A Rényi. On the evolution of random graphs. Transactions of the American Mathematical Society, 2011, 286(1): 257–274
47
W Aiello, F Chung, L Lu. A random graph model for massive graphs. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 2000, 171–180 https://doi.org/10.1145/335305.335326
48
M E J Newman, S H Strogatz, D J Watts. Random graphs with arbitrary degree distributions and their applications. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2001, 64(2): 026118 https://doi.org/10.1103/PhysRevE.64.026118
R Albert, A Barabasi. Topology of evolving networks: local events and universality. Physical Review Letters, 2000, 85(24): 5234–5237 https://doi.org/10.1103/PhysRevLett.85.5234
52
J M Kleinberg, R Kumar, P Raghavan, S Rajagopalan, A Tomkins. The Web as a graph: measurements, models, and methods. In: Proceedings of International Computing and Combinatorics Conference. 1999, 1–17 https://doi.org/10.1007/3-540-48686-0_1
53
R Kumar, P Raghavan, S Rajagopalan. Stochastic models for the Web graph. In: Proceedings of the 41st Annual Symosium on Foundations of Computer Science. 2000, 57–65 https://doi.org/10.1109/SFCS.2000.892065
54
S N Dorogovtsev, J F Mendes, A N Samukhin. Structure of growing networks with preferential linking. Physical Review Letters, 2000, 85(21): 4633–4636 https://doi.org/10.1103/PhysRevLett.85.4633
55
Q Chen, H Chang, R Govindan, S Jamin, S Shenker, W Willinger. The origin of power laws in Internet topologies revisited. In: Proceedings of the 51st International Conference on Computer Communications. 2002, 608–617
56
G Bianconi, A L Barabási. Competition and multiscaling in evolving networks. Physics Letters, 2000, 30(1): 37–43
57
A Barabási, H Jeong, Z Néda, E Ravasz, A Schubert, T Vicsek. Evolution of the social network of scientific collaborations. Physica Astatistical Mechanics and Its Applications, 2002, 311(3): 590–614 https://doi.org/10.1016/S0378-4371(02)00736-7
58
W Aiello, F Chung, L Lu. Random evolution in massive graphs. Computer, 2001, 510: 519
59
C Borgs, J Chayes, O Riordan. 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
B M Waxman. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 2002, 6(9): 1617–1622 https://doi.org/10.1109/49.12889
61
M V Looz, C L Staudt, H Meyerhenke, R Prutkin. Fast generation of complex networks with underlying hyperbolic geometry. 2015, arXiv preprint arXiv:1501.03545
62
D Chakrabarti, Y Zhan, C Faloutsos. R-MAT: a recursive model for graph mining. In: Proceedings of the 2004 SIAM International Conference on Data Mining. 2004, 442–446 https://doi.org/10.1137/1.9781611972740.43
63
J Leskovec, C Faloutsos. Scalable modeling of real graphs using kronecker multiplication. In: Proceedings of the 24th International Conference on Machine Learning. 2007, 497–504 https://doi.org/10.1145/1273496.1273559
64
D Dominguez-Sal, P Urbón-Bayes, A Giménez-Vaó, S Gómez-Villamor, N Martínez-Bazan, J Larriba-Pey. 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 https://doi.org/10.1007/978-3-642-16720-1_4
B A Miller, N T Bliss, P J Wolfe. Subgraph detection using eigenvector L1 norms. In: Proceedings of the 23rd International Conference on Neural Information Processing Systems. 2010, 1633–1641
67
B A Miller, L H Stephens, N T Bliss. 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 https://doi.org/10.1109/ICASSP.2012.6288612
68
D J Mir, R N Wright. A differentially private estimator for the stochastic kronecker graph model. In: Proceedings of the 2012 Joint EDBT/ICDT Workshops. 2012, 167–176 https://doi.org/10.1145/2320765.2320818
69
J Leskovec, D Chakrabarti, J M Kleinberg, C Faloutsos, Z Ghahramani. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research, 2010, 11(Feb): 985–1042
70
C Seshadhri, A Pinar, T G Kolda. An in-depth study of stochastic kronecker graphs. In: Proceedings of the 11th IEEE International Conference on Data Mining. 2011, 587–596 https://doi.org/10.1109/ICDM.2011.23
71
A Sala, L Cao, C Wilson, R Zablit, H Zheng, B Y Zhao. Measurementcalibrated graph models for social network experiments. In: Proceedings of the 19th International Conferences onWorldWideWeb. 2010, 861–870
72
L Akoglu, M Mcglohon, C Faloutsos. 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 https://doi.org/10.1109/ICDM.2008.123
73
S L Hakimi. 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
C Seshadhri, T G Kolda, A Pinar. Community structure and scale free collections of Erdös-Rényi graphs. Physical Review E, 2012, 85(5): 056109 https://doi.org/10.1103/PhysRevE.85.056109
75
N Du, H Wang, C Faloutsos. 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 https://doi.org/10.1007/978-3-642-15880-3_31
76
T G Armstrong, V Ponnekanti, D Borthakur, M Callaghan. 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 https://doi.org/10.1145/2463676.2465296
77
T G Kolda, A Pinar, T D Plantenga, C Seshadhri. A scalable generative graph model with community structure. SIAM Journal on Scientific Computing, 2014, 36(5): C424–C452 https://doi.org/10.1137/130914218
78
A Yoo, K Henderson. Parallel generation of massive scale-free graphs. Computer Science, 2010, 7: 123–136
79
M M Alam, M Khan, M V Marathe. 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 https://doi.org/10.1145/2503210.2503291
80
Y C Lo, H Lai, C T Li, S S Lin. Mining and generating large-scaled social networks via MapReduce. Social Network Analysis and Mining, 2013, 3(4): 1449–1469 https://doi.org/10.1007/s13278-013-0124-x
81
A Hadian, S Nobari, B Minaeibidgoli, Q Qu. ROLL: fast in-memory generation of gigantic scale-free networks. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 1829–1842 https://doi.org/10.1145/2882903.2882964
J Cho, H Garciamolina. Estimating frequency of change. ACM Transactions on Internet Technology, 2003, 3(3): 256–290 https://doi.org/10.1145/857166.857170
84
J Cho, H Garciamolina. Synchronizing a database to improve freshness. International Conference on Management of Data, 2000, 29(2): 117–128 https://doi.org/10.1145/342009.335391
85
S Eubank, H Guclu, V S Kumar, M V Marathe, A Srinivasan, Z Toroczkai, N Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 2004, 429(6988): 180–184 https://doi.org/10.1038/nature02541
J G Oliveira, A Barabási. Human dynamics: Darwin and Einstein correspondence patterns. Nature, 2005, 437(7063): 1251 https://doi.org/10.1038/4371251a
88
N Li, N Zhang, T Zhou. Empirical analysis on temporal statistics of human correspondence patterns. Complex System & Complexity Science, 2008, 387(25): 6391–6394 https://doi.org/10.1016/j.physa.2008.07.021
89
W Hong, X P Han, T Zhou, B H Wang. Heavy-tailed statistics in short-message communication. Chinese Physics Letters, 2009, 26(2): 028902 https://doi.org/10.1088/0256-307X/26/2/028902
90
J Candia, M C González, P Wang, T Schoenharl, G Madey, A Barabási. Uncovering individual and collective human dynamics from mobile phone records. Journal of Physics A: Mathematical and Theoretical, 2008, 41(22): 224015 https://doi.org/10.1088/1751-8113/41/22/224015
91
Z Dezsö, E Almaas, A Lukács, B Rácz, I Szakadát, A L Barabási. Dynamics of information access on the Web. Physical Review E, 2006, 73(6): 066132 https://doi.org/10.1103/PhysRevE.73.066132
92
A Vázquez, J G Oliveira, Z Dezsö, K Goh, I Kondor, A Barabási. Modeling bursts and heavy tails in human dynamics. Physical Review E, 2005, 73(2): 036127
93
A Gabrielli, G Caldarelli. Invasion percolation and critical transient in the Barabási Model of human dynamics. Physical Review Letters, 2007, 98(20): 208704 https://doi.org/10.1103/PhysRevLett.98.208701
B Goncalves, J J Ramasco. Human dynamics revealed through Web analytics. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2): 026123 https://doi.org/10.1103/PhysRevE.78.026123
96
R D Malmgren, D B Stouffer, A S L O Campanharo, L A N Amaral. On universality in human correspondence activity. Science, 2009, 325(5948): 1696–1700 https://doi.org/10.1126/science.1174562
97
K C Sia, J Cho, K Hino, Y Chi, S Zhu, B L Tseng. Monitoring RSS feeds based on user browsing pattern. In: Proceedings of International Conference on Weblogs and Social Media. 2007
98
K C Sia, J Cho, H K Cho. Efficient monitoring algorithm for fast news alerts. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(7): 950–961 https://doi.org/10.1109/TKDE.2007.1041
99
D Gruhl, R V Guha, D Liben-Nowell, A Tomkins. Information diffusion through blogspace. In: Proceedings of the 13th International World Wide Web Conferences. 2004, 491–501 https://doi.org/10.1145/988672.988739
100
J Bollen, H Mao, A Pepe. 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
R D Malmgren, D B Stouffer, A E Motter, L A N Amaral. 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
W J Stewart. Probability, Markov Chains, Queues, and Simulation: the Mathematical Basis of Performance Modeling. Princeton: Princeton Univers Press, 2009
104
D M Pennock, G W Flake, S Lawrence, E J Glover, C L Giles. 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
Z Bi, C Faloutsos, F Korn. 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 https://doi.org/10.1145/502512.502521
106
M J Welch, U Schonfeld, D He, J Cho. Topical semantics of twitter links. In: Proceedings of the 4th ACM International Conference on Web Search and Data Mining. 2011, 327–336 https://doi.org/10.1145/1935826.1935882
107
W Galuba, K Aberer, D Chakraborty, Z Despotovic, W Kellerer. Outtweeting the twitterers — predicting information cascades in microblogs. In: Proceedings of the 3rd Conference on Online Social Networks. 2010, 3–11
108
S Asur, B A Huberman. Predicting the future with social media. In: Proceedings of the 2010 IEEE International Conference on Web Intelligence and Intelligent Agent Technology. 2010, 492–499 https://doi.org/10.1109/WI-IAT.2010.63
109
T Martin, B Ball, B Karrer, M E J Newman. Coauthorship and citation in scientific publishing. 2013, arXiv preprint arXiv:1304.0473
110
J Xie, C Zhang, M Wu. Modeling microblogging communication based on human dynamics. In: Proceedings of the 8th International Conference on Fuzzy Systems and Knowledge Discovery. 2011, 2290–2294 https://doi.org/10.1109/FSKD.2011.6020045
