Chapter 1
Introduction
Networks are everywhere! A network is a system formed by certain entities and interactions among those entities. One example of a network as a physical system is an electrical power grid network formed by power generation sources, distribution lines, switches that control the transmission of electricity, and consumer equipments. Another popular example of a network is a computer network such as the Internet that consists of servers, clients, switches, and routers interconnected by several communication links such as optical fiber links, coaxial cables, Ethernet cables, wireless links, and satellite links. Other examples include a wide variety of physical networks such as biological networks, social networks, and technological networks. Without interconnected systems, resulting in a network, we can rarely find a physical world system. A network can be represented as a graph where is a set of vertices or nodes and ɛ is a set of edges, and W is the weight matrix used to represent the properties associated with the edges. The vertices of a graph represent the entities, and the edges represent interactions among certain entities.
1.1 Complex Networks
An abstract model of any complex physical system gives rise to a complex network model. Networks obtained by modeling complex systems result in a complex interconnection of nodes (vertices) by edges (links or arcs). Such models of complex physical systems result in complex networks. Figure 1.1 shows a complex network representation of a karate club social network, in a university, studied by Wayne W. Zachary during 1970–72 [1]. This network has 34 nodes and 78 edges where each node represents a person associated with the karate club and an edge between two nodes represents the interactions between individuals outside the normal club activities. In the network, node 1 represents the club instructor, and node 34 represents the club administrator. At the begining of the study, there was a conflict between the administrator and the instructor, which led to the division of the club at the end. Based on the network model, through complex network analysis, Zachary could estimate quite accurately how the members joined the respective fractured clubs.
Figure 1.1. Example of a real-world complex network: Zachary’s karate club network [1] with 34 nodes and 78 edges. Node 1 represents the instructor and node 34 represents the administrator (president) of the club.
Note that in Figure 1.1, the interconnections (edges) between vertices are not as simple as those of a regular network, shown in Figure 1.2. Analyzing and understanding the characteristics of regular networks is easier than complex networks because regular networks have certain order of connectivity between vertices. In certain human-planned networks, formation of regular networks is possible, and in such cases studying them and characterizing them is simpler. One example of a real-world network that is closer to a regular network is the road network present in certain parts of planned cities, as can be found in the road networks of Manhattan, New York, USA. In many natural systems, formation of complex networks is rather common; therefore, characterizing them is challenging. Characterization of a complex network is far more challenging than characterization of a regular network.
Figure 1.2. Example of a regular network
Most physical systems can be represented as complex networks. Complex networks are found in many facets of physical world systems. Natural networks such as biological networks, food-web networks, protein-protein interaction networks, disease networks [2], and ecological networks to human-made networks such as the author citation networks [3], [4], the Internet, the World Wide Web (WWW) [5], electrical power grid networks, transportation networks, and mobile call networks [6], [7], [8], [9], [10], [11] are a few examples of complex networks.
1.2 Types of Complex Networks
Complex networks can be classified into the following major types: random networks, small-world networks, and scale-free networks.
Random networks can be considered as models of physical systems where the connectivity between subsystems is probabilistically determined. In other words, a random network consists of a probabilistic model of a graph where the edges are determined with certain probability value p.
Physical systems of similar kind can interact among themselves with certain probability; therefore, models of such interactions can result in a random graph. For example, consider a social network that involves people and the relationship between people in a society. Many times, social interactions can happen through random events, and when we model the social relationship, the social relationship can be a random function characterized by a probability value p or a probability distribution function. Interaction between many physical parameters can be considered in a similar way. In communication networks such as ad hoc wireless networks [12], formed by highly mobile nodes communicating over wireless channels, network topology can change frequently. Further, the wireless channels limit the range of communication possible for a given ad hoc network node. Therefore, network topology of such an ad hoc wireless network for an instant can also be considered a random network.
Another example of a complex network is the road networks that show arbitrary topologies, as can be found in the road networks in a variety of urban settlements around the world. Figure 1.3 shows the network representation of the roads and intersections in several cities located in the United States, Europe, and India. The US locations are New York City, Manhattan Borough, Los Angeles, and Detroit. Each of the 13 types of roads is represented as a different colored line and presented accordingly for better visual perception of complex network representation of the road networks. It can be noticed that the road networks of New York and Manhattan are closer to a regular network topology. In comparison to the road networks of the United States, road networks of European cities have significant differences in the visual representation, as can be found from the city maps of London, Paris, Milan, and Berlin in Figure 1.3. The larger number of footways, tracks, steps, and paths gives a different look to the European cities. Compared to the networks of US and European cities, those of the Indian cities such as Bangalore, Chennai, Kolkata, and New Delhi have a very different visual appearance. Despite the differences in the visual appearances of these networks, the graph theoretical characteristics do not show significant difference, as can be observed in [13]. All these road networks can be seen as network topologies that can be instances of random network topologies.
Figure 1.3. Examples of road networks. Road types are numbered as superscripts1−13. © [2016] IEEE. Reprinted, with permission, from Sarath Babu and B. S. Manoj, “On the topology of indian and western road networks,” in Proc. 2016 Eighth International Conference on COMmunication Systems and NETworkS (COMSNETS 2016) Intelligent Transportation Systems Workshop, pp. 1–6, January 2016.
Graphs created by mathematical models can also be considered as random networks. For example, in order to study the behavior of a network through mathematical analysis, a graph can be created using mathematical models for network edges between node pairs. Study of such mathematical modeling can be useful in revealing properties of complex systems with similar network formation.
Small-world networks are either formed by natural formation processes or created artificially by network designing processes aimed specifically at achieving small-world characteristics. The most important element of small-world properties is that the average path length (APL) is lower than that of a regular network. In addition to a lower APL, small-world networks exhibit a low average clustering coefficient (ACC). Many large-scale natural networks are found to have very small APL, O(log N), where N is the number of nodes in the network, despite having large network size N. Further, regular networks can be transformed to bring down the APL by adding long-ranged links. Small-world networks have many applications in real-world networks. In Chapter 4, more details on small-world networks are provided, and in Chapters 6 and 7, small-world transformations of wireless mesh networks (WMNs) and wireless sensor neworks (WSNs) are discussed.
Studies of real-world networks, by the complex network research community, led to a very important observation that many real-world networks demonstrate a scale-free property. The scale-free property is defined by the degree distribution of the network nodes following a linear line on a log-log scale. That is, in a scale-free network, the probability of finding a node with a certain degree decreases rapidly with higher degrees. In other words, a fraction of nodes with degree D, represented as P(D) ∼ D−γ where 1 ≤ γ ≤ 3, is the scaling exponent. Scale-free networks have many interesting characteristics, one of which is the ultra small-world property, which results in the network having APL of O(log log N) where N is the number of nodes in the network. Identifying a real-world network as following a scale-free distribution helps in quickly characterizing the properties of the network. Chapter 5 provides details of scale-free networks.
1.3 Benefits of Studying Complex Networks
It is interesting to consider the benefits of studying complex networks. The most important benefit of applying the complex networks approach to real-world problems is to obtain a significant collection of tools to study various complex systems of the physical world. That is, modeling a real-world problem as a complex network model provides significant insights to the characteristics of the real-world problem. In general, we can find the following benefits in studying complex networks: (i) modeling and characterizing complex physical world systems, (ii) design of efficient physical world systems, (iii) development of solutions to complex real-world problems, (iv) molecular networks for biomedical research, (v) network medicine, (vi) neutralizing antisocial networks, and (vii) enhanced social science research through social networks. A brief description of various application domains where complex network modeling can be very useful is provided here.
1.3.1 Modeling and Characterizing Complex Physical World Systems
Studying and analyzing complex physical systems is not only challenging but also unavoidable in our daily life. As computing, communication, and physical systems become more and more complex, new techniques and solutions are required to model and characterize them. The volume of information exchanged as well as the diversity of devices communicating over the Internet have grown tremendously. For example, the Internet had only less than 100 nodes two decades ago. Today, it has more than 6 billion connected devices. The expansion of the Internet resulted in emergence of the Internet of Things (IoT), which consists of traditional physical objects (or items called usually as things), such as household furnitures, kitchen appliances, electrical lights fans, and other similar appliances, electromechanical devices such as automated gates, are Internet-enabled. The growth of IoT is predicted to go beyond 50 billion nodes by 2020. Due to such fast-growing complexity, analyzing the topological and other characteristics is too challenging; therefore, complex network analysis is essential to model and characterize the ever-growing Internet. Similarly, complex network analysis provides a means to model, characterize, and understand many such complex physical world systems.
1.3.2 Design of New and Efficient Physical World Systems
Studying complex networks can help create new system designs as well as improve the design, development, and deployment of various physical systems. For example, consider the design and deployment of wireless sensor networks. An efficient small-world wireless sensor network (SWWSN) system not only can improve energy savings and performance of the system but also can extend the network lifetime. Another example is the design of a small-world wireless mesh network (SWWMN), which can improve the network throughput, delay, and APL performance, thereby achieving higher network capacity. Social networks is another area where the network augmentation can be carried out for signifi-cant benefits. For example, the message propagation properties can be altered by using complex network principles in a social network. Therefore, complex network modeling and analysis can be utilized to design and deploy more efficient complex systems in many application areas of the physical world. Similarly, using the knowledge gained from complex networks, road networks in future towns and cities can be designed better.
1.3.3 Development of Solutions to Complex Real-World Problems
Characterizing complex physical systems into complex network models can be very useful for developing solutions to many real-world problems. For example, the routing problem in a complex navigation terrain can be achieved by graph theoretical solutions such as shortest path routing or all-pairs shortest path routing. Similarly, in a social network, problems such as finding the most connected social network member can be very useful in identifying how to sell advertisements and commercial promotional information. Another example is in the performance optimization of wireless or wired computer networks using complex network analysis.
1.3.4 Enhancing Biomedical Research through Molecular Network Modeling
There exist many applications for complex network analysis pertaining to biomedical engineering as well as biomedical research by modeling and analyzing molecular networks. Molecular networks are network representations of molecules within the biochemical families as well as across different biochemical families. A biochemical compound is characterized by the molecular interactions of various molecules in it. Molecular interactions are the protein-protein interactions within a biochemical compound. The term referred to as interactome represents the protein-protein interaction network (PPIN).
1.3.5 Network Medicine
Complex network analysis approaches can be used to diagnose, prevent, and cure diseases by carefully identifying the network and analysis technique [2]. For example, the protein-protein interactions network or metabolic networks can be effectively used for removing certain parts of the network, thereby achieving a cure to the disease. Another example is to use the complex network approach to study the spread of a particular disease over social networks and develop techniques to prevent disease spread.
1.3.6 Neutralizing Antisocial Networks
Analysis of social networks is an essential activity for law enforcement agencies in many developed countries. Social networks formed by antisocial elements in order to carry out subversive activities can be identified and neutralized. International terroristic networks, narcotics trading channels, human trafficking networks, and illegal mafia nexus can be identified using complex network analysis on their social networks. The most important issue in neutralizing such networks is the identification of key individuals in the antisocial networks so that a minimal set of actions can achieve the desired effect. Centrality analysis of individuals to identify the most important person in an antisocial network is often useful in neutralizing the network.
1.3.7 Enhanced Social Science Research through Social Networks
Prior to 2000, most social research was conducted through social experiments, games, or survey information collected directly from members of any particular society. The data was collected and analyzed using social network analysis. With the evolution of the Internet, WWW, and web-based social network services such as Facebook and Twitter, interaction between members of society substantially moved to the virtual world. As a result, much of the social science research done today draws on information from social networks formed over these web-based services. The data available from these sources is both vast and multidimensional. Today, most social science research depends on data from social networks. Therefore, complex network modeling and analysis of social network data become essential for deeper analysis of social networks.
1.4 Challenges in Studying Complex Networks
While complex network approach can be very useful for various areas of research and application, many challenges exist in its use. Following are the major challenges of studying complex networks:
High data volume Most of the real-world complex networks involve large numbers of nodes. Further, the complex presence of edges in the network results in huge data volume. For example, the Internet has many billions of nodes and edges. Storing and manipulating such large amounts of data requires sophisticated storage resources. Further, based on the approach used for analyzing the complex network dataset, intermediate processing required for data storage can be higher. For example, approaches such as graph signal processing require computation of eigenvectors and eigenvalues, which demand significant storage space.
Complexity in mapping physical systems to realistic complex network model Another major issue in complex network analysis is the difficulty in translating a real-world problem to a complex network model. In many real-world cases, only limited information about the nodes and edges of the physical world system can be captured to the complex network model. For example, consider a protein-protein interaction network where the edges are modeled on the basis of very limited interactions between proteins. In reality, the protein-protein interaction is far more complex, and it is challenging to model the complexity to the actual detailed level.
High computational complexity In order to characterize a real-world complex network, one needs a significant amount of computing resources. Therefore, algorithms must be efficient as well as able to process large-sized networks. Running complex network algorithms over large complex network datasets is computationally expensive. Approaches such as graph signal processing can take significant amounts of computing power to carry out complex network analysis of large real-world graphs.
1.5 What This Book Offers
This book offers a networking and signal processing perspective of complex networks. The networking aspects of complex networks, in this book, mainly focus on bringing out the overlap between computer networks and complex networks. The emergence of the Internet and the WWW resulted in the creation of several new complex networks such as complex physical networks of interconnecting computers, websites that hyperlink to other websites, and web-based social networks. It is beneficial to apply the tools and techniques from complex networks to achieve performance benefits in designing computer networks, including, but not limited to, architectures for network infrastructure, web-based social networks, WSNs, WMNs, and the Internet. Further, analyzing such large-scale computer networks entails using concepts from the complex networks field. Therefore, networking aspects of complex networks, in this book, present existing knowledge on scale-free networks, small-world networks, SWWMNs, and SWWSNs.
Since the nodes in a complex network generate huge amounts of data, it is of great interest to extract information from the data generated by the nodes of a complex network. Graph signal processing extends the concepts and tools developed in classical signal processing, such as translation, convolution, Fourier transform, filter banks, and wavelet transforms to data located on arbitrary networks. The field of graph signal processing is still in its nascent stage and has attracted a number of researchers from different communities such as networking, information sciences, signal processing, and statistical physics. This book presents various tools and concepts of graph signal processing developed in the past decade.
1.6 Organization of the Book
This chapter (Chapter 1) introduced the topics covered by the textbook, such as applications and the emerging relevance to complex networks.
Chapter 2 provides a preliminary discussion on graph theoretical foundations, which are necessary for grasping the rest of this book. While graph theory is an established area, we provide only the necessary elements required for understanding and appreciating complex networks topics.
Chapter 3 provides an introduction to complex networks where various examples and applications of real-world complex networks are discussed. This chapter serves as the introduction to the core areas covered by the book. A detailed discussion of the foundations of random networks is also provided in Chapter 3. Mathematical models corresponding to random networks and the estimated characteristics of random networks are essential topics covered in this chapter.
Small-world networks and their characteristics are presented in Chapter 4. Many real-world networks that are categorized as small-world networks and their key characteristics, such as APL, ACC, and other relevant properties, are presented. Many techniques used for creating small-world networks out of regular networks are also presented in this chapter.
Chapter 5 covers one of the most popular and interesting complex networks called scale-free networks. Scale-free networks are present in many natural and man-made physical world networks. In many examples of real-world networks, the evolutionary characteristics required for formation of scale-free networks are discussed in detail in Chapter 5.
Some of the applications of the small-world networks can be seen in wireless networks such as WMNs. Chapter 6 covers the use of small-world concepts in WMNs to create SWWMNs. SWWMNs benefit from performance improvement, low APL, and efficiency in resource management. This chapter also classifies the existing approaches for creating SWWMNs.
Similar to SWWMNs, another application area of small-world networking in wireless networking is WSNs. WSNs are used for monitoring and control of environmental parameters in large-scale sensor fields where sensor devices, which are tiny, inexpensive, and capable of sensing many physical world parameters, are deployed. Such WSNs benefit from application of small-world concepts for performance improvement. Chapter 7 presents benefits of using SWWSNs, challenges in designing them, existing techniques for transforming a WSN to SWWSN, and a set of open research issues.
Chapters 8 through 11 deal with the spectral analysis of complex networks and graph signal processing. Chapter 8 presents the eigenvalues and eigenvectors of various matrices related to a graph or a complex network. This chapter also serves as a preliminary to graph signal processing.
Chapter 9 discusses analysis and processing of data defined on complex networks, known as graph signals. Representations of graph signals have complex and irregular structures that require novel processing techniques, which has led to the emerging field of graph signal processing as discussed in Chapter 9.
Chapter 10 presents existing approaches for graph signal processing. There are mainly two frameworks for graph signal processing. The first method is based on the (symmetric) Laplacian matrix of the graph. The second method, known as the discrete signal processing on graphs (DSPG) framework, is rooted in the algebraic signal processing theory and based on the graph shift operator. Both of these frameworks are discussed in detail in Chapter 10.
Chapter 11 presents multiscale transforms for complex network data analysis. Wavelet transforms have the capability to simultaneously localize a signal content in both time and frequency that allows us to extract information from the data at various scales. This chapter presents various techniques for multiscale analysis of complex networks.
1.6.1 Suggested Navigation for Contents of the Book
Figure 1.4 shows the navigation flow of the chapters of this book. The introductory chapters (Chapters 1–3) provide the basics to understand the rest of the book. These chapters offer a motivation for the study of complex networks. Chapter 2 provides fundamentals of graph theory. Chapter 3 provides a brief technical introduction to complex networks. Those who are familiar with graph theory and its fundamentals can skip Chapter 2 and proceed to Chapter 3.
Figure 1.4. Suggested navigation sequence for contents of the book
After reading Chapters 1, 2, and 3, a reader may take two major directions: (i) complex networks and (ii) graph signal processing. Chapters 4 and 5 cover small-world networks and scale-free networks. After having some foundations of small-world networks, a reader may proceed to reading in the direction of computer networks where many applications of small-world approaches in wireless networks are presented, including SWWMNs and SWWSNs.
Computer scientists may read through Chapters 3 and 4, before focusing on Chapters 6 and 7.
After Chapter 3, a reader may also proceed to Chapters 8 through 11 that present the graph signal processing approaches for various complex networks. Readers who are familiar with complex networks and who want to understand graph signal processing concepts can read Chapters 8 through 11 straightaway.
While each chapter is written in a self-contained manner, the textbook provides necessary references to the required topics present in other chapters as well as those in research literature. Therefore, reading any chapter individually is not difficult.
1.7 Support Materials Available for Instructors
This book provides many support materials for instructors. First, a set of presentation slides for each chapter is provided with all the images and the LaTeX source code of the presentation slides. Instructors may customize the slides with additional information applicable to their classroom lectures.
Second, a solution manual, covering answers to most of the end-of-chapter exercises, is provided. Instructors may request a copy of the solution manual from the publisher. Computer-based exercises, marked with the 
symbol, require a computer to execute, and results can be obtained by the readers. Challenge exercises are problems, marked with the symbol 
, for which no solution exists in the current literature, and they are good research problems that can challenge an aspiring researcher. The solution manual provides answers or hints for answers for all exercises other than computer-based and challenge exercises.
Third, a set of code fractions for selected algorithms/programming exercises are available for download through the book’s website. Additional programming samples, exercises, and support materials will be made available online through the course website.
Finally, in addition to the online information for the book provided by the publisher, authors maintain a support website (https://complexnetworksbook.github.io) to provide the following: (i) errata of the textbook as and when errors are noticed, (ii) helpful additional exercise problems relevant for the chapters, (iii) presentation slides for the textbook, (iv) updates on new datasets and tools, and (v) information on the emerging topics in the complex networks research area. Readers are advised to check the support website once in a while.
1.8 Summary
Complex networks are present in many areas of our physical world. Modeling real-world complex systems into graph models results in complex networks. Studying such complex network models helps in identifying the characteristics of existing complex systems. This chapter reviewed some of the characteristics, applications, and challenges of complex networks and presented the topics covered by this book.