A Graph-Theoretical Basis of Stochastic-Cascading Network Influence: Characterizations of Influence-Based Centrality

Ker-I Ko (葛可一, 1950-2018) made multiple pioneering and milestone contributions to structural complexity theory and real-number computation. His sharp perception of both discrete and continuous structures had lead him to study fundamental concepts from one-way functions, to polynomial-time hierarchy, from integral equations, to real functions, from fractals to fixed-points, from optimization to relativization, from instance complexity to real complexity, from NP-completeness to exponential-time completeness. In his final two years, he turned his focus to game-theoretical designs for dynamic processes over social networks.

For this honorary special issue in memory of Professor Ker-I Ko, we are pleased to be able to contribute a paper with scope intersecting the areas that drew his last attention, and with results connecting discrete and continuous formulations of network dynamics. We prove that the complex stochastic network-influence processes have a simple graph-theoretical basis: Every stochastic-cascading influence profile can be written as a linear combination of breadth-first-search-based broadcast-propagations over layered-graphs. This graph-theoretical basis of stochastic network influence provides us with a systematic framework for studying the following fundamental question in network analysis:

How should one assess the centralities of nodes in an information/influence propagation process over a social network?

Our framework systematically extends a family of classical graph-theoretical centrality formulations  including degree centrality, harmonic centrality, and various notions of “sphere-of-influence” to influence-based network centralities. Given that group cooperation is essential in social influences, we further extend natural group centralities from graph models to influence models, enabling us to assess individuals’ centralities in group influence settings by applying the fundamental concept of Shapley value from cooperative game theory. Mathematically, using the property that these centrality formulations are Bayesian,1 we prove an axiomatic characterization theorem: Every influence-based centrality formulation in this family is the unique Bayesian centrality that conforms with its corresponding graph-theoretical centrality. Moreover, the uniqueness is fully determined by the centrality formulation on the class of layered graphs, which is derived from a beautiful algebraic structure of influence instances modeled by cascading sequences. We further provide an algorithmic framework for efficient approximation of these influence-based centrality measures.

Our study provides us with a systematic road map for comparative analyses of different influence-based centrality formulations. The fact that layered graphs form a basis for the space of influence-cascading-sequence proles could also be useful in other studies of network influences.