An Introduction to Complex Networks
Reviews some of the characteristics, applications, and challenges of complex networks.
Save 35% off the list price* of the related book or multi-format eBook (EPUB + MOBI + PDF) with discount code ARTICLE.
* See informit.com/terms
This chapter is from the book
This chapter is from the book
This chapter is from the book
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 G = {V, E, W} where V 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.
){kind=link}