Note: Title -- Preface -- Organization -- Table of Contents -- The Anatomy of the Long Tail of Consumer Demand -- A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification -- Introduction -- A Sharp PageRank Approximation Algorithm -- The Green Values for Edges in a Graph -- Graph Sparsification Using Green Values -- Analyzing the Sparsifier -- Proof of Theorem 4 -- Sparsification Using Approximate PageRank Vectors -- Graph Sparsification by Using Sharply Approximate Green Values -- Partitioning Using Approximate PageRank Vectors -- References -- Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning -- Introduction -- Preliminaries -- Existing Work -- Concentration of Measure -- Random Projections -- Proposed Method -- Edge Sparsification -- Triple Sampling -- Hybrid Algorithm -- Experiments -- Experimental Setup and Implementation Details -- Results -- Remarks -- Theoretical Ramifications -- Random Projections and Triangles -- Sampling in the Semi-streaming Model -- Conclusions and Future Work -- References -- Computing an Aggregate Edge-Weight Function for Clustering Graphs with Multiple Edge Types -- Introduction -- Background -- Clustering in Graphs -- Comparing Two Clusterings -- Recovering a Graph Given a Ground Truth Clustering -- Solving an Inverse Problem -- Maximizing the Quality of Ground-Truth Clustering -- Solving the Optimization Problems -- Experimental Results -- Recovering Edge Weights -- Clustering Quality vs. Holding Vertices -- Inverse Problems vs. Maximizing Clustering Quality -- Runtime Scalability -- Conclusion and Future Work -- References -- Component Evolution in General Random Intersection Graphs -- Introduction -- Model and Previous Work -- Mathematical Preliminaries -- Auxiliary Process on General Random Intersection Graphs. , Process Description in Terms of Random Variable Yt -- Expectation and Variance of t -- Giant Component -- Subcritical Regime -- Supercritical Regime -- Conclusion -- References -- Modeling Traffic on the Web Graph -- Introduction -- Background -- Empirical Traffic Data -- ABC Model -- Model Evaluation -- Conclusions -- References -- Multiplicative Attribute Graph Model of Real-World Networks -- Introduction -- Formulation of the Multiplicative Attribute Graph Model -- The Number of Edges -- Connectivity -- Diameter -- Degree Distribution -- Extensions: Power-Law Degree Distribution -- References -- Random Walks on Digraphs, the Generalized Digraph Laplacian and the Degree of Asymmetry -- Introduction -- Preliminaries: Random Walks on Undirected Graphs -- Random Walk Theory on Digraphs -- Random Walks on Directed Graphs and Fundamental Matrix -- (Normalized) Digraph Laplacian and Green's Function for Digraphs -- Computing Hitting and Commute Times for Digraphs Using Digraph Laplacian -- Degree of Asymmetry, Generalized Cheeger Constant and Bounds on Mixing Rate -- The Degree of Asymmetry, and Relations to Symmetrized Digraph Laplacian -- Bounding the Mixing Rate of Random Walks on Digraphs -- References -- Finding and Visualizing Graph Clusters Using PageRank Optimization -- Introduction -- Preliminaries -- PageRank Variance and Cluster Variance Measures -- The PageRank-Clustering Algorithms -- Analyzing PageRank Clustering Algorithms -- A Graph Drawing Algorithm Using PageRank -- References -- Improving Random Walk Estimation Accuracy with Uniform Restarts -- Introduction -- Reducing Mixing Time by Restart -- Numerical Results -- Conclusions and Future Work -- References -- The Geometric Protean Model for On-Line Social Networks -- Introduction -- The GEO-P Model for OSNs -- Results and Dimension -- Dimension of OSNs -- Proofs of Results. , Degree Distribution -- Proof of Theorem 1 -- Bad Expansion: Proof of Theorem 4 -- Diameter -- Proof of Theorem 3 -- Conclusion and Discussion -- References -- Constant Price of Anarchy in Network Creation Games via Public Service Advertising -- Introduction -- A Tight Upper Bound for Price of Anarchy in Uniform Games -- How the Public Service Advertising Affects the Price of Anarchy -- How to Deal with Unknown and -- References -- Fast Katz and Commuters: Efficient Estimation of Social Relatedness in Large Networks -- Introduction -- Related Work -- Algorithms for Pairwise Score -- Top-k Algorithms -- Empirical Evaluation -- Conclusions and Future Work -- References -- Game-Theoretic Models of Information Overload in Social Networks -- Introduction -- Modeling the Resulting Networks -- Our Models -- Our Results -- Related Work -- Empirical Evidence -- A Model of Friendship Selection: The Followership Game -- A Specific Utility Model -- Greedy Users -- Matchings Characterize Pure Rate Equilibria -- A Model of User Engagement: The Engagement Game -- Pure Equilibria under Sparse or Regular Users -- Conclusions -- References -- Author Index.