Identifying influential nodes in a network is a fundamental issue due to its wide applications, such as accelerating information diffusion or halting virus spreading. Many measures based on the network topology have emerged over the years to identify influential nodes such as Betweenness, Closeness, and Eigenvalue centrality. However, although most real-world networks are modular, few measures exploit this property. Recent works have shown that it has a significant effect on the dynamics on networks. In a modular network, a node has two types of influence: a local influence (on the nodes of its community) through its intra-community links and a global influence (on the nodes in other communities) through its inter-community links. Depending of the strength of the community structure, these two components are more or less influential. Based on this idea, we propose to extend all the standard centrality measures defined for networks with no community structure to modular networks. The so-called "Modular centrality" is a two dimensional vector. Its first component quantifies the local influence of a node in its community while the second component quantifies its global influence on the other communities of the network. In order to illustrate the effectiveness of the Modular centrality extensions, comparison with their scalar counterpart are performed in an epidemic process setting. Simulation results using the Susceptible-Infected-Recovered (SIR) model on synthetic networks with controlled community structure allows getting a clear idea about the relation between the strength of the community structure and the major type of influence (global local). Furthermore, experiments on real-world networks demonstrate the merit of this approach.
N. @cite_24 proposed a degree-based centrality measure for networks with non-overlapping community structure. It is based on a non-linear combination of the number of intra-community links and inter-community links. The goal is to select nodes that are both hubs in their community and bridges between the communities. This measure gives more importance to community bridges. Indeed, the number of inter-community links is raised to the power of two. Comparison have been performed with deterministic and random immunization strategies using the S.I.R epidemic model and both synthetic and real-world networks. Nodes are immunized sequentially from each community in the decreasing order of their centrality value in their respective community. Number of nodes to be removed from a community are kept proportional to the community size. Results show that the Comm strategy is more effective or at least works as well as Degree and Betweenness centrality while using only information at the community level.
@cite_24
2263392086 1992250165 2161283706 2152091390
Understanding the network structure, and finding out the influential nodes is a challenging issue in large networks. Identifying the most influential nodes in a network can be useful in many applications like immunization of nodes in case of epidemic spreading, during intentional attacks on complex networks. A lot of research is being done to devise centrality measures which could efficiently identify the most influential nodes in a network. There are two major approaches to this problem: On one hand, deterministic strategies that exploit knowledge about the overall network topology, while on the other end, random strategies are completely agnostic about the network structure. Centrality measures that can deal with a limited knowledge of the network structure are of prime importance. Indeed, in practice, information about the global structure of the overall network is rarely available or hard to acquire. Even if available, the structure of the network might be too large that it is too much computationally expensive to calculate global centrality measures. To that end, a centrality measure is proposed here that requires information only at the community level. Indeed, most of the real-world networks exhibit a community structure that can be exploited efficiently to discover the influential nodes. We performed a comparative evaluation of prominent global deterministic strategies together with stochastic strategies, an available and the proposed deterministic community-based strategy. Effectiveness of the proposed method is evaluated by performing experiments on synthetic and real-world networks with community structure in the case of immunization of nodes for epidemic control. Identifying influential nodes that lead to faster and wider spreading in complex networks is of theoretical and practical significance. The degree centrality method is very simple but of little relevance. Global metrics such as betweenness centrality and closeness centrality can better identify influential nodes, but are incapable to be applied in large-scale networks due to the computational complexity. In order to design an effective ranking method, we proposed a semi-local centrality measure as a tradeoff between the low-relevant degree centrality and other time-consuming measures. We use the Susceptible–Infected–Recovered (SIR) model to evaluate the performance by using the spreading rate and the number of infected nodes. Simulations on four real networks show that our method can well identify influential nodes. Simulation studies using susceptible-infectious-recovered models were conducted to estimate individuals’ risk of infection and time to infection in small-world and randomly mixing networks. Infection transmitted more rapidly but ultimately resulted in fewer infected individuals in the small-world, compared with the random, network. The ability of measures of network centrality to identify high-risk individuals was also assessed. ‘‘Centrality’’ describes an individual’s position in a population; numerous parameters are available to assess this attribute. Here, the authors use the centrality measures degree (number of contacts), random-walk betweenness (a measure of the proportion of times an individual lies on the path between other individuals), shortest-path betweenness (the proportion of times an individual lies on the shortest path between other individuals), and farness (the sum of the number of steps between an individual and all other individuals). Each was associated with time to infection and risk of infection in the simulated outbreaks. In the networks examined, degree (which is the most readily measured) was at least as good as other network parameters in predicting risk of infection. Identification of more central individuals in populations may be used to inform surveillance and infection control strategies. Measuring the centrality of nodes in real-world networks has remained an important task in the technological, social, and biological network paradigms carrying implications on their analysis and applications. Exact inference of centrality values is infeasible in large networks due to the need to solve the all-pairs shortest path problem. We introduce a framework to approximate node centralities in real-world networks that are known to exhibit modularity, i.e., the presence of dense subgraphs or communities, which are themselves sparsely connected. We also propose a novel centrality measure known as Community Inbetweenness that ranks nodes based solely on community information. In a modular network of size n with √n(1 2) evenly sized communities and m edges, our framework requires linear time O(m) and O(√nm) time for the approximation of closeness and betweenness respectively. Utilizing a recently proposed linear time method in community detection, our approximation techniques are faster than traditional sampling algorithms, applicable in real-time distributed environments, and offer highly comparable results.