Many popular measures used in social network analysis, including centrality, are based on the random walk. The random walk is a model of a stochastic process where a node interacts with one other node at a time. However, the random walk may not be appropriate for modeling social phenomena, including epidemics and information diffusion, in which one node may interact with many others at the same time, for example, by broadcasting the virus or information to its neighbors. To produce meaningful results, social network analysis algorithms have to take into account the nature of interactions between the nodes. In this paper we classify dynamical processes as conservative and non-conservative and relate them to well-known measures of centrality used in network analysis: PageRank and Alpha-Centrality. We demonstrate, by ranking users in online social networks used for broadcasting information, that non-conservative Alpha-Centrality generally leads to a better agreement with an empirical ranking scheme than the conservative PageRank.
@cite_28 studied measures similar to Alpha-Centrality and personalized PageRank (with attenuation factor 1) which they call communicability. They linked the communicability functions to dynamics by showing their relationship to the thermal Green's function of oscillators. They used communicability to identify important actors in small social networks, demonstrating that different communicability functions led to different judgements of centrality, but did not justify the choice of the particular communicability function in terms of the interactions taking place between actors. Although we study a similar function, the goal of our work is to contrast conservative and non-conservative dynamics and explain how these differences should guide the choice of centrality measure for a given social network.
@cite_28
2092598586
Abstract A fundamental problem in the study of complex networks is to provide quantitative measures of correlation and information flow between different parts of a system. To this end, several notions of communicability have been introduced and applied to a wide variety of real-world networks in recent years. Several such communicability functions are reviewed in this paper. It is emphasized that communication and correlation in networks can take place through many more routes than the shortest paths, a fact that may not have been sufficiently appreciated in previously proposed correlation measures. In contrast to these, the communicability measures reviewed in this paper are defined by taking into account all possible routes between two nodes, assigning smaller weights to longer ones. This point of view naturally leads to the definition of communicability in terms of matrix functions, such as the exponential, resolvent, and hyperbolic functions, in which the matrix argument is either the adjacency matrix or the graph Laplacian associated with the network. Considerable insight on communicability can be gained by modeling a network as a system of oscillators and deriving physical interpretations, both classical and quantum-mechanical, of various communicability functions. Applications of communicability measures to the analysis of complex systems are illustrated on a variety of biological, physical and social networks. The last part of the paper is devoted to a review of the notion of locality in complex networks and to computational aspects that by exploiting sparsity can greatly reduce the computational efforts for the calculation of communicability functions for large networks. The total communicability of a network (or graph) is defined as the sum of the entries in the exponential of the adjacency matrix of the network, possibly normalized by the number of nodes. This quantity offers a good measure of how easily information spreads across the network, and can be useful in the design of networks having certain desirable properties. The total communicability can be computed quickly even for large networks using techniques based on the Lanczos algorithm. In this work we introduce some heuristics that can be used to add, delete, or rewire a limited number of edges in a given sparse network so that the modified network has a large total communicability. To this end, we introduce new edge centrality measures, which can be used as a guide in the selection of edges to be added or removed. Moreover, we show experimentally that the total communicability provides an effective and easily computable measure of how "well-connected" a sparse network is. We introduce new broadcast and receive communicability indices that can be used as global measures of how effectively information is spread in a directed network. Furthermore, we describe fast and effective criteria for the selection of edges to be added to (or deleted from) a given directed network so as to enhance these network communicability measures. Numerical experiments illustrate the effectiveness of the proposed techniques. Degree centrality is considered to be one of the most basic measures of social network analysis, which has been used extensively in diverse research domains for measuring network positions of actors in respect of the connections with their immediate neighbors. In network analysis, it emphasizes the number of connections that an actor has with others. However, it does not accommodate the value of the duration of relations with other actors in a network; and, therefore, this traditional degree centrality approach regards only the presence or absence of links. Here, we introduce a time-variant approach to the degree centrality measure — time scale degree centrality (TSDC), which considers both presence and duration of links among actors within a network. We illustrate the difference between traditional and TSDC measure by applying these two approaches to explore the impact of degree attributes of a patient-physician network evolving during patient hospitalization periods on the hospital length of stay (LOS) both at a macro- and a micro-level. At a macro-level, both the traditional and time-scale approaches to degree centrality can explain the relationship between the degree attribute of the patient-physician network and LOS. However, at a micro-level or small cluster level, TSDC provides better explanation while the traditional degree centrality approach is found to be inadequate in explaining its relationship with LOS. Our proposed TSDC measure can explore time-variant relations that evolve among actors in a given social network.