Open Access is an initiative that aims to make scientific research freely available to all. To date our community has made over 100 million downloads. It’s based on principles of collaboration, unobstructed discovery, and, most importantly, scientific progression. As PhD students, we found it difficult to access the research we needed, so we decided to create a new Open Access publisher that levels the playing field for scientists across the world. How? By making research easy to access, and puts the academic needs of the researchers before the business interests of publishers.

We are a community of more than 103,000 authors and editors from 3,291 institutions spanning 160 countries, including Nobel Prize winners and some of the world’s most-cited researchers. Publishing on IntechOpen allows authors to earn citations and find new collaborators, meaning more people see your work not only from your own field of study, but from other related fields too.

The knowledge of node’s ability and importance in spreading information in a complex network is important for developing efficient methods either to decelerate spreading in the case of diseases or to accelerate spreading in the case of information flow, which would benefit the whole population. Some systems are highly affected by a small fraction of influential nodes. Number of fast and efficient spreaders in a network is much less compared to the number of ordinary members. Information about the influential spreaders is significant in the planning for the control of propagation of critical pieces of information in a social or information network. Identifying important members who act as the fastest and efficient spreaders is the focal theme of a large number of research papers. Researchers have identified approximately 10 different methods for this purpose. Degree centrality, closeness centrality, betweenness centrality, k‐core decomposition, mixed degree decomposition, improved k‐shell decomposition, etc., are some of these methods. In this expository article, we review all previous works done in the field of identifying potential spreaders in a network.

Keywords

social networks

information diffusion

node centrality

m‐ranking

k‐shell decomposition

improved k‐shell decomposition

weighted k‐shell decomposition

directed networks

degree centrality

closeness centrality

betweenness centrality

chapter and author info

Authors

Reji Kumar Karunakaran*

Department of Mathematics, N. S. S College, Pandalam, Kerala, India

Shibu Manuel

Department of Mathematics, St. Dominic’s College, Kanjirapally, Kerala, India

Edamana Narayanan Satheesh

Department of Mathematics, N. S. S. Hindu College, Changanacherry, Kerala, India

*Address all correspondence to: rkkmaths@yahoo.co.in

Identifying and analyzing various kinds of network have become an important theme in the frontiers of research for the past 50 years. It is an emerging area which demands research activities of interdisciplinary and collaborative nature. Network research spreads over a variety of fields such as Mathematics, Physics, Chemistry, Computer Science, Biology and Social Sciences. Recently, network research has proved its importance by establishing itself as a new domain of research. It brings together and coordinates activities and research findings of researchers from other fields. Based on the nature and type of subject area and research, the entire field is divided into many subfields. Social networks, biological networks, chemical networks, physical networks, information networks, etc., are some of the most important ones.

Networks are being used for representing, analyzing and explaining complex systems. Complex systems have structural and behavioral characteristics. Both characteristics influence each other. Structural properties enable us to classify networks as random networks, scale‐free networks, small‐world networks and so on. Networks have been almost completely studied on the basis of its structure. Current scenario in the field is to establish relationship between the structural properties and the behavior of the network. When we speak of behavior, the behavior of the members and the behavior of the entire network come into picture. Behavior of the entire network is either the average of the behavior of the members or the totality of the behavior of the members.

An important area in the behavioral study on a network is the study of flow of information among the members. Information in this context of study is very general, which can be interpreted as spread of virus either in human contact networks [1, 2] or in a computer network [3, 4]. In some context, it is a spread of person‐specific information in ego networks [5], or rumor that spreads in social networks [6, 7]. Irrespective of the nature and content of the information, there are some important factors which greatly affect the whole process of information diffusion in a social network. Structure of the underlying network is one factor. It is a global property. Ego networks and neighborhood of each actor in a network are important properties, which are classified as local properties. Rumor spread in social networks has got special attention as a kind of information spread. Rumor is unverified and instrumentally relevant information, the origin of which is uncertain and usually spread by word of mouth. Gossip and urban legend are also forms of information which spread in a social network by the way of social contacts. Character of the actors who receive a piece of information and transmit to other is a third factor, which would also greatly affect the information diffusion process.

In this chapter, we concentrate on some aspects of network‐specific properties that influence transmission of information. Role of actors in a network varies according to their relative importance in the network and difference in their character. Characteristic difference and its effect are far from the scope of this chapter. Details of contacts in a network give us very fruitful information about the transmission process. For example, if the network is completely connected, a piece of information can be received by any other in a single step. In a disconnected network, the chance of not receiving the information by some actor cannot be completely removed. If the structure of the network is like a tree, average time taken for the information to reach the nodes depends on the place where it is generated. If the source of information has connection with all the remaining actors, the spread can end in one step. Networks can be modeled as graphs in Mathematics in which nodes represent interacting elements and edges represent interaction among the interacting elements.

Importance of nodes in the transmission of information is a matter of great concern in literature of information diffusion in networks [8, 9, 10]. As mentioned in the previous paragraph, some nodes that have large number of connections are highly important in the sense that any piece of information in their hands may spread faster than that in the hands of others. In other words, degree of nodes in a network is a measure of the importance of nodes. Centrality is a measure of a network that characterizes the importance of nodes. In other words, centrality measures are useful to analyze how “central” an individual node in a network. It is a function that assigns a real number value to each vertex in a network. Based on the value of this function, we can rank the nodes in the network. This measure in some context is used to study flow of something in a network. In some other context, it is a measure of cohesion among actors [11]. A centrality measure which is meant for some purpose may not give the right conclusion in a different context. In the following section, we review some important centrality measures along with an analysis of its ability to rank nodes. Each centrality measure is developed either as a generalization of an existing measure or as a new method which rectifies the shortcoming of an existing methods. We also propose a new measure of centrality which considers the importance of all nodes and edges present in a network while calculating the function value of each node. This measure can uniquely rank each different node in a network in a different class. If two nodes are equally important in the network topology, they fall in the same class. Thus, this method is seems to be more powerful than all other methods.

Clear knowledge of powerful or influential nodes in a network is valuable for many reasons. Certain nodes play a key role in the propagation of information or in the spreading of disease. If we know the role of the nodes in dissemination of information, we can manage to control the speed of information transfer through the network. This technique has great applications in the control of disease and in blocking the diffusion of annoying information such as rumors, negative behaviors, spreading of virus and so on. It can also be used in the campaigning of government, political parties, NGOs, public agencies and even in advertisements.

In general, networks are dynamic. Dynamic networks change over time. In a dynamic network, some nodes which are very important in some point of time may lose its status at some later point of time. Some nodes which are initially inactive may become very important through the interactions with other members in the network. Centrality measures are classified as local metrics, global metrics and hybrid metrics. There are many centrality methods which can be used to rank spreaders such as degree, k‐shell, mixed degree decomposition, neighborhood coreness, extended neighborhood coreness and so on.

2. Comparison of important centrality measures

In this section, we discuss important centrality measures and relative importance. We also mention their drawbacks as evident from various contexts.

2.1. Degree centrality

In 1978, Freeman introduced the degree centrality [12]. He asserted that the degree of a focal node is the number of adjacencies in a network, that is, the number of nodes that the focal node is connected to. This is a basic centrality, and it is often used as a first step in the study of a network. The degree measure can be formulated as:

ki=CD(i)=∑jNxijE1

where iis the focal node and jrepresents all other nodes. Nis the total number of nodes. Xis the adjacency matrix, in which xij=1, if node iand jare connected and 0, otherwise.

The degree of a node is defined as the number of other nodes connected directly to a given node. In degree decomposition, we rank the nodes of a network according to the descending order of degrees of nodes. Nodes with highest degree are ranked 1, nodes with next higher degree as rank 2and so on. This ranking method is known as degree decomposition. The complexity of this method is O(n), where nis the number of nodes. It is a local metric. This is the first centrality measure that appeared in literature.

As an illustration, a network is given in the Figure 1 and degree of all vertices is calculated. There are six vertices of degree one. These vertices are labeled as 1, 2, 3, 7, 9 and 15. The vertex labeled 14 has degree two. The vertices 5, 6 and 13 have degree three, and the vertices 4, 10, 11 and 12 have degree four. The vertex 8 has degree six. In the sense of degree centrality, the vertex 8 is the most powerful in the network and the vertices 4, 10, 11 and 12 occupy the next lower position. In this class, there are four members. A close look in the network will reveal the fact that the status of the vertices 11 and 12 is same. But 10 is more powerful than 11 and 12, because it is connected to the most powerful member in the network (vertex 8). But 4 in that group is much weaker than 10, 11 and 12. Clearly, this ranking scheme lacks accuracy.

In the case of weighted networks, degree centrality can be extended as sum of weights. This measure has been labeled as node strength and formulated as follows:

Si=CDW(i)=∑jNwijE2

where Wis the weighted adjacency matrix, in which wijis greater than 0 if node iis connected to node j, and the value represents the weight of the link between iand j. This is equal to the usual degree centrality if the network is binary.

In both case, node strength is a rough measure, as it only takes into consideration a node’s total connections with other nodes in the network. Clearly, degree and strength are both indicators of the level of connections of a node to other nodes of the network. It is important to incorporate both these measures for studying the new centrality of a node.

In Ref. [12], a new centrality measure is proposed. It is the average of the number of nodes connected to a focal node and the strength of that node. It is calculated using the following formula.

CDwα(i)=ki(1−α)siαE3

In the formula, αis a parameter that can set between 0 and 1. If αis near 0, the degree is more important, and if it is near 1, then node strength is more important.

Directed networks add complexity to degree centrality as two additional aspects of a node’s involvement are to be incorporated in the calculations. The activity of a node can be quantified by the number of ties that originate from a node, denoted by Kout, and the number of ties that are directed toward a node, denoted by Kin. For a weighted network, Soutand Sincan be defined as the total weight attached to the outgoing and incoming ties, respectively. Taking into account the weights of the directed ties, the previous formula is modified in [12] to assess a node’s importance in a directed network:

CD−outwα(i)=ki(1−α)−outsiα−outE4

and

CD−inwα(i)=ki(1−α)−insiα−inE5

The value of α in these equations is defined as above.

2.2. Closeness centrality

The closeness centrality was also proposed by Freeman [13]. It is based on the length of the shortest paths among nodes in a network. In a binary network, the shortest path is found by minimizing the intermediary nodes, and its length is defined as the minimum number of ties linking the two nodes, directly or indirectly. We define the shortest distance between the vertices iand jas

d(i,j)=min(xih+…+xhj).E6

Here hstands for intermediary nodes on a path between nodes iand j. The basic assumption in shortest distance is that the intermediary nodes increase the cost of the interaction and the higher number of intermediary nodes increases the time taken for interaction between nodes. Again intermediary nodes are powerful third parties and can distort information or delay information passage between nodes. In unweighted networks, the shortest path of two nodes is through the smallest number of intermediary nodes.

Closeness centrality relies on the length of the paths from a node to all other nodes. Closeness centrality is defined as:

Cc(i)=[∑jNd(i,j)]−1E7

We know that diseases are more likely to be transferred from one person to another person if they have frequent interaction. Frequency of interaction can be quantified and used as weights of links. In weighted networks, distance between two nodes iand jis defined as

dw(i,j)=min(1wih+…+1whj).E8

where his intermediary nodes and wihdenotes its weights.

Here, closeness centrality is defined as

Cc(i)=[∑jNdw(i,j)]−1.E9

In Ref. [12], Opsahl et al. propose a new closeness centrality by introducing the tuning parameter α, in finding the least costly path. This ensures that the both the weights of the ties and the number of intermediary nodes are considered in the identification of length of the path. Thus, length of the path is defined as

dwα(i,j)=min(1(wih)α+…+1(whj)α).E10

In the formula, α is a tuning parameter. If α = 0, the proposed measure produces the same output as in the case of unweighted network. When α = 1, this method gives the same result as the method proposed by Freeman. A value α < 1 assigns the path with greatest number of intermediary nodes, the longest distance. Conversely, α > 1, the impact of additional intermediary nodes is relatively unimportant compared to the strength of the ties and paths with more intermediaries.

2.3. Betweenness centrality

Betweenness centrality is measured for each vertex in a network. It quantifies the number of times each node appeared as a bridge along the shortest path between any two other nodes. This measure was also proposed by Freeman in 1958 [12]. Betweenness centrality for unweighted networks is defined as

CB(i)=∑j≠i≠kgjk(i)gjk,E11

where gjkis the number of shortest paths between nodes jand kand gjk(i)is the number of shortest paths between nodes jand kand passing through node i. This quantity is added over all pairs of vertices in the network. In the case of weighted networks, betweenness centrality is defined as

CBwα(i)=∑j≠i≠kgjkwα(i)gjkwαE12

This can also be generalized to directed networks. The identification of the shortest path, and their lengths, in directed networks is similar to the process of undirected networks with an additional constraint. A path from one node to another node cannot be treated as connection in the reverse direction. Thus, a directed path is said to exist only if all edges in the path are directed in the same direction. As a result, the values of betweenness centrality calculated for a directed graph may significantly vary from that of the underlying undirected graph.

2.4. K‐core decomposition

In 2010, Garas et al. put forward a fast node ranking method called k‐shell decomposition [14] for large networks. The k‐shell or k‐core decomposition method partitions a network into substructures. This method assigns an index ksto each node, which is the rank of the node in the network, according to its importance. Nodes with high values of the ksare located at the center or core of the network, and nodes with low values of kslie in the periphery of the network. This way, the network is described by a layered structure, exposing the hierarchy of its nodes.

Now, we present a calculation of k‐shell for nodes in the network of Figure 1. First, we removes recursively from the network all nodes of the network with degree 1 and we assign the integer value ks=1to them. This procedure is repeated iteratively until there are only nodes with degree d≥2in the network. Subsequently, we removes all nodes with degree d=2. Again, this procedure is repeated iteratively until there are only nodes with degree d≥3left in the network and assign to them the integer value ks=2and so on. This procedure is applied until all nodes of the network have been assigned to one of the k‐shells. Thus, we partition all nodes of the network into different shells with an integer value. This is how the original k‐shell decomposition method works.

From the above network, we can assign ks=1to the vertices 1, 2, 3, 4, 7, 9, 14 and 15 in the first step. Then, we can assign ks=2to the vertices 5, 6 and 13. Finally, the vertices 8, 10, 11 and 12 get the value ks=3.These vertices are the most important in the network according to the assumptions of k‐shell decomposition method. There are three categories of vertices. Each contains more than one vertex, which are of different nature. Hence, we arrive at the conclusion that this method is far from attaining the aim of the method. Computational complexity associated with the k‐shell method is O(n). It is a global metric. As a means to overcome this inefficiency of the k‐shell decomposition method, a modified method called mixed degree decomposition method was proposed.

2.5. Mixed degree decomposition method

It was in 2013 that Zeng and Zhang proposed a modification of k‐shell method called the mixed degree decomposition (MDD) [8]. The method is described as follows. The k‐shell method is a dynamical network decomposition procedure in which the residual degree (number of links connected to the remaining nodes) of nodes is updated in each step while all the information of the removed nodes is dropped. In mixed degree decomposition method, both residual degree and exhausted degree (number of links connected to the removed nodes) of the nodes are recorded and the decomposition is based on both of them. For node i, exhausted degree is denoted by ki(e)and residual degree is denoted by ki(r). In each iteration, the nodes are removed according to the mixed degree defined by

ki(m)=k(r)+λki(e)E13

where λis a tunable parameter between 0 and 1. The detailed decomposition is described below.

Initially, k(m)of each node is equal to 0, since there is no removed node in the network.

Remove all nodes with least degree, denoted by M and assign them to the M‐shell.

Update k(m)of all the remaining nodes by ki(m)=k(r)+λki(e). Then, remove all nodes with k(m)smaller than or equal to M and assign them to the M‐shell also. This step is recursively carried on until k(m)of all remaining nodes are larger than M.

Repeat steps 2 and 3 as M value increases until all nodes in the network have been assigned to one of the shells.

When λ=1,this MDD method coincides with the degree centrality method, and when λ=0,this method coincides with the usual k‐shell decomposition. The MDD method is no longer integer since k(m)can be decimal when we take λbetween 0 and 1. The following simple example (Figure 2) illustrates the procedure of MDD method.

If a virus originates from a node with large exhausted degree, not only it has the same probability as the other nodes in the same shell to infect the nodes in the higher shells, but also it has a bigger branch of nodes in the lower shells to infect, so that this virus will end up covering much more nodes at the end. Thus, the information of the exhausted degree cannot be overlooked when ranking the nodes. The frequency of appearance of different nodes in MDD method is higher than in k‐shell decomposition. The k‐shell has limited number of ranks, and the number of nodes in each rank is quite high, which means that the node differences are not well distinguished in k‐shell decomposition. In MDD method, the nodes more differently ranked than k‐shell decomposition. So this method is preferred over the k‐shell decomposition method. Liu et al. proposed an improvement on the k‐shell decomposition in the year 2013. It is discussed below.

2.6. Improved k‐shell decomposition method

Improved k‐shell decomposition method [9] is calculated in terms of the distance from a target node to the network core, the spreading influence of the nodes within the same k‐shell values could be distinguished. The formula for improved k‐shell decomposition is that θ(i/ks)=(ksmax−ks+1)∑j∈Jdij,where ksmaxis the largest k‐core value of the network, dijis the shortest distance from the node ito the node j, and jis the set of nodes whose k‐shell value is the maximum. Using this θ(i/ks)value, we can rank the nodes of the network. Calculated values of θfor the network in Figure 1 are as given below. θ(15)=52,θ(1)=45,θ(2)=45,θ(3)=45,θ(4)=33,θ(7)=33,θ(14)=30,θ(9)=21,θ(5)=14,θ(6)=14,θ(13)=12,θ(8)=3,θ(10)=3,θ(11)=3,θ(12)=3.Here, nodes of the network are divided into eight different shells using the new method.

In Ref. [15], Young Deng et al. proposed a refinement for the k‐shell decomposition for unweighted network.

Here, the weight of the edge connection between iand jis defined as wij=ki+kj, where kiand kjare the degrees of node iand j, respectively. Next, for each node i, we calculate the weighted degree kiwusing the following measure

kiw=αki+(1−α)∑j∈Γiwij,E14

where Γiis the set of neighboring nodes of i, and αis a positive tuning parameter between 0 and 1 that can be set according to the requirement and data. If this parameter αis near 1, then the degree of nodes is taken as favorable. If α=1, this method becomes the usual k‐shell decomposition. If αis close to 0, then the high edge weight is taken as favorable. Since the weighted degree may be no longer an integer, the weighted degree is approximated to the nearest integer. After this, the pruning routine is same as the k‐shell decomposition method but is based on the weighted degree kiw. Using this method, we can partition the node set of the network into more shells.

Using the usual k‐shell decomposition, the nodes are portioned as follows. The vertices 1, 2, 3, 4, 7, 9, 14 and 15 have ks=1.Vertices 5, 6 and 13 have ks=2.Vertices 8, 10, 11 and 12 have ks=3.

By the weighted k‐shell decomposition (Wks) described above, the node partitions obtained are given in Table 1. Thus, the new method partitions set of nodes into seven shells, which indicate this method is more efficient (Table 1).

Sl. no.

Value of wk−s

Vertex labels

1

1

7, 15

2

2

1, 2, 3

3

3

9, 14

4

4

4, 5, 6, 13

5

5

10

6

6

11, 12

7

7

8

Table 1.

Ranks of nodes in the network given in Figure 3 by Wks.

An improved version of the weighted decomposition method was suggested by Reji Kumar et al. [16]. The calculation of the rank of the nodes is based on the following procedure. The total of weight kiwof the vertices are calculated to obtain the value T(G). So T(G)=q∑i=1nkiw.Here n is the number of nodes. The right‐hand side is multiplied by q to make T(G)an integer. Next, the vertex 1 is deleted to obtain a new graph G1=G−{1}.. Subsequently, we find T(G1).Then, we delete the vertex 2 to obtain G2=G−{2}and find T(G2)exactly as before. This procedure is repeated to obtain T(G)values of all vertices. Finally, we find the value T(G)−T(Gi)for the vertex i. The vertices are ranked on the basis of these values.

2.7. Decomposition using k‐shell iteration factor

Very recently, Wang and Zhao put forward a method for fast ranking of influential nodes [17] in complex networks. He also improves the k‐shell decomposition method using iteration factor. The method is as follows. Suppose node niis a node in the network and its k‐shell value is k. In the k‐shell decomposition, the total iteration number is m and niis removed in the n^{th} iteration of the k‐shell decomposition, where 1≤n≤m. Let δnidenotes the k‐shell iteration factor of node niwhich is defined as follows;

δni=k(1+nm).E15

The k‐shell iteration factor of each node can thus be obtained with this formula. For example, for the above unweighted figure for node 3, ks=1, n = 1 and m = 2; therefore, δn3=1.5. For node 4, n = 2, and m = 2, and δn4=2. Here, nodes 3 and 4 are in the same k‐shell, and this method distinguishes them with different δvalue. Thus, if we rank the nodes of the network with the calculated δvalue, this method will give a refinement of k‐shell decomposition.

2.8. Weighted k‐shell decomposition

One major limitation of most centrality measures, including k‐core decomposition method, is that they are designed for unweighted networks. However, in practice, real‐world networks are weighted, and their weights carry very valuable information about the strength or pace of flow of information through the edges. This information is highly critical in the study of transmission of information. In a weighted network, every node has two underlying attributes, their degree and weight of the edges incident with that node. Since weights are associated with networks links, the nodes weights are calculated as the sum over all link weights incident with a particular node. It may happen in network that a node with high degree can have small weight and vice versa. There are situations in which weights play important role. In such networks weights are related to some measured property. For example, in trade flow, capital flow, etc., nodes with high weight can usually be an important player. Thus, in such systems, the presence of nodes with high degree and relatively low weights may vary from the results obtained by methods that are based only on the degree of nodes. Under this approach, one completely neglects the weights and performs the analysis on unweighted network. In the second approach, consider only links and their weights and neglects degree.

Garas et al. gave the following method for weighted networks [14], called weighted k‐shell decomposition method (Wk‐shell). This method applies the same pruning method as in k‐shell decomposition. Here, we consider both degree of a node and weights of its links. We also assign for each node a weighted degree k′. The weighted degree of a node is defined as

ki'=[kiα(∑jkiwij)β]1α+β,E16

where kiis the degree of the node i, and ∑jkiwijis the sum of all link weights. αand βare two parameters. If α=β=1, the weight and degree equally get equal consideration in the calculation. If α=β=12, then the above equation becomes

ki1=ki∑jkiwij.E17

In the case of unweighted networks, where wij=1,the weighted degree is equivalent to the usual node degree and we use the same usual k‐shell decomposition method. In general, the weighted method is able to split further the cores obtained by the unweighted method and help us find the most central of the central nodes. Thus, it is reasonable to assume that the weighted k‐shell partitioning method provides us with a more accurate node ranking for representing the node’s spreading power.

In a recent article, Reji Kumar et al. [18] proposed a method in which degree and weights of all vertices and edges get relative representation in a network. This method is named as m‐ranking method. This method is discussed in the subsequent section.

2.9. The m‐ranking of nodes

Total power is calculated for each node in the m‐ranking method. Total power of a node iis defined by the formula,

In the formula, α=pqis a parameter between 0 and 1 and β>1is another parameter. It is good practice to choose βan integer close to the average degree of the nodes of the graph. The first series contains at most D+1terms, and the second series contains at most Dterms, where Dis the diameter of the graph. Here, di(0)is the degree of the node i,and ∑di(j)is the sum of the degrees of the nodes of the graph at a distance jaway from node i. Similarly, ∑Wi(0)is the sum of the weights of the incident edges of the node iand ∑Wi(j),is the sum of the weights of all edges which are jsteps away from the node i. Since we are considering degree of all nodes and weights of all edges, usually the total power of all nodes will be different except for vertices which are same with respect to an isomorphism. When βvalue is very large, this method tends to usual degree centrality. We rank the nodes in the descending order of total power T(i). If we put α=0, this method can be applied to unweighted networks. In Ref. [18], the authors have verified the reliability of this method using rank correlation method.

PageRank [19] is a method for rating web pages effectively by measuring the human interest and attention devoted to them. In the network of web pages, a webpage is a node and a hyperlink is a directed link in the network. It is the ranking method used by Google. In PageRank, a hyperlink is understood as an endorsement relationship. In this method, number and quality of links to a page are used to determine a rough estimate of how influential the web page is. This method was first introduced in 1976 by Gabriel Pinski and Francis Narin. The PageRank is defined as a function

PR(TA)=(1−d)+d(PR(T1)C(T1)+…+PR(Tn)C(Tn))E19

where PR(TA)is the page rank of TAand PR(Ti)is the page rank of Tiwhich is linked to TA. C(Ti)is the number of outbound links on page Ti, and dis a parameter between 0 and 1.

3. Conclusion

A large variety of node centrality measures are being used by network scientists to identify potential spreaders of information in a network. Degree centrality, betweenness centrality, closeness centrality, k‐core decomposition, mixed degree decomposition, improved k‐shell decomposition, weighted k‐shell decomposition, page ranking and m‐ranking method, etc., are important methods, which are discussed in this paper. These methods help us to rank the members in a network according to their importance. A method, which is suitable in some context, may not fit in another situation. Each method has its own strengths and weakness. The weakness of the methods motivates social scientists to redefine or modify the existing methods, which in turn leads to the development of new methods to rank the nodes in a better way. All the methods, except m‐ranking method, have been criticized about its inefficiency in uniquely ranking the members. In addition, some methods may give higher rank to less important nodes, while most important nodes being underestimated. It has been claimed that m‐ranking method is far better than all other methods, which are described above.

Acknowledgments

This research was completed with the financial assistance of University Grants Commission, India. First author is grateful to University Grants Commission for sanctioning a major research project titled, “Modeling of social ties; a modified approach”, No. F. No. 40‐243/2011 (SR).

Reji Kumar Karunakaran, Shibu Manuel and Edamana Narayanan Satheesh (December 20th 2017). Spreading Information in Complex Networks: An Overview and Some Modified Methods, Graph Theory, Beril Sirmacek, IntechOpen, DOI: 10.5772/intechopen.69204. Available from:

An Example Usage of Graph Theory in Other Scientific Fields: On Graph Labeling, Possibilities and Role of Mind/Consciousness

By Auparajita Krishnaa

Related Book

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.