Final Grades are out!! Enjoy
1. Allotment of term project done - 21.2Related Course Webpages
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
10. Resilience on Network 04CS1029
11. Bipartite Network 04CS1011
1. Assignment 1 04CS1014
2. Assignment 2 04CS3014
3. Assignment 3 04CS3009
4. Assignment 4 04CS1005
1. Search in small world networks.
2. Community Structure in networks - Developing and evaluating overlapping communities
3. Routing Strategy in complex networks
4. Study of the spectral plots of different connectivity matrices of a graph
5. Technique to calculate all eigenvalues of huge matrix
6. Hierarchical Model of Internet Topology
7. Classification of Edges in Citation Networks
8. Forming Random Graphs.
9. Routing Strategy in faulty hypercube networks
10. Finding standard measures of various real life networks
Term Project and scribe allotment list