## Slides on Re-Distribution Models

Here is the slides on redistribution models that we have covered in the class.

## Mid-term report

The midterm report is due on Nov 19th.

In the following weeks, we will cover several papers related to robustness and cascading failures in complex networks. This week (Oct 18 – 22), Sindhura will cover the following three papers:
1. Error and Attack Tolerance of Complex Networks
2. Optimization of Robustness of Complex Networks.
3. A simple model of global cascades on random networks

More papers on cascading failures that we plan to cover are as follows:

1. A. E. Motter and Y. Lai “Cascade-based Attacks on Complex Networks” Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 66, 2002
2. R. Albert, I. Albert and G. L. Nakarado “Structural Vulnerability of the North American Power Grid” Rev. Mod. Phys., 69, 2004
3. Cascade-based attack vulnerability on the US power grid
4. Optimizing complex networks for resilience against cascading failure
5. Ali Pinar, Juan Meza, Vaibhav Donde, and Bernard Lesieutre. Optimization strategies for the vulnerability analysis of the electric power grid. SIAM Journal on Optimization, 20(4):1786–1810, 2010.
7. K. Peters, L. Buzna and D. Helbing “Modelling of Cascading Effects and Efficient Response to Disaster Spreading in Complex Networks” International Journal of Critical Infrastructures 2008, 4(1/2):46–62,
2008
8. D. E. Newman, B. Nkei, B. A. Carreras, I. Dobson, V. E. Lynch and P. Gradney “Risk Assessment in Complex Interacting Infrastructure Systems” 38th Annual Hawaii International Conference on System
Sciences, 2005
9. B. A. Carreras, D. E. Newman, P. Gradney, V. E. Lynch, and I. Donson, “Interdependent Risk in Interacting Infrastructure Systems,” Proc. of the 40th Hawaii International Conference on System Sciences, 2007.
10. L. Buzna, K. Peters and D. Helbing “Modelling the Dynamics of Disaster Spreading in Networks” Physical A., 328:132–140, 2006
11. Z. Dezso and A. L. Barabasi “Halting Viruses in Scale-Free Networks” Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 65, 2002

## Group Project Timeline

The project must be done by following this procedure.

• By the third week, each group selects one or two research topics in consultation with the instructor.
• On Oct 8th, 2010, a “research proposal” must be submitted which describes the scope of the project, lists the issues to be addressed, and outlines approaches to be taken. Several recommended papers related to the project must also be provided. The research proposal is about 4 pages long, single space.
• By the tenth week (exact date will be given later), a project midterm report must be submitted. It is about 7 pages long.
• By the last day of class, the final project report in the format of a journal paper is due. It is 11 pages maximum.

## Nice overview

This paper provides a nice view on complex networks. Please read it.

SIAM REVIEW Vol. 45,No . 2,pp . 167–256
The Structure and Function of Complex Networks

## Team Information

Team 1. Thang Dinh and Yilin Shen
Team 2. Nam Nguyen and Dzung Nguyen
Team 3. Ying Xuan and Sindhura

## Graph Generating Models

In this sequence of lectures, we are going to cover several models as follows:

1. Random graph model. (Presented by Yilin Shen). Lecture notes can be found here
2. The Barabasi-Albert Model
3. Modifications to the Barabasi-Albert Model
4. Fitness based Model
5. Online and Offline Models (presented by Nam Nguyen)
6. Small-World Model

(Some other models that we are not going to cover in this class, including Copying models and graph from optimization principles)

## A History Touch on Graph Theory in the Information Age

I will cover a little bit of history in this entry. Yilin Shen will present the random model in the class. Please read the first two papers in the reading list. In addition, you are required to understand the binomial distribution and its asymptotic behavior, Chernoff inequalities, a concentration inequality. Please read paper 11 for this (Concentration Inequalities and Martingale Inequalities). This is a fundamental knowledge for you to understand the course! So please do read and study paper 11!

In 1999, at the dawn of the new Millennium, a most surprising type of graph was uncovered, thus brought graph theory to the heart of a new paradigm of science. This family of graphs consists a wide range of applications, from WWW, biological networks, phone call networks, collaboration networks, to social networks… These graphs have the following main characteristics:

1. Large: The size of the network typically ranges from hundreds of thousands to billions of nodes (vertices), surrender the use of brute force approaches.
2. Sparse: The number of edges is learning, i.e., within a small multiple of the number of vertices.
3. The small word phenomenon: This refers to two distinct properties: small distance and clustering effect where the former implies that two strangers are typically joined by a short chain of mutual acquaintances and the latter means that two people who share a common neighbor are more likely to know each other.
4. Power law degree distribution: The number of vertices with degree $k$ is proportional to $k^{-\beta}$

As you can see, the first two characteristics come naturally and the third one has long been within the mindset. The most remarkable fact is the last one, the power law, which allows us to use one single parameter, $\beta$, to describe the degree distribution of billions of nodes. This discovery leads to two things: (1) Re-investigate many existing tools such as combinatorial, probabilistic and spectral, to deal with problems on power law graphs; and (2) these graphs provide insight and suggest many new research direction in the field of graph theory.

Indeed, even at the end of the 19th century, the power law had been noted in various scenarios. However, only in 1999 were the dots connected and a more complete picture emerged. Since then, a new area of network complexity has been rapidly developing, spanning several disciplines such as mathematics, physics, computer science, social science, biology, and telecommunication.

Here is a brief history on what happen before 1999 on the power law:

1. 1896, Pareto stated that the distribution of income and wealth follows the logarithmic pattern.
2. 1926, Lotka found that the number of authors who published $n$ papers is inversely proportional to the square of $n$.
3. 1932, Zipf observed that the frequency of English words follows a power law function.
4. 1949, Yule discovered the distribution of species among genera of plants, which is similar to preferential attachment.
5. 1955, Simon gave an argument of how the preferential attachment model leads to power law distributions.
6. The history comes! In 1999, Kumar et al., Barabasi et al., Faloutsos et al. independently reported that the WWW is a power law graph. In the same year, Abello et al. and Aiello et al. stated that the call graphs are power law graphs, and Bhalla et al. and Schilling et al. found that the metabolic networks are power law graphs.
7. 2000, Watts et al. reported various social networks are power law graphs.

## List of Papers

Here is the tentative list of papers which we will partially cover in the class. It will be updated regularly.

1. A Random Graph Model for Power Law Graphs
2. A Random Graph Model for Massive Graphs
3. Random Evolution in Massive Graphs
4. Coupling Online and Offline Analyses for Random Power Graphs
5. Structural and Algorithimic Aspects of Massive Social Networks
6. On the Hardness of Optimization in Power Law Graphs
7. Conductance and Congestion in Power Law Graphs
8. Large Cliques in a Power Law Random Graphs
9. The Small-World Phenomenon: An Algorithmic Perspective
10. The Diameter of Spares Random Graphs
11. Concentration Inequalities and Martingale Inequalities
12. Connected Components in Random Graphs with Given Expected Degree Sequence
13. The Volume of the Giant Component of a Random Graphs with Given expected Degrees
14. A Survey of Models of the Web Graph
15. Editorial: The Future of Power Law Research
16. Approximating Flow Throughput in Complex Data Networks
17. Spectra of random graphs with given expected degrees

Influence in Social Networks

Network Vulnerability and Robustness

1. Effect of Attack on Scale-free Networks due to Cascading Failure
2. Entropy optimization of scale-free networks’ robustness to random failures
3. Robustness of power laws in degree distributions for spiking neural networks

Dynamic Communities

## CIS6900: Optimization in Adaptive Complex Systems and Social Networks

Welcome to the class! Here is a short description of the syllabus.
General Information:

• Time & Place: MWF 1:55pm-2:45pm, Turlington Hall, 2333
• Instructor: My T. Thai. Office hours: Tuesday: 9:30am-11:10am

Course Description and Objectives
The scope of this class is to offer the basic theory of complex networks with a focus on optimization techniques, in the design and analysis of these networks. In addition, it also covers a wide range of applications and optimization problems arising in online social networks and complex communication networks.

I plan to cover the following:

• Basic Theory in Complex Networks
• Configuration Models for Power Law Graphs
• Random Graphs: Offline and Online Analyses
• Average Distance and the Diameter
• Influence in Social Networks
• Network Vulnerability and Robustness
• Dynamic Community Structures

Prerequisites
There is no formal prerequisite for this course. However, this course is designed mainly for graduate students whose research interests lie in complex networks. Students are expected to be very self-motivated and able to keep up with the reading and presentations.

Textbooks
No textbook is used in this course. We will read a list of related papers along with my notes. For references, please read the following:

1. F. Chung and L. Lu, Complex Graphs and Networks, American Mathematical Society, 2006
2. T. D. Lewis, Network Science: Theory and Applications, Wiley, 2009
3. A.-L. Barabasi, Linked, Plume, 2003
4. F. Vega-Redondo, Complex Social Networks, Cambridge University Press, 2007
5. A. Barrat, M. Barthelemy, and A. Vespignani, Dynamical Processes on Complex Networks, Cambridge University Press, 2008
6. G. Caldarelli, Scale-Free Networks, Oxford University Press, 2007