sGrow: Explaining the Scale-Invariant Strength Assortativity of Streaming Butterflies
Article No.: 24, Pages 1 - 46
Abstract
Bipartite graphs are rich data structures with prevalent applications and characteristic structural features. However, less is known about their growth patterns, particularly in streaming settings. Current works study the patterns of static or aggregated temporal graphs optimized for certain downstream analytics or ignoring multipartite/non-stationary data distributions, emergence patterns of subgraphs, and streaming paradigms. To address these, we perform statistical network analysis over web log streams and identify the governing patterns underlying the bursty emergence of mesoscopic building blocks, 2, 2-bicliques, leading to a phenomenon that we call scale-invariant strength assortativity of streaming butterflies. We provide the graph-theoretic explanation of this phenomenon. We further introduce a set of micro-mechanics in the body of a streaming growth algorithm, sGrow, to pinpoint the generative origins. sGrow supports streaming paradigms, emergence of four-vertex graphlets, and provides user-specified configurations for the scale, burstiness, level of strength assortativity, probability of out-of-order records, generation time, and time-sensitive connections. Comprehensive evaluations on pattern reproducing and stress testing validate the effectiveness, efficiency, and robustness of sGrow in realization of the observed patterns independent of initial conditions, scale, temporal characteristics, and model configurations. Theoretical and experimental analysis verify sGrow’s robustness in generating streaming graphs based on user-specified configurations that affect the scale and burstiness of the stream, level of strength assortativity, probability of out-of-order streaming records, generation time, and time-sensitive connections.
References
[1]
Rezwan Ahmed and George Karypis. 2015. Algorithms for mining the coevolving relational motifs in dynamic networks. ACM Transactions on Knowledge Discovery from Data 10, 1 (2015), 1–31.
[2]
Leman Akoglu and Christos Faloutsos. 2009. RTG: A recursive realistic graph generator using random typing. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 13–28.
[3]
Leman Akoglu, Mary McGlohon, and Christos Faloutsos. 2008. RTM: Laws and a recursive generator for weighted time-evolving graphs. In Proceedings of the 8th IEEE International Conference on Data Mining. 701–706.
[4]
Leman Akoglu, Mary McGlohon, and Christos Faloutsos. 2010. Oddball: Spotting anomalies in weighted graphs. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining. 410–421.
[5]
Sinan G. Aksoy, Cliff Joslyn, Carlos Ortiz Marrero, Brenda Praggastis, and Emilie Purvine. 2020. Hypernetwork science via high-order hypergraph walks. EPJ Data Science 9, 1 (2020), 16.
[6]
Sinan G. Aksoy, Tamara G. Kolda, and Ali Pinar. 2017. Measuring and modeling bipartite graphs with community structure. Journal of Complex Networks 5, 4 (2017), 581–603.
[7]
Marie Al-Ghossein, Talel Abdessalem, and Anthony Barré. 2021. A survey on stream-based recommender systems. ACM Computing Surveys 54, 5 (2021), 1–36.
[8]
Réka Albert and Albert-László Barabási. 2002. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 1 (2002), 47.
[9]
Albert-László Barabási. 2005. The origin of bursts and heavy tails in human dynamics. Nature 435, 7039 (2005), 207–211.
[10]
Sadegh Aliakbary, Jafar Habibi, and Ali Movaghar. 2014. Quantification and comparison of degree distributions in complex networks. In Proceedings of the 7th International Symposium on Telecommunications. 464–469.
[11]
Güneş Aluç, Olaf Hartig, M. Tamer Özsu, and Khuzaima Daudjee. 2014. Diversified stress testing of RDF data management systems. In Proceedings of the 13th International Semantic Web Conference.197–212.
[12]
Khaled Ammar and M. Tamer Özsu. 2013. WGB: Towards a universal graph benchmark. In Advancing Big Data Benchmarks. Lecture Notes in Computer Science, Vol. 8585. Springer, 58–72.
[13]
Naomi A. Arnold, Raul J. Mondragón, and Richard G. Clegg. 2021. Likelihood-based approach to discriminate mixtures of network models that vary in time. Scientific Reports 11, 1 (2021), 1–13.
[14]
Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509–512.
[15]
Michael J. Barber. 2007. Modularity and community detection in bipartite networks. Physical Review E 76, 6 (2007), 066102.
[16]
Alain Barrat, Marc Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. 2004. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences 101, 11 (2004), 3747–3752.
[17]
Alain Barrat, Marc Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. 2004. Weighted evolving networks: Coupling topology and weight dynamics. Physical Review Letters 92, 22 (2004), 228701–228704.
[18]
Alain Barrat, Marc Barthélemy, and Alessandro Vespignani. 2004. Modeling the evolution of weighted networks. Physical Review E 70, 6 (2004), 066149.
[19]
Austin R. Benson, David F. Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163–166.
[20]
Ginestra Bianconi and A.-L. Barabási. 2011. Competition and multiscaling m evolving networks. In The Structure and Dynamics of Networks. Princeton University Press, Princeton, NJ, 361–367.
[21]
Angela Bonifati, George Fletcher, Jan Hidders, and Alexandru Iosup. 2018. A survey of benchmarks for graph-processing systems. In Graph Data Management. Data-Centric Systems and Applications. Springer, 163–186.
[22]
Angela Bonifati, Irena Holubová, Arnau Prat-Pérez, and Sherif Sakr. 2020. Graph generators: State of the art and open challenges. ACM Computing Surveys 53, 2 (2020), 1–30.
[23]
Guilherme O. Campos, Arthur Zimek, Jörg Sander, Ricardo J. G. B. Campello, Barbora Micenková, Erich Schubert, Ira Assent, and Michael E. Houle. 2016. On the evaluation of unsupervised outlier detection: Measures, datasets, and an empirical study. Data Mining and Knowledge Discovery 30, 4 (2016), 891–927.
[24]
Deepayan Chakrabarti and Christos Faloutsos. 2006. Graph mining: Laws, generators, and algorithms. ACM Computing Surveys 38, 1 (2006), 2–es.
[25]
Lijun Chang, Jeffrey Xu Yu, Lu Qin, Hong Cheng, and Miao Qiao. 2012. The exact distance to destination in undirected world. VLDB Journal 21, 6 (2012), 869–888.
[26]
Vittoria Colizza, Alessandro Flammini, M. Angeles Serrano, and Alessandro Vespignani. 2006. Detecting rich-club ordering in complex networks. Nature Physics 2, 2 (2006), 110–115.
[27]
Colin Cooper and Alan Frieze. 2003. A general model of web graphs. Random Structures & Algorithms 22, 3 (2003), 311–335.
[28]
Peter Csermely, András London, Ling-Yun Wu, and Brian Uzzi. 2013. Structure and dynamics of core/periphery networks. Journal of Complex Networks 1, 2 (2013), 93–123.
[29]
Gregorio D’Agostino, Antonio Scala, Vinko Zlatić, and Guido Caldarelli. 2012. Robustness and assortativity for diffusion-like processes in scale-free networks. Europhysics Letters 97, 6 (2012), 68006.
[30]
Manh Tuan Do, Se-Eun Yoon, Bryan Hooi, and Kijung Shin. 2020. Structural patterns and generative models of real-world hypergraphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 176–186.
[31]
Zheng Dong, Xin Huang, Guorui Yuan, Hengshu Zhu, and Hui Xiong. 2021. Butterfly-core community search over labeled graphs. Proceedings of the VLDB Endowment 14, 11, 2006–2018.
[32]
Sergey N. Dorogovtsev and José F. F. Mendes. 2001. Scaling properties of scale-free evolving networks: Continuous approach. Physical Review E 63, 5 (2001), 056125.
[33]
Mikhail Drobyshevskiy and Denis Turdakov. 2019. Random graph modeling: A survey of the concepts. ACM Computing Surveys 52, 6 (2019), 1–36.
[34]
Gideon Dror, Noam Koenigstein, Yehuda Koren, and Markus Weimer. 2012. The Yahoo! music dataset and KDD-Cup’11. In Proceedings of KDD-Cup 2011. 3–18.
[35]
Andrew F. Emmott, Shubhomoy Das, Thomas Dietterich, Alan Fern, and Weng-Keen Wong. 2013. Systematic construction of anomaly detection benchmarks from real data. In Proceedings of the ACM SIGKDD Workshop on Outlier Detection and Description. 16–21.
[36]
Yixiang Fang, Kai Wang, Xuemin Lin, and Wenjie Zhang. 2021. Cohesive subgraph search over big heterogeneous information networks: Applications, challenges, and solutions. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 2829–2838.
[37]
Frank Fischer and Christoph Helmberg. 2014. Dynamic graph generation for the shortest path problem in time expanded networks. Mathematical Programming 143, 1 (2014), 257–297.
[38]
Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, and Johan Ugander. 2018. Configuring random graph models with fixed degree sequences. SIAM Review 60, 2 (2018), 315–355.
[39]
Dan Frankowski, Shyong K. Lam, Shilad Sen, F. Maxwell Harper, Scott Yilek, Michael Cassano, and John Riedl. 2007. Recommenders everywhere: The WikiLens community-maintained recommender system. In Proceedings of the International Symposium on Wikis. 47–60.
[40]
João Gama, Indrė Žliobaitė, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. 2014. A survey on concept drift adaptation. ACM Computing Surveys 46, 4 (2014), 1–37.
[41]
Michelle Girvan and Mark E. J. Newman. 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 12 (2002), 7821–7826.
[42]
Lukasz Golab and M. Tamer Özsu. 2010. Data stream management. Synthesis Lectures on Data Management 2, 1 (2010), 1–73.
[43]
Robert Görke, Roland Kluge, Andrea Schumm, Christian Staudt, and Dorothea Wagner. 2012. An efficient generator for clustered dynamic random networks. In Proceedings of the Mediterranean Conference on Algorithms. 219–233.
[44]
Jelena Grujic, Marija Mitrovic, and Bosiljka Tadic. 2009. Mixing patterns and communities on bipartite graphs on web-based social interactions. In Proceedings of the 16th International Conference on Digital Signal Processing. 1–8.
[45]
Xianbin Gu, Jeremiah D. Deng, and Martin K. Purvis. 2014. Superpixel-based segmentation using multi-layer bipartite graphs and Grassmann manifolds. In Proceedings of the 29th International Conference on Image and Vision Computing New Zealand. 119–123.
[46]
Jean-Loup Guillaume and Matthieu Latapy. 2004. Bipartite structure of all complex networks. Information Processing Letters 90, 5 (2004), 215–221.
[47]
Jean-Loup Guillaume and Matthieu Latapy. 2006. Bipartite graphs as models of complex networks. Physica A: Statistical Mechanics and Its Applications 371, 2 (2006), 795–813.
[48]
Roger Guimerà, Marta Sales-Pardo, and Luís A. Nunes Amaral. 2007. Module identification in bipartite and directed networks. Physical Review E 76, 3 (2007), 036102.
[49]
Guibing Guo, Jie Zhang, Daniel Thalmann, and Neil Yorke-Smith. 2014. ETAF: An extended trust antecedents framework for trust prediction. In Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 540–547.
[50]
Ali Hadian, Sadegh Nobari, Behrooz Minaei-Bidgoli, and Qiang Qu. 2016. ROLL: Fast in-memory generation of gigantic scale-free networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1829–1842.
[51]
Yang Hao, Mengqi Zhang, Xiaoyang Wang, and Chen Chen. 2020. Cohesive subgraph detection in large bipartite networks. In Proceedings of the 32nd International Conference on Scientific and Statistical Database Management. 1–4.
[52]
F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens datasets: History and context. ACM Transactions on Interactive Intelligent Systems 5, 4 (2015), 1–19.
[53]
Jonathan L. Herlocker, Joseph A. Konstan, Al Borchers, and John Riedl. 2017. An algorithmic framework for performing collaborative filtering. ACM SIGIR Forum 51 (2017), 227–234.
[54]
Petter Holme. 2005. Core-periphery organization of complex networks. Physical Review E 72, 4 (2005), 046111.
[55]
Jiafeng Hu, Reynold Cheng, Kevin Chen-Chuan Chang, Aravind Sankar, Yixiang Fang, and Brian Y. H. Lam. 2019. Discovering maximal motif cliques in large heterogeneous information networks. In Proceedings of the 35th International Conference on Data Engineering. IEEE, Los Alamitos, CA, 746–757.
[56]
Jiewen Huang and Daniel J. Abadi. 2016. Leopard: Lightweight edge-oriented partitioning and replication for dynamic graphs. Proceedings of the VLDB Endowment 9, 7 (2016), 540–551.
[57]
Shuta Ito and Takayasu Fushimi. 2020. Fast clustering of hypergraphs based on bipartite-edge restoration and node reachability. In Proceedings of the 22nd International Conference on Information Integration and Web-Based Applications and Services. 115–124.
[58]
Mohsen Jamali, Gholamreza Haffari, and Martin Ester. 2011. Modeling the temporal dynamics of social rating networks using bidirectional effects of social relations and rating patterns. In Proceedings of the 20th International World Wide Web Conference.527–536.
[59]
Jun Ji, Aifen Fang, Chenlu Qiu, and Lei Zhao. 2018. Detection of abnormal database queries in weighted bipartite graph. In Proceedings of the International Conference on Big Data Engineering and Technology. 7–11.
[60]
Ruoming Jin, Hui Hong, Haixun Wang, Ning Ruan, and Yang Xiang. 2010. Computing label-constraint reachability in graph databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 123–134.
[61]
Nitin Jindal and Bing Liu. 2008. Opinion spam and analysis. In Proceedings of the International Conference on Web Search and Web Data Mining. 219–230.
[62]
Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew S. Tomkins. 1999. The web as a graph: Measurements, models, and methods. In Proceedings of the Computing and Combinatorics Conference.1–17.
[63]
Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. 2011. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment 2011, 11 (2011), P11005.
[64]
Pavel L. Krapivsky and Sidney Redner. 2005. Network growth by copying. Physical Review E 71, 3 (2005), 036118.
[65]
Pavel L. Krapivsky, Geoff J. Rodgers, and Sidney Redner. 2001. Degree distributions of growing networks. Physical Review Letters 86, 23 (2001), 5401.
[66]
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, and Eli Upfal. 2000. Stochastic models for the web graph. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. 57–65.
[67]
Jérôme Kunegis. 2013. Konect: The Koblenz network collection. In Proceedings of the 22nd International World Wide Web Conference.1343–1350.
[68]
Matthieu Latapy, Clémence Magnien, and Nathalie Del Vecchio. 2008. Basic notions for the analysis of large two-mode networks. Social Networks 30, 1 (2008), 31–48.
[69]
Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. 2008. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 462–470.
[70]
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 177–187.
[71]
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data 1, 1 (2007), 2–es.
[72]
C. C. Leung and H. F. Chau. 2007. Weighted assortative and disassortative networks model. Physica A: Statistical Mechanics and Its Applications 378, 2 (2007), 591–602.
[73]
Xiaodong Li, Reynold Cheng, Kevin Chen-Chuan Chang, Caihua Shan, Chenhao Ma, and Hongtai Cao. 2021. On analyzing graphs with motif-paths. Proceedings of the VLDB Endowment 14, 6, 1111–1123.
[74]
Ee-Peng Lim, Viet-An Nguyen, Nitin Jindal, Bing Liu, and Hady Wirawan Lauw. 2010. Detecting product review spammers using rating behaviors. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 939–948.
[75]
Kun Liu and Evimaria Terzi. 2008. Towards identity anonymization on graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 93–106.
[76]
Paul Liu, Austin R. Benson, and Moses Charikar. 2019. Sampling methods for counting temporal motifs. In Proceedings of the 12th ACM International Conference on Web Search and Data Mining. 294–302.
[77]
Weide Liu, Chi Zhang, Guosheng Lin, Tzu-Yi Hung, and Chunyan Miao. 2020. Weakly supervised segmentation with maximum bipartite graph matching. In Proceedings of the 28th ACM International Conference on Multimedia. 2085–2094.
[78]
Chenhao Ma, Reynold Cheng, Laks V. S. Lakshmanan, Tobias Grubenmann, Yixiang Fang, and Xiaodong Li. 2019. LINC: A motif counting algorithm for uncertain graphs. Proceedings of the VLDB Endowment 13, 2 (2019), 155–168.
[79]
Mary McGlohon, Leman Akoglu, and Christos Faloutsos. 2008. Weighted graphs and disconnected components: Patterns and a generator. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 524–532.
[80]
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (2002), 824–827.
[81]
Jayanta Mondal and Amol Deshpande. 2012. Managing large dynamic graphs efficiently. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 145–156.
[82]
Arjun Mukherjee, Bing Liu, and Natalie Glance. 2012. Spotting fake reviewer groups in consumer reviews. In Proceedings of the 21st International World Wide Web Conference.191–200.
[83]
Mark E. J. Newman. 2002. Assortative mixing in networks. Physical Review Letters 89, 20 (2002), 208701.
[84]
Mark E. J. Newman and Juyong Park. 2003. Why social networks are different from other types of networks. Physical Review E 68, 3 (2003), 036122.
[85]
Mark E. J. Newman, Steven H. Strogatz, and Duncan J. Watts. 2001. Random graphs with arbitrary degree distributions and their applications. Physical Review E 64, 2 (2001), 026118.
[86]
Rogier Noldus and Piet Van Mieghem. 2015. Assortativity in complex networks. Journal of Complex Networks 3, 4 (2015), 507–542.
[87]
M. Tamer Özsu and Patrick Valduriez. 2019. Big data processing. In Principles of Distributed Database Systems (4th ed.). Springer, 449–518.
[88]
M. Tamer Özsu and Patrick Valduriez. 2019. Stream data management. In Principles of Distributed Database Systems (4th ed.). Springer, 470–485.
[89]
Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. 2017. Motifs in temporal networks. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining. 601–610.
[90]
Deokhwan Park, Joosoon Lee, Junseok Lee, and Kyoobin Lee. 2021. Deep learning based food instance segmentation using synthetic data. In Proceedings of the 2021 18th International Conference on Ubiquitous Robots (UR’21). 499–505.
[91]
Himchan Park and Min-Soo Kim. 2021. LineageBA: A fast, exact and scalable graph generation for the Barabási-Albert model. In Proceedings of the 37th International Conference on Data Engineering. 540–551.
[92]
Romualdo Pastor-Satorras, Alexei Vázquez, and Alessandro Vespignani. 2001. Dynamical and correlation properties of the Internet. Physical Review Letters 87, 25 (2001), 258701.
[93]
Tiago P. Peixoto. 2020. The Netzschleuder Network Catalogue and Repository. Retrieved October 2021 from https://networks.skewed.de.
[94]
Sumit Purohit, Lawrence B. Holder, and George Chin. 2018. Temporal graph generation based on a distribution of temporal motifs. In Proceedings of the 14th International Workshop on Mining and Learning with Graphs, Vol. 7.
[95]
Jérémie Rappaz, Julian McAuley, and Karl Aberer. 2021. Recommendation on live-streaming platforms: Dynamic availability and repeat consumption. Interactions 20 (2021), 40.
[96]
Ryan A. Rossi, Nesreen K. Ahmed, Aldo Carranza, David Arbour, Anup Rao, Sungchul Kim, and Eunyee Koh. 2020. Heterogeneous graphlets. ACM Transactions on Knowledge Discovery from Data 15, 1 (2020), 1–43.
[97]
Aida Sheshbolouki and M. Tamer Özsu. 2022. sGrapp: Butterfly approximation in streaming graphs. ACM Transactions on Knowledge Discovery from Data 16, 4 (2022), 1–43.
[98]
Aida Sheshbolouki, Mina Zarei, and Hamid Sarbazi-Azad. 2015. Are feedback loops destructive to synchronization? Europhysics Letters 111, 4 (2015), 40010.
[99]
Yook Soon-Hyung, Hawoong Jeong, Albert-Laszlo Barabási, and Yuhai Tu. 2001. Weighted evolving networks. Physical Review Letters 86, 25 (2001), 5835–5838.
[100]
Isabelle Stanton and Ali Pinar. 2012. Constructing and sampling graphs with a prescribed joint degree distribution. Journal of Experimental Algorithmics 17 (2012), Article 3.5, 25 pages.
[101]
Jianing Sun, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, Xiuqiang He, Chen Ma, and Mark Coates. 2020. Neighbor interaction aware graph convolution networks for recommendation. In Proceedings of the 43rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 1289–1298.
[102]
Zeeshan Syed, Collin Stultz, Manolis Kellis, Piotr Indyk, and John Guttag. 2010. Motif discovery in physiological datasets: A methodology for inferring predictive elements. ACM Transactions on Knowledge Discovery from Data 4, 1 (2010), 1–23.
[103]
Jiliang Tang, Huiji Gao, Huan Liu, and Atish Das Sarma. 2012. eTrust: Understanding trust evolution in an online world. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 253–261.
[104]
Yu Ting, Cao Yan, and Mu Xiang-Wei. 2013. Personalized recommendation system based on web log mining and weighted bipartite graph. In Proceedings of the 2013 International Conference on Computational and Information Sciences. 587–590.
[105]
Stojan Trajanovski, Javier Martín-Hernández, Wynand Winterbach, and Piet Van Mieghem. 2013. Robustness envelopes of networks. Journal of Complex Networks 1, 1 (2013), 44–62.
[106]
Katherine Van Koevering, Austin R. Benson, and Jon Kleinberg. 2021. Random graphs with prescribed k-core sequences: A new null model for network analysis. arXiv preprint arXiv:2102.12604 (2021).
[107]
Demival Vasques Filho and Dion R. J. O’Neale. 2018. Degree distributions of bipartite networks and their projections. Physical Review E 98, 2 (2018), 022307.
[108]
Demival Vasques Filho and Dion R. J. O’Neale. 2020. Transitivity and degree assortativity explained: The bipartite structure of social networks. Physical Review E 101, 5 (2020), 052305.
[109]
Alexei Vazquez. 2000. Knowing a network by walking on it: Emergence of scaling. arXiv preprint cond-mat/0006132 (2000).
[110]
Alexei Vázquez. 2003. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Physical Review E 67, 5 (2003), 056104.
[111]
Andrew Z. Wang, Rex Ying, Pan Li, Nikhil Rao, Karthik Subbian, and Jure Leskovec. 2021. Bipartite dynamic representations for abuse detection. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 3638–3648.
[112]
Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2019. Vertex priority based butterfly counting for large-scale bipartite networks. Proceedings of the VLDB Endowment 12, 10 (2019), 1139–1152.
[113]
Wei Wang, Furu Wei, Wenjie Li, and Sujian Li. 2009. Hypersum: Hypergraph based semi-supervised sentence ranking for query-oriented summarization. In Proceedings of the 18th ACM International Conference on Information and Knowledge Management. 1855–1858.
[114]
Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of ‘small-world’networks. Nature 393, 6684 (1998), 440.
[115]
Anatol Wegner. 2011. Random graphs with motifs. https://www.mis.mpg.de/preprints/2011/preprint2011_61.pdf.
[116]
Yinwei Wei, Xiang Wang, Liqiang Nie, Xiangnan He, Richang Hong, and Tat-Seng Chua. 2019. MMGCN: Multi-modal graph convolution network for personalized recommendation of micro-video. In Proceedings of the 27th ACM International Conference on Multimedia. 1437–1445.
[117]
Guangyu Wu, Martin Harrigan, and Pádraig Cunningham. 2011. Characterizing Wikipedia pages using edit network motif profiles. In Proceedings of the 3rd International Workshop on Search and Mining User-Generated Contents. 45–52.
[118]
Shengqi Yang, Xifeng Yan, Bo Zong, and Arijit Khan. 2012. Towards effective partition management for large graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 517–528.
[119]
Josh Jia-Ching Ying, Ji Zhang, Che-Wei Huang, Kuan-Ta Chen, and Vincent S. Tseng. 2018. FrauDetector+: An incremental graph-mining approach for efficient fraudulent phone call detection. ACM Transactions on Knowledge Discovery from Data 12, 6 (2018), 1–35.
[120]
Giselle Zeno, Timothy La Fond, and Jennifer Neville. 2021. DYMOND: DYnamic MOtif-NoDes network generative model. In Proceedings of the Web Conference 2021. 718–729.
[121]
Yang Zhang. 2019. Language in our time: An empirical analysis of hashtags. In Proceedings of the 28th International World Wide Web Conference.2378–2389.
[122]
Lingxiao Zhao and Leman Akoglu. 2020. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. arXiv preprint arXiv:2012.12931 (2020).
[123]
Yi Zheng, Hongchao Qin, Jun Zheng, Fusheng Jin, and Rong-Hua Li. 2020. Butterfly-based higher-order clustering on bipartite networks. In Proceedings of the International Conference on Knowledge Science, Engineering, and Management. 485–497.
[124]
Zheng Zhong, Shen Yan, Zikun Li, Decheng Tan, Tong Yang, and Bin Cui. 2021. BurstSketch: Finding bursts in data streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 2375–2383.
[125]
Dawei Zhou, Lecheng Zheng, Jiawei Han, and Jingrui He. 2020. A data-driven graph generative model for temporal interaction networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 401–411.
[126]
Shi Zhou and Raúl J. Mondragón. 2004. The rich-club phenomenon in the Internet topology. IEEE Communications Letters 8, 3 (2004), 180–182.
[127]
Tao Zhou, Jie Ren, Matúš Medo, and Yi-Cheng Zhang. 2007. Bipartite network projection and personal recommendation. Physical Review E 76, 4 (2007), 046115.
[128]
Qiuyu Zhu, Jiahong Zheng, Hao Yang, Chen Chen, Xiaoyang Wang, and Ying Zhang. 2020. Hurricane in bipartite graphs: The lethal nodes of butterflies. In Proceedings of the 32nd International Conference on Scientific and Statistical Database Management. 1–4.
[129]
Yong Zou, Reik V. Donner, Norbert Marwan, Jonathan F. Donges, and Jürgen Kurths. 2019. Complex network approaches to nonlinear time series analysis. Physics Reports 787 (2019), 1–97.
Index Terms
- sGrow: Explaining the Scale-Invariant Strength Assortativity of Streaming Butterflies
Recommendations
Spanners of Hypercube-Derived Networks
A spanning subgraph $G'$ of a simple undirected graph $G$ is a t-spanner of $G$ if every pair of vertices that are adjacent in $G$ are at distance at most $t$ in $G'$. The parameter $t$ is called the dilation of the spanner. Spanners with small ...
Scale invariant learning from trapezoidal data streams
SAC '20: Proceedings of the 35th Annual ACM Symposium on Applied ComputingTrapezoidal data streams pervasively exist in many applications, where the number of features keeps increasing over time with the continuous arrival of new instances. Extensive learning solutions on such data streams with a doubly streaming nature make ...
PSoup: a system for streaming queries over streaming data
Abstract.Recent work on querying data streams has focused on systems where newly arriving data is processed and continuously streamed to the user in real time. In many emerging applications, however, ad hoc queries and/or intermittent connectivity also ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2023
302 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 May 2023
Online AM: 14 December 2022
Accepted: 20 October 2022
Revised: 08 August 2022
Received: 13 January 2022
Published in TWEB Volume 17, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Natural Sciences and Engineering Research Council (NSERC) of Canada
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 298Total Downloads
- Downloads (Last 12 months)131
- Downloads (Last 6 weeks)7
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in