#
Complex Networks

An Algorithmic Perspective

## Preview

## Book Description

Network science is a rapidly emerging field of study that encompasses mathematics, computer science, physics, and engineering. A key issue in the study of complex networks is to understand the collective behavior of the various elements of these networks.

Although the results from graph theory have proven to be powerful in investigating the structures of complex networks, few books focus on the algorithmic aspects of complex network analysis. Filling this need, **Complex Networks: An Algorithmic Perspective** supplies the basic theoretical algorithmic and graph theoretic knowledge needed by every researcher and student of complex networks.

This book is about specifying, classifying, designing, and implementing mostly sequential and also parallel and distributed algorithms that can be used to analyze the static properties of complex networks. Providing a focused scope which consists of graph theory and algorithms for complex networks, the book identifies and describes a *repertoire *of algorithms that may be useful for *any *complex network.

- Provides the basic background in terms of graph theory
- Supplies a survey of the key algorithms for the analysis of complex networks
- Presents case studies of complex networks that illustrate the implementation of algorithms in real-world networks, including protein interaction networks, social networks, and computer networks

Requiring only a basic discrete mathematics and algorithms background, the book supplies guidance that is accessible to beginning researchers and students with little background in complex networks. To help beginners in the field, most of the algorithms are provided in ready-to-be-executed form.

While not a primary textbook, the author has included pedagogical features such as learning objectives, end-of-chapter summaries, and review questions

## Table of Contents

BACKGROUND **Introduction**

Overview

Real-World Complex Networks

Technological Networks

Information Networks

Social Networks

Biological Networks

Topological Properties of Complex Networks

Algorithmic Challenges

Outline of the Book

References**Graph Theory**

Basics

Subgraphs

Graph Isomorphism

Types of Graphs

Paths and Cycles

Connectivity

Trees

Graph Representations

Spectral Properties of Graphs

Eigenvalues and Eigenvectors

The Laplacian Matrix

Chapter Notes

References**Algorithms and Complexity**

Introduction

Time Complexity

Recurrences

Divide and Conquer Algorithms

Graph Algorithms

Breadth-first Search

Depth-first Search

Dynamic Programming

Greedy Algorithms

NP-Complete Problems

NP Completeness

Reductions

Satisfiability Problems

3-SAT to Independent Set

Independent Set to Vertex Cover

Independent Set to Clique

Coping with NP Completeness

Backtracking

Branch and Bound

Approximation Algorithms

Parallel Algorithms

Architectural Constraints

Example Algorithms

Distributed Systems and Algorithms

Chapter Notes

References**Analysis of Complex Networks**Introduction

Vertex Degrees

Degree Sequence

Degree Distribution

Communities

Clustering Coefficient

The Matching Index

Centrality

Network Motifs

Models

Small World Networks

Scale-Free Networks

Chapter Notes

References

ALGORITHMS

**Distance and Centrality**

Introduction

Finding Distances

Average Distance

Dijkstra’s Single Source Shortest Paths Algorithm

Floyd-Warshall All Pairs Shortest Paths Algorithm

Centrality

Degree Centrality

A Distributed Algorithm for *k*-hop Degree Centrality

Closeness Centrality

Stress Centrality

Betweenness Centrality

Newman’s Algorithm

Brandes’ Algorithm

Eigenvalue Centrality

Chapter Notes

References**Special Subgraphs**

Introduction

Maximal Independent Sets

Dominating Sets

A Greedy MDS Algorithm

Guha-Khuller First MCDS Algorithm

Guha-Khuller Second MCDS Algorithm

Matching

A Maximal Unweighted Matching Algorithm

A MaximalWeighted Matching Algorithm

Vertex Cover

A Minimal Connected Vertex Cover Algorithm

A Minimal Weighted Vertex Cover Algorithm

A Distributed Algorithm for MWVC Construction

Chapter Notes

References**Data Clustering**

Introduction

Types of Data Clustering

Agglomerative Hierarchical Clustering*k*-means Algorithm

Nearest Neighbor Algorithm

Fuzzy Clustering

Density-based Clustering

Parallel Data Clustering

Chapter Notes

References**Graph-based Clustering**

Introduction

Graph Partitioning

BFS-based Partitioning

Kernighan-Lin Algorithm

Spectral Bisection

Multi-level Partitioning

Parallel Partitioning

Graph Clustering

MST-based Clustering

Clustering with Clusterheads

Discovery of Dense Subgraphs

Definitions

Clique Algorithms

The First Algorithm

The Second Algorithm

*k*-core Algorithm

Chapter Notes

References **Network Motif Discovery **Introduction

Network Motifs

Measures of Motif Significance

Generating Null Models

Hardness of Motif Discovery

Subgraph Isomorphism

Vertex Invariants

Algorithms

Ullman’s Algorithm

*Nauty*Algorithm

VF2 Algorithm

BM1 Algorithm

Motif Discovery Algorithms

Exact Census Algorithms

*Mf inder*Algorithm

Enumerate Subgraphs (ESU) Algorithm

Grochow and Kellis Algorithm

*Kavosh*Algorithm

MODA

Approximate Algorithms with Sampling

*Mf inder*with Sampling

Randomized ESU Algorithm

MODA with Sampling

Chapter Notes

References

APPLICATIONS

**Protein Interaction Networks**

Introduction

Topological Properties of PPI Networks

Detection of Protein Complexes

Highly Connected Subgraphs Algorithm

Restricted Neighborhood Search Algorithm

Molecular Complex Detection Algorithm

Markov Clustering Algorithm

Network Motifs in PPI Networks

Network Alignment

Quality of the Alignment

Topological Similarity

Node Similarity

Algorithms

*PathBLAST*

*MaWIsh*

*IsoRank*

GRAAL

Recent Algorithms

Chapter Notes

References

Social Networks

Social Networks

Introduction

Relationships

Homophily

Positive and Negative Relations

Structural Balance

Equivalence

Community Detection Algorithms

Edge Betweenness-based Algorithm

Resistor Networks

RandomWalk Centrality

Modularity-based Algorithm

Chapter Notes

References

**The Internet and the Web**

Introduction

The Internet

Services

Services of Connection

Circuit and Packet Switching

Internet Protocol Suite

Analysis

The Web

The Web Graph

Properties

Models

Evolving Model

Copying Model

Growth-deletion Model

Multi-layer Model

Cyber Community Detection

Link Analysis

Hubs and Authorities

Page Rank Algorithm

Chapter Notes

References

Ad hoc Wireless Networks

Ad hoc Wireless Networks

Introduction

Clustering Algorithms

Lowest-ID Algorithm

Dominating Set-based Clustering

Spanning Tree-based Clustering

Mobile Social Networks

Architecture

Community Detection

Middleware

MobiSoC

MobiClique

SAMOA

Yarta

Chapter Notes

References

Index

## Author(s)

### Biography

**Kayhan Erciyes** is a professor of computer science and engineering and also the rector of Izmir University, Izmir, Turkey. Dr. Erciyes worked as a research and development engineer of Alcatel Turkey, Alcatel Portugal, and Alcatel SEL. He has worked as faculty in Oregon State University, UC Davis and California State University, US and Izmir and Aegean universities. His research interests are on distributed systems, graph theory and distributed algorithms for complex networks, mobile ad hoc networks, wireless sensor networks and the Grid and has published extensively in these areas. Dr. Erciyes is the designer and implementer of one of the first commercially available MODEMs in Turkey