logo资料库

Network Analysis: methodological foundations.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：4.87M 资料格式：pdf 举报 版权申诉
第1页 / 共482页
第2页 / 共482页
第3页 / 共482页
第4页 / 共482页
第5页 / 共482页
第6页 / 共482页
第7页 / 共482页
第8页 / 共482页
资料共482页，剩余部分请下载后查看
    00
    01
    Element-Level Analysis (Google’s PageRank)
    Group-Level Analysis (Political Ties)
    Network-Level Analysis (Oracle of Bacon)
    02
    Graph Theory
    Essential Problems and Algorithms
    Connected Components
    Distances and Shortest Paths
    Network Flow
    Graph k-Connectivity
    Linear Programming
    NP-Completeness
    Algebraic Graph Theory
    Probability and Random Walks
    Chapter Notes
    03
    Introductory Examples
    A Loose Definition
    Distances and Neighborhoods
    Degree
    Facility Location Problems
    Structural Properties
    Shortest Paths
    Stress Centrality
    Shortest-Path Betweenness Centrality
    Reach
    Traversal Sets
    Derived Edge Centralities
    Edge Centralities Derived from Vertex Centralities
    Vitality
    Flow Betweenness Vitality
    Closeness Vitality
    Shortcut Values as a Vitality-Like Index
    Stress Centrality as a Vitality-Like Index
    Current Flow
    Electrical Networks
    Current-Flow Betweenness Centrality
    Current-Flow Closeness Centrality
    Random Processes
    Random Walks and Degree Centrality
    Random-Walk Betweenness Centrality
    Random-Walk Closeness Centrality
    Feedback
    Counting All Paths – The Status Index of Katz
    General Feedback Centralities
    Web Centralities
    Dealing with Insufficient Connectivity
    Intuitive Approaches
    Cumulative Nominations
    Graph- vs. Vertex-Level Indices
    Chapter Notes
    04
    Basic Algorithms
    Shortest Paths
    Shortest Paths Between All Vertex Pairs
    Dynamic All-Pairs Shortest Paths
    Maximum Flows and Minimum-Cost Flows
    Computing the Largest Eigenvector
    Centrality-Specific Algorithms
    Betweenness Centrality
    Shortcut Values
    Fast Approximation
    Approximation of Centralities Based on All Pairs Shortest Paths Computations
    Approximation of Web Centralities
    Dynamic Computation
    Continuously Updated Approximations of PageRank
    Dynamically Updating PageRank
    05
    Normalization
    Comparing Elements of a Graph
    Comparing Elements of Different Graphs
    Personalization
    Personalization for Distance and Shortest Paths Based Centralities
    Personalization for Web Centralities
    Four Dimensions of a Centrality Index
    Axiomatization
    Axiomatization for Distance-Based Vertex Centralities
    Axiomatization for Feedback-Centralities
    Stability and Sensitivity
    Stability of Distance-Based Centralities
    Stability and Sensitivity of Web-Centralities
    06
    Perfectly Dense Groups: Cliques
    Computational Primitives
    Finding Maximum Cliques
    Approximating Maximum Cliques
    Finding Fixed-Size Cliques
    Enumerating Maximal Cliques
    Structurally Dense Groups
    Plexes
    Cores
    Statistically Dense Groups
    Dense Subgraphs
    Densest Subgraphs
    Densest Subgraphs of Given Sizes
    Parameterized Density
    Chapter Notes
    07
    Fundamental Theorems
    Introduction to Minimum Cuts
    All-Pairs Minimum Cuts
    Properties of Minimum Cuts in Undirected Graphs
    Cactus Representation of All Minimum Cuts
    Flow-Based Connectivity Algorithms
    Vertex-Connectivity Algorithms
    Edge-Connectivity Algorithms
    Non-flow-based Algorithms
    The Minimum Cut Algorithm of Stoer and Wagner
    Randomized Algorithms
    Basic Algorithms for Components
    Biconnected Components
    Strongly Connected Components
    Triconnectivity
    Chapter Notes
    08
    Quality Measurements for Clusterings
    Coverage
    Conductance
    Performance
    Other Indices
    Summary
    Clustering Methods
    Generic Paradigms
    Algorithms
    Bibliographic Notes
    Other Approaches
    Extensions of Clustering
    Axiomatics
    Chapter Notes
    09
    Role Assignments
    Preliminaries
    Role Graph
    Structural Equivalence
    Lattice of Equivalence Relations
    Lattice of Structural Equivalences
    Computation of Structural Equivalences
    Regular Equivalence
    Elementary Properties
    Lattice Structure and Regular Interior
    Computation of Regular Interior
    The Role Assignment Problem
    Existence of k-Role Assignments
    Other Equivalences
    Exact Role Assignments
    Automorphic and Orbit Equivalence
    Perfect Equivalence
    Relative Regular Equivalence
    Graphs with Multiple Relations
    The Semigroup of a Graph
    Winship-Pattison Role Equivalence
    Chapter Notes
    10
    Deterministic Models
    Measuring Structural Equivalence
    Multidimensional Scaling
    Clustering Based Methods
    CONCOR
    Computing the Image Matrix
    Goodness-of-Fit Indices
    Generalized Blockmodeling
    Stochastic Models
    The p1 Model
    Goodness-of-Fit Indices
    Blockmodels and p1
    Posterior Blockmodel Estimation
    p* Models
    Chapter Notes
    11
    Degree Statistics
    Distance Statistics
    Average or Characteristic Distance
    Radius, Diameter and Eccentricity
    Neighborhoods
    Effective Eccentricity and Diameter
    Algorithmic Aspects
    ANF – The Approximate Neighborhood-Function
    The Number of Shortest Paths
    Distortion
    Clustering Coefficient and Transitivity
    Definitions
    Relation Between C and T
    Computation
    Approximation
    Network Motifs
    Algorithmic Aspects
    Types of Network Statistics
    Transformation of Types of Statistics
    Visualization
    Sampling of Local Statistics
    Chapter Notes
    12
    Graph Isomorphism
    A Simple Backtracking Algorithm
    McKay’s Nauty Algorithm
    The Difficulty of GI or ‘How to Trick Nauty’
    Graph Similarity
    Edit Distance
    Difference in Path Lengths
    Maximum Common Subgraphs
    Other Methods
    Chapter Notes
    13
    Fundamental Models
    The Graph Model (Gn,p)
    Small World
    Local Search
    Power Law Models
    Global Structure Analysis
    Finding Power Laws of the Degree Distribution
    Generating Functions
    Graphs with Given Degree Sequences
    Further Models of Network Evolution
    Game Theory of Evolution
    Deterministic Impact of the Euclidean Distance
    Probabilistic Impact of the Euclidean Distance
    Internet Topology
    Properties of the Internet’s Topology
    INET – The InterNEt Topology Generator
    Chapter Notes
    14
    Fundamental Properties
    Basics from Linear Algebra
    The Spectrum of a Graph
    The Laplacian Spectrum
    The Normalized Laplacian
    Comparison of Spectra
    Examples
    Numerical Methods
    Methods for Computing the Whole Spectrum of Small Dense Matrices
    Methods for Computing Part of the Spectrum of Large Sparse Matrices
    Subgraphs and Operations on Graphs
    Interlacing Theorem
    Grafting
    Operations on Graphs
    Bounds on Global Statistics
    Proof of Theorem 14.4.7
    Heuristics for Graph Identification
    New Graph Statistics
    Spectral Properties of Random Graphs
    Random Power Law Graphs
    Chapter Notes
    15
    Worst-Case Connectivity Statistics
    Classical Connectivity
    Cohesiveness
    Minimum m-Degree
    Toughness
    Conditional Connectivity
    Worst-Case Distance Statistics
    Persistence
    Incremental Distance and Diameter Sequences
    Average Robustness Statistics
    Mean Connectivity
    Average Connected Distance and Fragmentation
    Balanced-Cut Resilience
    Effective Diameter
    Probabilistic Robustness Statistics
    Reliability Polynomial
    Probabilistic Resilience
    Chapter Notes
    99
    Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen 3418 Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos New York University, NY, USA Doug Tygar University of California, Berkeley, CA, USA Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
    Ulrik Brandes Thomas Erlebach (Eds.) Network Analysis Methodological Foundations 1 3
    Volume Editors Ulrik Brandes University of Konstanz Department of Computer and Information Science Box D 67, 78457 Konstanz, Germany E-mail: ulrik.brandes@uni-konstanz.de Thomas Erlebach University of Leicester Department of Computer Science University Road, Leicester, LE1 7RH, U.K. E-mail: t.erlebach@mcs.le.ac.uk Library of Congress Control Number: 2005920456 CR Subject Classification (1998): G.2, F.2.2, E.1, G.1, C.2 ISSN 0302-9743 ISBN 3-540-24979-6 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springeronline.com © Springer-Verlag Berlin Heidelberg 2005 Printed in Germany Typesetting: Camera-ready by author, data conversion by Markus Richter, Heidelberg Printed on acid-free paper SPIN: 11394051 06/3142 5 4 3 2 1 0
    Preface The present book is the outcome of a seminar organized by the editors, sponsored by the Gesellschaft f¨ur Informatik e.V. (GI) and held in Dagstuhl, 13–16 April 2004. GI-Dagstuhl-Seminars are organized on current topics in computer science that are not yet well covered in textbooks. Most importantly, this gives young researchers an opportunity to become actively involved in such topics, and to produce a book that can provide an introduction for others as well. The participants of this seminar were assigned subtopics on which they did half a year of research prior to the meeting. After a week of presentations and discussion at Schloss Dagstuhl, slightly more than another half-year was spent on writing the chapters. These were cross-reviewed internally and blind-reviewed by external experts. Since we anticipate that readers will come from various disciplines, we would like to emphasize that it is customary in our field to order authors alphabetically. The intended audience consists of everyone interested in formal aspects of network analysis, though a background in computer science on, roughly, the undergraduate level is assumed. No prior knowledge about network analysis is required. Ideally, this book will be used as an introduction to the field, a reference and a basis for graduate-level courses in applied graph theory. First and foremost, we would like to thank all participants of the seminar and thus the authors of this book. We were blessed with a focused and deter- mined group of people that worked professionally throughout. We are grateful to the GI and Schloss Dagstuhl for granting us the opportunity to organize the seminar, and we are happy to acknowledge that we were actually talked into doing so by Dorothea Wagner who was then chairing the GI-Beirat der Uni- versit¨atsprofessor(inn)en. We received much appreciated chapter reviews from Vladimir Batagelj, Stephen P. Borgatti, Carter Butts, Petros Drineas, Robert Els¨asser, Martin G. Everett, Ove Frank, Seokhee Hong, David Hunter, Sven O. Krumke, Ulrich Meyer, Haiko M¨uller, Philippa Pattison and Dieter Raut- enbach. We thank Barny Martin for proof-reading several chapters and Daniel Fleischer, Martin Hoefer and Christian Pich for preparing the index. December 2004 Ulrik Brandes Thomas Erlebach
    List of Contributors Andreas Baltz Mathematisches Seminar Christian-Albrechts-Platz 4 University of Kiel 24118 Kiel, Germany Nadine Baumann Department of Mathematics University of Dortmund 44221 Dortmund, Germany Michael Baur Faculty of Informatics University of Karlsruhe Box D 6980 76128 Karlsruhe, Germany Marc Benkert Faculty of Informatics University of Karlsruhe Box D 6980 76128 Karlsruhe, Germany Thomas Erlebach Department of Computer Science University of Leicester University Road Leicester LE1 7RH, U.K. Marco Gaertler Faculty of Informatics University of Karlsruhe Box D 6980 76128 Karlsruhe, Germany Riko Jacob Theoretical Computer Science Swiss Federal Institute of Technology Z¨urich 8092 Z¨urich, Switzerland Frank Kammer Theoretical Computer Science Faculty of Informatics University of Augsburg 86135 Augsburg, Germany Ulrik Brandes Computer & Information Science University of Konstanz Box D 67 78457 Konstanz, Germany Michael Brinkmeier Automation & Computer Science Technical University of Ilmenau 98684 Ilmenau, Germany Gunnar W. Klau Computer Graphics & Algorithms Vienna University of Technology 1040 Vienna, Austria Lasse Kliemann Mathematisches Seminar Christian-Albrechts-Platz 4 University of Kiel 24118 Kiel, Germany
    VIII List of Contributors Dirk Kosch¨utzki IPK Gatersleben Corrensstraße 3 06466 Gatersleben, Germany Sven Kosub Department of Computer Science Technische Universit¨at M¨unchen Boltzmannstraße 3 D-85748 Garching, Germany Katharina A. Lehmann Wilhelm-Schickard-Institut f¨ur Informatik Universit¨at T¨ubingen Sand 14, C108 72076 T¨ubingen, Germany Daniel Sawitzki Computer Science 2 University of Dortmund 44221 Dortmund, Germany Thomas Schank Faculty of Informatics University of Karlsruhe Box D 6980 76128 Karlsruhe, Germany Sebastian Stiller Institute of Mathematics Technische Universit¨at Berlin 10623 Berlin, Germany J¨urgen Lerner Computer & Information Science University of Konstanz Box D 67 78457 Konstanz, Germany Hanjo T¨aubig Department of Computer Science Technische Universit¨at M¨unchen Boltzmannstraße 3 85748 Garching, Germany Marc Nunkesser Theoretical Computer Science Swiss Federal Institute of Technology Z¨urich 8092 Z¨urich, Switzerland Leon Peeters Theoretical Computer Science Swiss Federal Institute of Technology Z¨urich 8092 Z¨urich, Switzerland Stefan Richter Theoretical Computer Science RWTH Aachen Ahornstraße 55 52056 aachen, Germany Dagmar Tenfelde-Podehl Department of Mathematics Technische Universit¨at Kaiserslautern 67653 Kaiserslautern, Germany Ren´e Weiskircher Computer Graphics & Algorithms Vienna University of Technology 1040 Vienna, Austria Oliver Zlotowski Algorithms and Data Structures Univerist¨at Trier 54296 Trier, Germany
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料