Erciyes K. Complex Networks. An Algorithmic Perspective

CRC Press, 2015, -318 p.Recent technological advances in the last two decades have provided availability of enormous amounts of data about large networks consisting of hundreds and thousands of nodes. These so-called complex networks have non-trivial topological features and can vary from technological networks to social networks to biological networks. The study of complex networks, sometimes referred to as network science, has become a fundamental research area since then in various disciplines such as mathematics, statistics, computer science, physics and biology.
These seemingly unrelated networks experimentally have been shown to have common properties such as low average distance between their nodes, high local densities and degree distributions with few high degree nodes and many low degree nodes. Modeling and analysis of these networks based on experiments and evaluations has become an active and attractive area of research with many potential results. Graphs have been widely and successfully used to model computer networks, and it seems graph theory is a promising tool also for complex networks. Although there has been considerable amount of study and research on the modeling and analysis of complex networks, the algorithms for these networks are relatively less investigated.
Whether a complex network is man-made such as the Internet or not such as a protein interaction network, predicting its behavior is not a trivial task. Understanding the functionality of complex networks provides us with insight to predict their behavior and once we can estimate the behavior of a complex network based on its functionality, we may be able to control its functionality. For example, if we can understand the spreading pattern of an epidemic disease which in fact is a complex network, we can estimate where it will most likely spread and can then take precautions to stop it. In summary, controlling the functionality of a complex network is one of the fundamental reasons to study these networks.
As a first step in their study, we need to specify and classify the properties of complex networks. We can then use analytical tools to identify and analyze these properties to understand them better. As an example, a group of entities that make the complex network may be more closely related to each other than the rest of the network. These groups called the clusters may have important processing effects on the overall functionality of the network. If we can detect clusters in a social network for example, we can locate these intense regions of activity in that network after which we can investigate the role of these clusters in the functioning of the whole network. Detection of these propertiesmay be visually possible in a small network of few tens of nodes but for a complex network of hundreds of thousands of nodes, we need analytical tools and computational methods. Properties of complex networks such as clustering depend on their topological properties and study of topological properties of these networks provides insight to their functioning.
This book is about specifying, classifying, designing and implementation of mostly sequential, and also parallel and distributed algorithms that can be used to analyze mostly the static properties of complex networks. Our aim has been to identify and describe a repertoire of algorithms that may be of use for any complex network. The starting point was to identify fundamental and mostly topological properties which are static in general and evaluation of these properties which requires efficient algorithms. The problems encountered are NP-hard in many cases and we need to rely on approximation algorithms where sub-optimal solutions in polynomial time can be found. Sometimes, using heuristic algorithms may be the only choice and extensive tests are needed to support that the algorithm works for most of the cases. Parallel algorithms aim at performance and provide efficiency for computation intensive tasks to be performed and we present several parallel algorithms. Distributed algorithms reach a decision by local information and are usually the only choice in computer networks. Design and implementation of parallel and distributed algorithms received little attention for complex networks in the past and are promising areas for potential research in these networks.
An important static topological property of a complex network is its centrality measure which shows the importance of a node or an edge in the network. Clustering or community detection is another fundamental topological complex network property and provides information about groups of nodes in the complex networks which have closer relations among them than the rest of the network. Discovery of motifs which are patterns occurring more than any other patterns, possibly indicating a basic function in the network is another important property of the complex networks. Evaluation of such measures using sequential, approximation, heuristic, parallel and distributed algorithms provides us with significant information about a particular network. We can then improve the modeling of the network, understand its function better and possibly predict the behavior of the network.
The style we have adopted is to keep everything as simple as possible, to be able to guide a beginning researcher or a student with virtually no background in the field of complex networks. The language used is mathematical rather than descriptive most of the time; however, a basic discrete mathematics and algorithms background at undergraduate level is sufficient to follow the material. Again, to aid the beginner in the field, most of the algorithms are provided in ready-to-be-executed form to test. The book is divided into three parts. Part I provides the basic background in terms of the graph theory; algorithms and complexity and the specification of the parameters for the analysis of complex networks. In Part II, we provide a survey of important algorithms for the analysis of complex networks, starting with distance and centrality algorithms. We then describe algorithms to construct and detect special subgraphs in complex networks, which may be used for other tasks such as clustering. A survey of data and graph clustering algorithms is also presented and this part concludes by the description of the network motif discovery algorithms. Part III is about case studies of complex networks and we show the implementation of some of the algorithms we have described in real-life networks such as the protein interaction networks, the social networks and the computer networks.I: BACKGROUND
Graph Theory
Algorithms and Complexity
Analysis of Complex Networks
II: ALGORITHMS
Distance and Centrality
Special Subgraphs
Data Clustering
Graph-based Clustering
Network Motif Discovery
III:APPLICATIONS
Protein Interaction Networks
Social Networks
The Internet and the Web
Ad hoc Wireless Networks