Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIH0013	Evolution in Complex Systems	

Semester	Hours: C+S+L	Category	Status	
6	2+0+1	speciality	optional	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
GOG Anca-Mirela	Ph.D.	Lect.	Computer Systems	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
Approaching complex networks applications by means of non-conventional search and optimization techniques
Understanding complex networks dynamics in order to improve artificial intelligence techniques	

IV. Course contents
Complex Networks are approached from two different perspectives. On one hand we present the static structural properties of complex networks and several applications that arise from understanding networks according to these properties. Existing search and optimization techniques from the field of artificial intelligence, such as evolutionary computation, can be successfully applied for problems that occur for such complex networks, problems that prove themselves to be complex as well. On the other hand we consider the more difficult dynamic approach of complex networks that is trying to understand how information is processed and propagated in such networks and how a certain global behavior of the entire network emerges from local interactions of individual components of the network. The challenge posed by a better understanding of complex networks, especially of the way they manage to organize themselves without having a central control, is to create better mechanisms of artificial life and artificial intelligence.	

V. Bibliography
Barabasi, A.-L. (2002), Linked: The New Science of Networks. Perseus, New York.
Balakrishnan, H., Deo, N. (2006), Discovering Communities in Complex Networks. Proceedings of the ACM Southeast Regional Conference, p. 280-285.
Crutchfield, JP, Mitchell, M. (1995), The evolution of emergent computation. Proceedings of the National Academy of Sciences, USA 92 (23), p. 10742-10746.
Das, R., Mitchell, M., Crutchfield, J. P. (1994), A genetic algorithm discovers particle-based computation in cellular automata. Parallel Problem Solving from Nature Conference (PPSN-III), Berlin, Germany, Springer-Verlag, p. 244-253.
Duch, J., Arenas, A. (2005), Community Detection in Complex Networks using Extremal Optimization. Physical Review E, 72, 027104 -1.
Erdős, P., Rényi, A. (1959), On Random Graphs. I. Publicationes Mathematicae 6, p. 290-297.
Erdős, P., Rényi, A. (1960), The Evolution of Random Graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5, p. 17-61.
Girvan, M., Newman, M. E. J. (2002), Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences of the USA, 99, p. 7821-7826.
Huberman, B. A., Wu, F. (2004), Finding Communities in Linear Time: a Physics Approach. The European Physics Journal B, 38, p. 331-338.
Juillé, H., Pollack, J. B. (1998), Coevolving the 'ideal' trainer: Application to the discovery of cellular automata rules. Genetic Programming 1998: Proceedings of the Third Annual Conference, San Francisco, CA. Morgan Kaufmann.
Juillé, H., Pollack, J. B. (2000), Coevolutionary learning and the design of complex systems. Advances in Complex Systems 2(4), p. 371–394.
Mitchell, M. (2006), Complex systems: Network thinking. Artificial Intelligence (18), p. 1194-1212.
Newman, M. E. J., Girvan, M. (2004), Finding and Evaluating Community Structure in Networks. Physical Review E, 69, 026113-1.
Palla, G., Derenyi, I., Farkas, I., Vicsek, T. (2005), Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, p. 814–818.
Reichardt, J., Bornholdt, S. (2004), Detecting fuzzy community structures in complex networks with a Potts model. Phys. Rev. Lett. 93, 218701.
Scott, J. (2000), Social Network Analysis: A Handbook. Sage Publication, London.
Tasgin, M., Bingol, H. (2006), Community Detection in Complex Networks using Genetic Algorithm. cond-mat/0604419.
Tomassini M., Giacobini M., Darabos Ch. (2005), Evolution and Dynamics of Small-World Cellular Automata, Complex Systems, 15(4), p. 261-284.
Watts, D., Strogatz, S. (1998), Collective dynamics of 'small-world' networks, Nature 393, p. 440–442.
Watts, D. (1999), Small worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press, Princeton, NJ.
Watts, D. (2003), Six degrees: The Science of a Connected Age. Gardner’s Books, New York.
Zhang, S., Wang, R.-S., Zhang, X.-S. (2007), Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications, 374 (1), p. 483-490.	

VI. Thematic of didactic activities per weeks
1. Overview of Complex Networks

2. Static structural properties of Complex Networks

3. Complex Network models

4. Six-degrees of separation theory

5. Real-world Complex Networks

6. Applications of network characterizations

7. Algorithms for searching in Complex Networks

8. Algorithms for detecting community structure in Complex Networks

9. Dynamics of Complex Networks

10. Cellular Automata as simple Complex Networks

11. Algorithms for evolving rules for Cellular Automata

12. Algorithms for evolving new Cellular Automata topologies

13. Collaborative Evolutionary Algorithms – applications for Complex Networks

14. Circular Evolutionary Algorithms – applications for Complex Networks	

VII. Didactic methods used
Expositions: description, explanation, class lectures, dialog-based lectures, lectures with demonstrations, introductive lectures, current lectures, synthesis lectures. 
Conversations: debate, dialog, introductive conversations, conversations for knowledge consolidation, conversations to systematize and synthesize knowledge 
Use of problems: use of problem questions, problems and problem situations. 
Discovery: directed and independent rediscovery, creative discovery, inductive discovery, deductive discovery, discovery by documenting, experimental discovery. 
Other methods: case study; cooperation, simulation, brainstorming, individual study, exercise, homework study.	

VIII. Assessment
Written exam, combined with the activity at the laboratories during the semester. The final mark is obtained as an average between:
- the grade at the written exam – 60%
- a grade on the laboratory activity – 40%
The required details for passing this course can be found at
http://www.cs.ubbcluj.ro/~anca/cs/cerinte.htm	

IX. Additional references
Alba E., Giacobini M., Tomassini M., Romero S. (2002), Comparing Synchronous and Asynchronous Cellular Genetic Algorithms. J.J. Merelo et al. (eds.), Proceedings of the Parallel Problem Solving from Nature VII, Granada (SP), LNCS 2439, p. 601-610.
Bäck, T., Fogel, D.B., Michalewicz, Z. (Ed.) (1997), Handbook of Evolutionary Computation. Institute of Physics Publishing, Bristol and Oxford University Press, New York.
Dumitrescu, D., Lazzerini, B., Jain, L.C, Dumitrescu, A. (2000), Evolutionary Computation. CRC Press, Boca Raton, FL.
Pagie, L., Mitchell, M. (2002), A comparison of evolutionary and coevolutionary search, Int. J. Comput. Intell. Appl. 2(1), p. 53–69.
Gog, A., Dumitrescu, D., Hirsbrunner, B. (2007), Community Detection in Complex Networks using Collaborative Evolutionary Algorithms. Proceedings of European Conference on Artificial Life (ECAL), Lisbon, Lecture Notes in Computer Science 4648, p. 886-894.

	Dean,							Chair head,

Date,							Course responsible,
								Lect. GOG Anca-Mirela, Ph.D.