Interactive Random Graph Generation with Evolutionary Algorithms

Bach, Benjamin and Spritzer, Andre and Lutton, Evelyne and Fekete, Jean-Daniel (2013) Interactive Random Graph Generation with Evolutionary Algorithms. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 541-552 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_48).

Full text not available from this repository.

Abstract

This paper introduces an interactive system called GraphCuisine that lets users steer an Evolutionary Algorithm (EA) to create random graphs that match user-specified measures. Generating random graphs with particular characteristics is crucial for evaluating graph algorithms, layouts and visualization techniques. Current random graph generators provide limited control of the final characteristics of the graphs they generate. The situation is even harder when one wants to generate random graphs similar to a given one, all-in-all leading to a long iterative process that involves several steps of random graph generation, parameter changes, and visual inspection. Our system follows an approach based on interactive evolutionary computation. Fitting generator parameters to create graphs with pre-defined measures is an optimization problem, while assessing the quality of the resulting graphs often involves human subjective judgment. In this paper we describe the graph generation process from a user’s perspective, provide details about our evolutionary algorithm, and demonstrate how GraphCuisine is employed to generate graphs that mimic a given real-world network. An interactive demo of GraphCuisine can be found on our website http://www.aviz.fr/Research/Graphcuisine .

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_48
Classifications:S Software and Systems > S.999 Others
ID Code:1341

Repository Staff Only: item control page

References

Aiello, W., Chung, F., Lu, L.: A Random Graph Model for Power Law Graphs. Experimental Mathematics 10(1), 53–66 (2001)

Albuquerque, G., Löwe, T., Magnor, M.: Synthetic Generation of High-Dimensional Datasets. IEEE Transactions on Visualization and Computer Graphics 17(12), 2317–2324 (2011)

Barabási, A.L., Albert, R.: Emergence of Scaling in Random Networks. Science 286(5439), 509–512 (1999)

Berger, N., Borgs, C., Chayes, J.T., D’Souza, R.M., Kleinberg, R.D.: Competition-Induced Preferential Attachment. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 208–221. Springer, Heidelberg (2004)

Biedl, T., Marks, J., Ryall, K., Whitesides, S.: Graph Multidrawing: Finding Nice Drawings Without Defining Nice. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 347–355. Springer, Heidelberg (1998)

Calvert, K., Doar, M., Zegura, E.: Modeling Internet Topology. IEEE Communications Magazine 35(6), 160–163 (1997)

Carlson, J.M., Doyle, J.: Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems. Physical Review E 60, 1412–1427 (1999)

Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: A Recursive Model for Graph Mining. In: Proc. SIAM International Conference on Data Mining (2004)

Doar, M.: A better Model for Generating Test Networks. In: Proc. Global Telecommunications Conference, pp. 86–93 (1996)

Eppstein, D., Wang, J.: A Steady State Model for Graph Power Laws. In: 2nd International Workshop on Web Dynamics (2002)

Erdös, P., Rényi, A.: On Random Graphs. Publicationes Mathematicae 6, 290–297 (1959)

Fabrikant, A., Koutsoupias, E., Papadimitriou, C.H.: Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 110–122. Springer, Heidelberg (2002)

Frank, O., Strauss, D.: Markov Graphs. Journal of the American Statistical Association 81(395), 832–842 (1986)

Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning, 1st edn. Addison-Wesley Longman Publishing Co., Inc., Boston (1989)

Gruau, F.: Neural Network Synthesis using Cellular Encoding and Genetic Algorithms. Ph.D. thesis, Laboratoire de l’Informatique du Parallelisme, Ecole Normale Superieure de Lyon, France (1994)

Kitano, H.: Designing Neural Networks Using Genetic Algorithms with Graph Generation System. Complex Systems 4, 461–476 (1990)

Kleinberg, J.: Navigation in a Small World - It is easier to find Short Chains between Points in some Networks than Others. Nature 406(6798), 845–845 (2000)

Medina, A., Matta, I., Byers, J.: On the Origin of Power Laws in Internet Topologies. SIGCOMM Comput. Commun. Rev. 30(2), 18–28 (2000)

Pandurangan, G., Raghavan, P., Upfal, E.: Using PageRank to Characterize Web Structure. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 330–339. Springer, Heidelberg (2002)

Stanley, K., Miikkulainen, R.: Evolving Neural Networks through Augmenting Topologies. Evolutionary Computation 10(2), 99–127 (2002)

Suchorzewski, M.: Evolving Scalable and Modular Adaptive Networks with Developmental Symbolic Encoding. Evolutionary Intelligence 4, 145–163 (2011)

Watts, D., Strogatz, S.: Collective Dynamics of ‘Small-World’ Networks. Nature 393(6684), 440–442 (1998)

Waxman, B.: Routing of Multipoint Connections. Journal on Selected Areas in Communications 6(9), 1617–1622 (1988)

Wong, P.C., Foote, H., Mackey, P., Perrine, K., Chin Jr., G.: Generating Graphs for Visual Analytics through Interactive Sketching. IEEE Transactions on Visualization and Computer Graphics 12(6), 1386–1398 (2006)