CS 60078 Complex Networks

(Spring Semester 2008)

Theory
Niloy Ganguly (NG) niloy@cse.iitkgp.ernet.in

Teaching Assistant
Bivas Mitra (BM) bivas_mitra@yahoo.com

Notices

Final Grades are out!! Enjoy

1. Allotment of term project done - 21.2
2. Abstract of term project due - 7.3.08
3. First draft of scribe due - 27.2.08

Class Room/Hour
Books
Evaluation
Lectures
Syllabus
Students List
Assignments
Term projects

Class Room/Hours

Lectures : Wed - 3, Thu - 2, Fri - 4
Room : CSE 302
Units : 3-0-0
Credits : 3
Contact : Room #313 (CSE), Phone 3460

Books

A list of useful books and materials is given below.

Guido Caldarelli, Scale-Free Networks, Oxford University Press, Oxford (2007)
S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks, Oxford University Press, Oxford (2003)
M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167-256 (2003).
R. Albert and A.-L. Barabasi Statistical mechanics of complex networks. Rev. Mod. Phys., Vol. 74, No. 1, January 2002.
Narsingh Deo, Graph Theory Prentice Hall India.
For Social Networks
Robert A. Hanneman Introduction to Social Network Methods
Martin Everett, Stephen P. Borgatti. Extending Centrality
Martin Everett, Stephen P. Borgatti. Computing Regular Equivalence: Practical and Theoretical Issues
For Assortativeness
Assortative mixing in networks, M. E. J. Newman, Phys. Rev. Lett. 89, 208701 (2002).
Mixing patterns and community structure in networks, M. E. J. Newman and M. Girvan, in Statistical Mechanics of Complex Networks, R. Pastor-Satorras, J. Rubi, and A. Diaz-Guilera (eds.), Springer, Berlin (2003).

For Clustering Coefficient

Higher order clustering coefficients in Barab´asi-Albert networks
For Community Structure
Detecting community structure in networks, M. E. J. Newman, Eur. Phys. J. B 38, 321-330 (2004).
Finding Communities in Linear Time: A Physics Approach Fang Wu, Bernardo A. Huberman
Defining and identifying communities in networks, Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, Domenico Parisi
Finding and evaluating community structure in network. M.E.J. Newman, M. Girvan
For Generating Function
Random graphs with arbitrary degree distributions and their applications, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118 (2001).
For growth model
M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167-256 (2003).
P. L. Krapivsky and S. Redner, Organization of growing random networks
For Small World
D. J. Watts, Small Worlds, Princeton Studies in Complexity
Models of the small world, M. E. J. Newman, J. Stat. Phys. 101, 819-841 (2000).
For epidemics
SIR Study material
SIS Study material
R. Pastor-Satorras and A. Vespignani.Epidemic dynamics and endemic states in complex networks
For Search
Jon M. Kleinberg Authoritative sources in a hyperlinked environment

Related Course Webpages

Evaluation (Tentative)

Mid-sem : 20
Term Project/ (Scribes, Assignment) : 35
Class Performance (Attendance etc): 5
End-sem : 40

Lectures

4/1/2008 Introduction

9/1/2008 to 11/1/2008 Pajek

16/1/2008 Introductory graph theory, properties of adjacency matrix and incidence matrix, calculating diameter, shortest path.

17/1/2008 Introductory graph theory, planer graph, properties of planer graph, connected component, clique, k-plex,

18/1/2008 Centrality measures, degree centrality, closeness, betweenness, eigenvector centrality, analytical expressions.

24/1/2008 Searching the web, hubs and authorities, HITS algorithm, Page rank.

30/1/2008 Social network analysis, roles in network, concept of equivalence, structural similarity, Pearson correlation, Euclidian distance.

31/1/2008 Clustering coefficient, higher order clustering coefficients, Assortativity, automorphic equivalence, hierarchical clustering

6/2/2008 Community formation, Graph partitioning algorithm, sociological influence, new approaches, Keningham Lin algorithm, and spectral bisection method

7/2/2008 Community finding algorithms, Wu-Huberman algorithm, Newman Girvan, Bridge edges, finding shortest path betweenness, spanning tree based approach.

8/2/2008 Community finding algorithms, random walker based approach, Raddicchi’s algorithm, Motif network

13/2/2008 Introduction to Random graphs, degree distribution, Erdos Renyi graph, scale free networks, construction of random graphs

14/2/2008 Concept of giant component, phase transition, size of the giant component, different properties of E-R graphs

15/2/2008 Generating function, Basic concepts and results, calculation of the moments

20/2/2008 Generating function, power property, calculating the degree distribution of the first neighbors, number of second neighbors, calculation of component size distribution like H1(x) and H0(x).

5/3/2008 Generating function, deriving the condition of phase transition and emergence of giant component, calculation of the number of neighbors and average path length.

06/03/2008 Models of network growth, preferential attachment, Barabasi-Albert Model.

07/03/2008 Barabasi-Albert Model., Price’s growth model

12/03/2008 Generalized growth model, Kaprivsky-Render model, theory for sublinear and linear growth.

13/03/2008 Kaprivsky-Render model, theory for sublinear and linear growth, Problems of Barabasi model

14/03/2008 Growth in the rewiring environment, vertex copying model of network growth

19/03/2008 Small World network, small world property, Watts and Strogatz model, – diameter, clustering cooefficient, no. of neighbors.

20/03/2008 Small World, Newman and Watts model, rewiring, connected caveman model – prisoner’s dilemma.

02/04/2008 Kleinberg’s model, 2 d grid network as small world, Decentralized algorithm for search in 2 D grid network, processes on network.

03/04/2008 Epidemics, SIS model, Epidemic threshold, modeling, initial dynamics(butterfly effect)

04/04/2008 Different models of epidemics, SIR, SIRS model.

09/04/2008 Robustness of a network, degree independent and dependent failure, stability condition of an infinite graph

10/04/2008 Stability condition for finite size graph, mathematical approximation of the deformed topology due to node disruption, percolation condition for finite size graph, percolation threshold.

11/04/2008 percolation in finite graph for random failure and information sensitive attach, growth in bipartite networks

Scribes

1. Scribes on basics of graph theory 04CS1014

2. Scribe on Social Networks 04CS1016 (new)

3. Scribe on community identification 04CS1029

4. Theory of random graphs 04CS3009

First draft due - 27.2.08, prepare scribe in latex (must)

5. Glossary of essential terms in CNT 04CS1015

6. Growth of Networks 04CS1015

7. Small World 04CS1005

8. Pajec 04CS1016

9. Epidemics on Network 04CS1011