Tempo Centrality


Definition

The functionality of a complex network correlate with the topology and dynamics of a complex network. In many cases of complex networks the topological information is either unavailable or incomplete. The idea of the Tempo Centrality comes from this fact that without the explicit knowledge of network topology it is difficult to quantify the influence of nodes. The tempo centrality utilised the data generated from the network dynamics to infer the influence of nodes. the tempo centrality can be used to construct an accurate estimate of both the propagation rate of influence exerted on consensus networks and the Kirchhoff index of the underlying graph. Moreover, the tempo centrality also encodes the disturbance rejection of nodes in a consensus network.

The tempo centrality quantify the influence of nodes in a consensus network a type of complex network whose components are diffusively coupled, and provide an elegant prototype for collective behaviors

The evolution of the network state is calculate by the network topology and the individual node dynamics. The network snapshots that are generated by the individual dynamics can provide an alternative way for the computation of $TC$ even when the network topology is unknown. This property could be utilize for the design of an algorithm for computing $TC$ from the temporal data of a consensus network.
Consider a consensus network with the set of leader agent $v_l = \{i\}$ and the corresponding perturbed Laplacian matrix $\ell_\beta$. Denote by $h_i$ and $h_j$ as selection matrices for the leader agent $\{i\}$ and a distinct agent $\{j\}$, respectively.The following result establishes linking the network state and the spectra of perturbed Laplacian matrix.

$${\underset{t\to \infty}{lim r_{\{i\},\{j\}}}}(t)\overset{\triangle}{=}{\underset{t\to \infty}{lim}} {||h_i x(t)||_2\over ||h_j x(t)||_2}={||h_i v_1||_2\over ||h_j v_1||_2},$$

where $v_1$ is the normalized eigenvector corresponding to the smallest eigenvalue of $l_\beta$

TC can be computed from the network snapshots.Without loss of generality, designate agent 1 as the leader agent in the network. Discretizing at the sampling points $t_0 ≤ \delta_1 < \delta_2 < … < \delta_m$ yields an m-length snapshots of the consensus network i.e., $\bar x(k) = x (t_0 + \delta_k)$ where $t_0 ≥ 0$ is the initial time step and $k = 0, 1, … , m.$ Denote $\beta(k) = [\beta_1 (k), \beta_2 (k),..., \beta_n(k)]^T \in R^n$ satisfying

$$\beta_1(k+1)=\beta_1(k),$$

$$\beta_j (k+1)={\beta_1(k+1) \over \bar r_{\{1\},\{j\}}(k)},$$

$$\bar r_{\{1\},\{j\}}(k)={||h_1(\bar x(k+1))-\bar x (k)||_2\over ||h_j(\bar x(k+1))-\bar x (k)||_2}, j\in \{2,3,...,n\}$$

Then, it follows that

$$v_1={\underset{k \to \infty}{lim}} {\beta (k)\over ||\beta (k)||_2}$$

According to the definition, the first entry of ${\beta (k)\over ||\beta (k)||_2}$ approaches the TC of agent 1 when $k \to \infty$. A value threshold $\epsilon > 0$ needs to be set such that the computation of $\bar r_{\{1\},\{j\}}(k)$ terminates when reaching its steady state.






References

  • Shao H., Mesbahi M., Li D., Xi Y., 2017. Inferring centrality from network snapshots. Scientific Reports, 7. DOI: 10.1038/srep40642 Publisher web site
The rendering mode: