Open access peer-reviewed chapter

Controllable Subspace as a New Characterization of Influence of Nodes in Complex Networks

By Jiuhua Zhao

Reviewed: November 9th 2016Published: February 1st 2017

DOI: 10.5772/66783

Downloaded: 639

Abstract

In this chapter, we investigate the influence of a node on a network. By virtue of the classical control theory, the influence of a node is represented by the controllable subspace, which is further transformed into a specified graph named general‐cacti. An algorithm is developed to calculate the influence, which contains the searching of different kinds of circles and the longest path in the directed graph. Moreover, eight real networks are studied and simulations show that (1) a node in dense and homogeneous networks could have more influence comparing with nodes in sparse and heterogeneous networks, (2) any single studied classical centrality measure including output degree, betweenness and PageRank could not rank the influence and (3) a node with high rank in all these three measures could have more influence.

1. Introduction

With the development of society and technology, nowadays lots of industry and manmade systems have become larger and larger. Different from traditional systems, these systems have a large amount of state variables and complex connection between states. Usually the variables, which capture the connection between states, are unable to measure and at the same time these variables can be easily changed for reasons of temperature, humidity and so on. Hence, these complex systems are difficult to analyze by using classical control theory. In the 1970s, a new control conception, structural controllability, was first introduced by Ching‐Tai Lin in 1974 [1]. In Ref. [1] the complete structural controllability of systems with single input was studied. Shields and Pearson [2] extended the result of Lin to multiple input structural systems. Glover and Silverman [3] simplified the work of Shields and Pearson. The conception of structural controllability allows part of systems of the same structure, though with measure of zero, be uncontrollable. Mayeda and Yamada [4] introduced the conception of strong structural controllability to eliminate this kind of uncontrollability. Reinschke et al. [5] studied the conception in multiinput and multioutput systems. Jarczyk et al. [6] revisited the previous results and gave out a new graph‐theoretic characterization of strong structural controllability. The solid foundation of structural controllability had been laid down from then on. For those structural uncontrollable systems, the structural controllable subspace is studied by Hosoe [7] and Poliak [8]. All these studies shed light on the study on the systems where the variables, which capture the connections between states, are unmeasured or mutable. When the system becomes larger, the methods and algorithms mentioned by the above literature studies become inapplicable for the reason of complexity of computation. Recently, Liu et al. [9] combined the structural controllability theory with the complex network, by using the algorithm of maximum match to calculate the minimum input nodes for complete control and methods of complex network science to analyze the properties of the input nodes. Since then more and more studies have been dedicated to controllability of complex network. Nepusz and Vicsek [10] used edge dynamics to describe the controllability of complex networks. Banerjee and Roy [11] exploited the property of driver nodes and made some supplement for the result of Liu et al. All the existing literature studies about the controllability of complex networks are focused on complete controllability. How about those complex networks, who are not controllable with the given diver nodes? Among hundreds even thousands or billions nodes, what role does a single node actually play? How many nodes will it affect, if it is chosen as a driver node? What properties do those nodes with powerful control ability have? All these questions motivated us to study the problem when networks are not fully controlled.

The chapter is organized as follows. In Section 2, some useful preliminaries and the model descriptions are introduced. In Section 3, an algorithm to search for the influence of a single node is proposed and we apply it to several real complex networks in Section 4. Finally, Section 5 contains concluding remarks.

2. Preliminaries and model description

Consider a linear time‐invariant control system

x˙=Ax(t)+Bu(t)E1

where x(t)Rn, u(t)Rmand we assume that Aand Bare structural matrices, which means all elements in the matrix are either fixed (zero) or unfixed (indeterminate) and the indeterminate parameters are unrelated. Hereafter Eq. (1) is called a structural system and denoted by (A,B). Let [A  B]denote the matrix of the system and G(V,E)denote the digraph of the system. We generate a digraph G(V,E)from (A,B), with n+mnodes, V=v1,,vn,vn+1,,vn+m, where v1,,vnrepresent the state nodes of (A,B)and vn+1,,vn+mrepresent the control nodes. And all those edges are generated as follows: for every fixed entry mijof [A  B], the graph contains an oriented edge (vi,vj). For a structural system (A,B), his corresponding fixed system is denoted by (A^,B^), where unfixed parameters in (A,B)are filled by one class of unrelated real numbers.

Definition 1: A system (A,B)is structural controllable if all its possible fixed systems (A^,B^)are controllable.

The above definition was first introduced by C‐T Lin. He reduced the property of structural property to the property of the graph of the system.

Definition 2 (stem) [1]: A stem is an elementary path originating from an input vertex (see Figure 1).

Figure 1.

Stem.

Definition 3 (bud) [1]: A bud is an elementary cycle with an additional edge that ends, but not begins, in a vertex of the cycle. Vertex v1is called the origin of the bud (see Figure 2).

Figure 2.

Bud.

Definition 4 (cactus) [1]: A cactus is defined recursively as follows. A stem is cacti. Given a stem S0and buds B1,B2,,Bp, then S0B1Bpis a cacti if for every i(1ip)the origin vertex of Biis also the origin of an edge in S0B1Biand is the only vertex belonging the same time to Biand S0B1Bi. A set of disjoint cacti is called cactus (see Figure 3).

Figure 3.

Cacti.

We call the red node in Figure 3, i.e., the input vertex, driver node and the nodes connected to driver node are defined as driven nodes(e.g., node d1and d2in Figure 3.

Theorem 1 (Lin) [1]: The single input system pair (A,b)is structurally controllable iff the graph of (A,b)is spanned by cacti.

Many works have been done to study the complete controllability of a system. Hosoe considered the problem for the first time, where the system is not fully controllable. He defined the maximal dimension of controllability matrix of the structural system as the generic dimension of controllable subspace, denoted by dc=gennericrank[AABAn1B]. And give out two methods for determining the generic dimension of controllable subspace of a system. We show the graph‐theoretic method here (see Theorem 1).

Theorem 2 [2]: Let dcbe the generic dimension of the controllable subspace of the structural system (A,B)and G(A,B)represents the graph of (A,B). Assume that [A  B]is irreducible. Then dc=maxG˜G{|E(G˜)|}where Gdenotes the subgraphs of G(A,B)which is defined by

and |E(G˜)|represents the number of edges in graph G˜. Comparing with the graphic properties of complete controllable system in Lin [1], the graph of controllable subspace contains more circles than cactus. Those circles are not directly connected to the cactus in the form of buds. They are connected to the cactus through at least one node. We define the circle in G˜as a general‐bud. Then replacing all the buds in cacti by general‐buds, we can have the definition of general‐cacti (see Figure 4). In Figure 4, those circles with dash lines are the defined general‐bud.

Figure 4.

General‐cacti.

In our research, we consider the influence of a single node in the complex network. By the influence of node i, we mean the controllable subspace of the system when we only control node i. Then we denote the structural input vector as bi, where all elements in vector biare fixed zero except for the ith element. Therefore, we can just study the controllable subspace of structural system (A,bi), whose corresponding structural matrix and digraph are denoted as [A  bi]and Gi. Let us define the controllability of a node iin a complex network as Pi. Then we can easily derive Pifrom Theorem [1], i.e.,

Pi=maxG˜iGi{|V(G˜i)|}E2

where Gidenotes the set of general‐cacti originated from node iin digraph Gi. To ignore the influence of the network size, the influence of node iis normalized as pi=Pi/N.

3. Algorithm

To find the largest general‐cacti, we classify the circle in the network into three categories. The first one is circles with no inbound (see Figure 5a). This kind of circles cannot be arrived by the input, so they are not in our general‐cacti. The second one is circles with no outbound edges (see Figure 5b). This kind of circles can only act as general‐buds in the general‐cacti without affecting the competition of two different general‐cactus. The third one is circles with both inbound and outbound edges (see Figure 5c). These circles can also be part of a stem, which means these nodes affect the dimension of general‐cacti.

Figure 5.

Circles of three categories.

Our instinct is exploring the longest path to act as a stem and then add all the circles as the general‐buds. Nevertheless, the third kind of circles makes it difficult to search for the largest general‐cacti. As shown in Figure 6, the blue stem in (b) is longer than the red one in (a), but the circle can also act as a general‐bud to increase the dimension of controllable subspace. Hence, the dimension of general‐cacti in (a) is larger than the one in (b).

Figure 6.

(a, b) Two different cacti in the same network.

However, if the circle of the third kind is not large enough, the choice of the longest path will not affect the influence of the origin node significantly. When the circle is large enough, we set it as a general‐bud to prevent it from participating in the stem forming. The definition of “large” affects the accuracy of our method. However, from the real database we find that the circles are either very small or very large. Our method is efficient in real networks. Thus far we can give an approach to discover the influence of a single node in the complex network.

3.1. Procedure to discover the influence of a single node

  • Search the reachable nodes from node iin the original graph and delete all those unreachable nodes.

  • Search for the second category circles in the current graph, count the number (N1) of their nodes, then delete all those nodes and the edges connected to them.

  • Search for large circles in the current graph, count the number (N2) of their nodes, then delete all those nodes and the edges connected to them.

  • Search for the longest path originate from the input in the current graph, count the number (N3) of the nodes, then delete all those nodes and the edges connected to them.

  • Search for all the circles left in the current graph, count the number (N4) of the nodes, then delete all those nodes and the edges connected to them.

  • Pi=N1+N2+N3+N4

The first, second and fourth steps of this procedure are all about search for the directed circle in the digraph. We recursively delete the nodes without any input or without any output. Then we can get all the nodes in circle. Using the depth‐first search method, we can separate these nodes into different circles and count for the number of nodes of each circle. For the circle, which has small circles inside, we just count the largest circle.

The third step of this procedure is the most difficult one. To the best of our knowledge, there exist no optimal algorithms to search for the longest path in the digraph. The existing algorithms of searching for the shortest path cannot be modified to search for the longest path, for the existing of directed circles. We modify the classical depth‐first search method to search for the longest path in a digraph with directed circles (see Algorithm 1).

Algorithm 1 Algorithm to search for the longest path in a digraph

Require: vNULL

Ensure: Long(v)

deepdeep+1, visited(v)1,

vexdeep(v)deep,

vex the vertex v directs to

while vexNULLdo

if visited(v)=0and (circle(v)0or

deepvexdeep(v)) then

Long(vex)

visited(v)0

vex the vertex v directs to

deepdeep1

 else if visited(v)=1then

for all vertex iin the current circle do

circle(i)1

end for

vex the vertex which has the same origin as vex

else

vex the vertex which has the same origin as              vex

end if

end while

In the algorithm, we use vector visitedand circleto mark the node. Node iis visited (in a circle) if visited(i)=1(circle(i)=1), otherwise unvisited (not in a circle). We use deepto record the current depth and vector vexdeepto record the depth of every vertex. The most significant difference between our method and the depth‐first search method is that we allow one vertex to be detected more than one time and at the same time we record the circles in the network for searching in other directions. The time complexity of our algorithm is O(NM), where Nis the number of nodes in the network and Mdenotes the number of edges.

4. Simulation results

We now apply the proposed algorithm to several kinds of real networks. It is infeasible to search all the nodes to find out the most influential node, for the unbearable complexity. Hence, we rank the node by their ODCR (outcome‐degree centrality rank), BCR (betweenness centrality rank) and PR (page rank), then analysis the first three nodes of every categories. Form Table 1, we can find that nodes in dense and homogeneous networks, like network Caenorhabditis elegans, network Seagrass, network s838, network s420 and network s208, can control more percentage of nodes than nodes in sparse and heterogeneous networks. This phenomenon implies that nodes are more influential in dense and homogeneous networks. We think it is reason why dense and homogeneous networks need less driver nodes for full structural control which is observed in [9].

TypeRegulatoryNeuronalFood webElectronic circuits
NameTRN‐Yeast‐1 [12]TRN‐Yeast‐2 [12]TRN‐EC‐2 [12]Caenorhabditis elegans [13]Seagrass [14]S838 [12]S420 [12]S208 [12]
N444168841829749512252122
L1287310795192345226819399189
nD96.5%82.1%75.1%16.5%26.5%23.2%23.4%23.8%
pODR10.97%0.29%0.96%58.59%24.49%31.64%32.54%34.43%
pODR21.10%0.44%0.48%58.59%22.45%2.73%31.35%24.60%
pODR31.15%0.29%0.72%56.9%16.33%26.95%3.17%31.97%
pBCR11.15%0.73%0.96%0.34%24.49%31.64%3.17%5.74%
pBCR21.10%0.44%1.20%58.59%14.29%7.42%3.17%34.43%
pBCR31.04%0.29%0.48%58.59%10.20%1.76%3.57%18.03%
pPR11.15%0.29%0.96%0.34%10.20%31.64%32.54%34.43%
pPR21.10%0.44%0.48%58.59%14.29%2.34%31.35%5.74%
pPR30.97%0.44%0.72%58.59%12.24%2.73%5.95%12.30%

Table 1.

The influence of the studied nodes in eight real networks.

From Figure 7, we find influence of node does not rank according to any single studied centrality measure. In fact, in network Yeast‐1, nodes ODR3, BCR1 and PR1 are the same node and it has largest influence 1.15% among the considered nodes. In network Yeast‐2, nodes ODR2, BCR2 and PR2 are the same node and it has the largest influence 0.44%. In network EC‐2, nodes ODR1, BCR1 and PR1 are the same node and it has the largest influence 0.96%. In network elegans, nodes ODR1, BCR2 and PR2 are the same node and it has the largest influence 58.59%. In network Seagrass, nodes ODR1 and BCR1 are the same node and it has the largest influence 24.49%. In network s838, nodes ODR1, BCR1 and PR1 are the same node and it has the largest influence 31.64%. In network s240, nodes ODR1 and PR1 are the same node and it has the largest influence 32.54%. In network s208, nodes ODR1, BCR2 and PR1 are the same node and it has the largest influence 34.43%. Hence, we can conclude that if a node has a high ODCR, BCR and PR at the same time, this node can have lager influence.

Figure 7.

The influence of top three nodes according to each centrality measure in eight real networks.

5. Conclusions

In this chapter, we have introduced the notion of the influence of a node in complex networks and gave out a useful algorithm to count for that property. Meanwhile we applied this method to exploit the influence of nodes in some real networks. Results have shown that nodes in dense and homogeneous networks were more influential than nodes in sparse and heterogeneous networks. And in the same network node which has high rank in ODR, BCR and PR simultaneously could be more influential. Next we will try to study the characteristic of the most influential node in a complex network and the influence of a set of nodes.

© 2017 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Jiuhua Zhao (February 1st 2017). Controllable Subspace as a New Characterization of Influence of Nodes in Complex Networks, Proceedings of the 2nd Czech-China Scientific Conference 2016, Jaromir Gottvald and Petr Praus, IntechOpen, DOI: 10.5772/66783. Available from:

chapter statistics

639total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Distributed Consensus‐Based Estimation with Random Delays

By Dou Liya

Related Book

First chapter

Traffic Management by Admission Control in IMS Networks

By Ivan Baroňák, Michal Čuba, Chien-Ming Chen and Ladislav Beháň

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us