Intro; Preface; Network; Graph; Organization of the Book; Network Datasets; Contents; List of Figures; List of Tables; 1 Basics of Graph Theory; 1.1 Choice of Representation; 1.1.1 Undirected Graphs; 1.1.2 Directed Graphs; 1.2 Degree of a Vertex; 1.3 Degree Distribution; 1.4 Average Degree of a Graph; 1.5 Complete Graph; 1.6 Regular Graph; 1.7 Bipartite Graph; 1.8 Graph Representation; 1.8.1 Adjacency Matrix; 1.8.2 Edge List; 1.8.3 Adjacency List; 1.9 Edge Attributes; 1.9.1 Unweighted Graph; 1.9.2 Weighted Graph; 1.9.3 Self-looped Graph; 1.9.4 Multigraphs; 1.10 Path; 1.11 Cycle

1.12 Path Length1.13 Distance; 1.14 Average Path Length; 1.15 Diameter; 1.16 Connectedness of Graphs; 1.17 Clustering Coefficient; 1.18 Average Clustering Coefficient; Reference; 2 Graph Structure of the Web; 2.1 Algorithms; 2.1.1 Breadth First Search (BFS) Algorithm; 2.1.2 Strongly Connected Components (SCC) Algorithm; 2.1.3 Weakly Connected Components (WCC) Algorithm; 2.2 First Set of Experiments-Degree Distributions; 2.3 Second Set of Experiments-Connected Components; 2.4 Third Set of Experiments-Number of Breadth First Searches; 2.5 Rank Exponent mathcalR; 2.6 Out-Degree Exponent mathcalO

2.7 Hop Plot Exponent mathcalH2.8 Eigen Exponent mathcalE; References; 3 Random Graph Models; 3.1 Random Graphs; 3.2 Erdös-Rényi Random Graph Model; 3.2.1 Properties; 3.2.2 Drawbacks of Gn,p; 3.2.3 Advantages of Gn,p; 3.3 Bollobás Configuration Model; 3.4 Permutation Model; 3.5 Random Graphs with Prescribed Degree Sequences; 3.5.1 Switching Algorithm; 3.5.2 Matching Algorithm; 3.5.3 ``Go with the Winners'' Algorithm; 3.5.4 Comparison; References; 4 Small World Phenomena; 4.1 Small World Experiment; 4.2 Columbia Small World Study; 4.3 Small World in Instant Messaging; 4.4 Erdös Number

4.5 Bacon Number4.6 Decentralized Search; 4.7 Searchable; 4.8 Other Small World Studies; 4.9 Case Studies; 4.9.1 HP Labs Email Network; 4.9.2 LiveJournal Network; 4.9.3 Human Wayfinding; 4.10 Small World Models; 4.10.1 Watts-Strogatz Model; 4.10.2 Kleinberg Model; 4.10.3 Destination Sampling Model; References; 5 Graph Structure of Facebook; 5.1 HyperANF Algorithm; 5.2 Iterative Fringe Upper Bound (iFUB) Algorithm; 5.3 Spid; 5.4 Degree Distribution; 5.5 Path Length; 5.6 Component Size; 5.7 Clustering Coefficient and Degeneracy; 5.8 Friends-of-Friends; 5.9 Degree Assortativity

5.10 Login Correlation5.11 Other Mixing Patterns; 5.11.1 Age; 5.11.2 Gender; 5.11.3 Country of Origin; References; 6 Peer-To-Peer Networks; 6.1 Chord; 6.2 Freenet; Problems; References; 7 Signed Networks; 7.1 Theory of Structural Balance; 7.2 Theory of Status; 7.3 Conflict Between the Theory of Balance and Status; 7.4 Trust in a Network; 7.4.1 Atomic Propagations; 7.4.2 Propagation of Distrust; 7.4.3 Iterative Propagation; 7.4.4 Rounding; 7.5 Perception of User Evaluation; 7.6 Effect of Status and Similarity on User Evaluation; 7.6.1 Effect of Similarity on Evaluation