ABSTRACT
Dynamic graphs are an essential tool for representing a wide variety of concepts that change over time. Examples include modeling the evolution of relationships and communities in a social network or tracking the activity of users within an enterprise computer network. In the case of static graph representations, random graph models are often useful for analyzing and predicting the characteristics of a given network. Even though random dynamic graph models are a trending research topic, the field is still relatively unexplored. The selection of available models is limited and manually developing a model for a new application can be difficult and time-consuming. This work leverages hyper-heuristic techniques to automate the design of novel random dynamic graph models. A genetic programming approach is used to evolve custom heuristics that emulate the behavior of a variety of target models with high accuracy. Results are presented that illustrate the potential for the automated design of custom random dynamic graph models.
- Viplove Arora and Mario Ventresca. 2017. Action-based Modeling of Complex Networks. Scientific Reports 7, 1 (2017), 66--73.Google ScholarCross Ref
- Alexander Bailey, Mario Ventresca, and Beatrice Ombuki-Berman. 2014. Genetic Programming for the Automatic Inference of Graph Models for Complex Networks. IEEE Transactions on Evolutionary Computation 18, 3 (2014), 405--419.Google ScholarCross Ref
- L. Boratto, S. Carta, A. Chessa, M. Agelli, and M. L. Clemente. 2009. Group Recommendation with Automatic Identification of Users Communities. In 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, Vol. 3. 547--550. Google ScholarDigital Library
- Edmund K. Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu. 2013. Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society 64, 12 (2013), 1695--1724.Google ScholarCross Ref
- Paul Erdős and Alfréd Rényi. 1959. On random graphs I. Publ. Math. Debrecen 6 (1959), 290--297.Google ScholarCross Ref
- Paul Erdős and Alfréd Rényi. 1960. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl 5 (1960), 17--61.Google Scholar
- Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. 2004. Modelling Disease Outbreaks in Realistic Urban Social Networks. Nature 429, 6988 (2004), 180.Google Scholar
- Kyle Robert Harrison. 2014. Network Similarity Measures and Automatic Construction of Graph Models using Genetic Programming. Master's thesis. Brock University.Google Scholar
- Kyle Robert Harrison, Mario Ventresca, and Beatrice M. Ombuki-Berman. 2016. A meta-analysis of centrality measures for comparing and generating complex network models. Journal of Computational Science 17 (2016), 205 -- 215.Google ScholarCross Ref
- Petter Holme and Jari SaramÃd'ki. 2012. Temporal networks. Physics Reports 519, 3 (2012), 97--125.Google ScholarCross Ref
- John R. Koza. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA. Google ScholarDigital Library
- M. R. Medland, K. R. Harrison, and B. M. Ombuki-Berman. 2016. Automatic Inference of Graph Models for Directed Complex Networks using Genetic Programming. In 2016 IEEE Congress on Evolutionary Computation (CEC). 2337--2344.Google Scholar
- Telmo Menezes and Camille Roth. 2014. Symbolic Regression of Generative Network Models. Scientific reports 4 (2014), 6284.Google Scholar
- Henning Meyerhenke. 2013. Shape optimizing load balancing for MPI-parallel adaptive numerical simulations. Proceedings of the 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering (2013), 67--82.Google ScholarCross Ref
- David J. Montana. 1995. Strongly Typed Genetic Programming. Evolutionary Computation 3, 2 (June 1995), 199--230. Google ScholarDigital Library
- Mark Newman. 2010. Networks: An Introduction. Oxford Univ. Press, New York, NY, USA. Google ScholarCross Ref
- M. E. J. Newman, S. H. Strogatz, and D. J. Watts. 2001. Random graphs with arbitrary degree distributions and their applications. Physical Review E 64 (Aug. 2001), 026118. Issue 2.Google Scholar
- Aaron S. Pope, Daniel R. Tauritz, and Alexander D. Kent. 2016. Evolving Random Graph Generators: A Case for Increased Algorithmic Primitive Granularity. In 2016 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 1--8.Google Scholar
- Melissa J. M. Turcotte, Alexander D. Kent, and Curtis Hash. 2018. Unified Host and Network Data Set. World Scientific, Chapter Chapter 1, 1--22.Google Scholar
- Yu Wang, Aniket Chakrabarti, David Sivakoff, and Srinivasan Parthasarathy. 2017. Fast Change Point Detection on Dynamic Social Networks. CoRR abs/1705.07325 (2017), 1--8. arXiv: 1705.07325 http://arxiv.org/abs/1705.07325 Google ScholarDigital Library
- Xiao Zhang, Cristopher Moore, and Mark E. J. Newman. 2017. Random Graph Models for Dynamic Networks. The European Physical Journal B 90, 10 (18 Oct 2017), 200.Google ScholarCross Ref
Index Terms
- Automated design of random dynamic graph models
Recommendations
Automated design of random dynamic graph models for enterprise computer network applications
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference CompanionDynamic graphs are an essential tool for representing a wide variety of concepts that change over time. In the case of static graph representations, random graph models are often useful for analyzing and predicting the characteristics of a given ...
Dynamic graph models
Research in graph theory has focused on studying the structure of graphs with the assumption that they are static. However, in many applications, the graphs that arise change with time, i.e., they are dynamic in nature. This is especially true of ...
A survey on dynamic graph processing on GPUs: concepts, terminologies and systems
AbstractGraphs that are used to model real-world entities with vertices and relationships among entities with edges, have proven to be a powerful tool for describing real-world problems in applications. In most real-world scenarios, entities and their ...
Comments