TDC - Temporal Dynamic-Sensitive Centrality
Definition
In the susceptible-infected-recovered $(SIR)$ model in discrete time, where the nodes can only be in one of three mutually exclusive states: susceptible $(S)$, infectious $(I)$, recovered $(R)$. At each time step, a node in the state $S$ will get infected with infection probability $\beta$ when contacting one of its infected neighbors. And an infected node can be recovered with a probability $\mu$. When $\mu = 0$, the $SIR$ model reduces to a standard $SI$ model: nodes can only be susceptible or infected. The temporal network forming considered as the substrate of the spreading process to be a sequence of undirected and unweighted temporal networks, which has been described above. Markov chain uses for the epidemic model and derive the analytical result of node influence. Denote $x(t)(t ≥ 0)$ as an $n \times 1$ vector whose components are the probabilities of nodes to be ever infected no later then the time step $t$, then $P(t) = x(t) − x(t−1)(t ≥ 1)$ is the probabilities of nodes to be infected at time step $t$, and subsequently, $P(0) = x(0)$ to represent the initial condition. If $i$ is the only initially infected node, then $x_i(0) = 1$. Notice that, $x(t)$ is the cumulative probability that can be large than 1, and the term probability just used for simplicity. In the first time step, $x(1) = \beta A(1)x(0)$, and in the below Section, it will prove that for $t > 1$ the following equation can be obtained:
$$X(t)-X(t-1)= \beta A (t) {\underset{r=1}{\overset{t-1}{\prod}}} [\beta A(r)+(1-\mu)X(0).$$
So we have
$$P(t) = MP(0),$$
were $M=\beta A(t) \prod_{r=1}^{t-1} [\beta A(r)+(1-\mu)I].$
The probabilities of nodes to be ever infected no later than the time step $t$ in temporal networks can be expressed by
$$X(t)={\underset{r=2}{\overset{t}{\sum}}} [x(r)-x(r-1)]+x(1)={\underset{r=2}{\overset{t}{\sum}}} [x(r)-x(r-1)]+\beta A (1) H^{(0)} x(0)$$
$$= {\underset{r=2}{\overset{t}{\sum}}} \beta A(r) H^{(r-1)} x(0)+\beta A(1) H^{r-1} x(0)= {\underset{r=1}{\overset{t}{\sum}}}\beta A(r) H^{(r-1)} x(0)$$
$$= {\underset{r=0}{\overset{t-1}{\sum}}} \beta A(r+1) H^{(r)} x(0),$$
were $H^{(r)}=\prod_{\alpha=1}^r [\beta A(\alpha)+(1-\mu)I]$ then $H^{(0)}=1$
we can use the sum of infected probabilities of all nodes to express the the spreading influence of nodes. Denote $S_i(t)$ to be the sum of infected probabilities of node $i$ at time step $t$, then
$$S_i(t)=[(\beta A(1)+ \beta A(2)H^{(1)}+...+\beta A(t)H^{(t-1)})^T V]_i$$
were $X^T$ means the transpose of matrix $X$, $V = (1, 1, … . 1)^T$ is $n × 1$ vector whose components are all equal to 1.
$$[H^{(t)}]^T=\{{\underset{\alpha=1}{\overset{t}{\prod}}}[\beta A(\alpha)+(1-\mu)I]\}= {\underset{\alpha=1}{\overset{t}{\prod}}}[\beta A(\alpha)+(1-\mu)I]= H_*^{(t)}$$
then the spreading influence of all nodes can be described by the vector
$$S(t)={\underset{r=0}{\overset{t-1}{\prod}}} \beta H_*^{(r)} A(r+1)V$$
In addition to the topological information,TDC takes the time into consideration and propose temporal centrality metrics based on the time-ordered graph. It established the method to measure the spreading influence of nodes in temporal networks.
$$X(t)-X(t-1)= \beta A (t) {\underset{r=1}{\overset{t-1}{\prod}}} [\beta A(r)+(1-\mu)X(0).$$
So we have
$$P(t) = MP(0),$$
were $M=\beta A(t) \prod_{r=1}^{t-1} [\beta A(r)+(1-\mu)I].$
The probabilities of nodes to be ever infected no later than the time step $t$ in temporal networks can be expressed by
$$X(t)={\underset{r=2}{\overset{t}{\sum}}} [x(r)-x(r-1)]+x(1)={\underset{r=2}{\overset{t}{\sum}}} [x(r)-x(r-1)]+\beta A (1) H^{(0)} x(0)$$
$$= {\underset{r=2}{\overset{t}{\sum}}} \beta A(r) H^{(r-1)} x(0)+\beta A(1) H^{r-1} x(0)= {\underset{r=1}{\overset{t}{\sum}}}\beta A(r) H^{(r-1)} x(0)$$
$$= {\underset{r=0}{\overset{t-1}{\sum}}} \beta A(r+1) H^{(r)} x(0),$$
were $H^{(r)}=\prod_{\alpha=1}^r [\beta A(\alpha)+(1-\mu)I]$ then $H^{(0)}=1$
we can use the sum of infected probabilities of all nodes to express the the spreading influence of nodes. Denote $S_i(t)$ to be the sum of infected probabilities of node $i$ at time step $t$, then
$$S_i(t)=[(\beta A(1)+ \beta A(2)H^{(1)}+...+\beta A(t)H^{(t-1)})^T V]_i$$
were $X^T$ means the transpose of matrix $X$, $V = (1, 1, … . 1)^T$ is $n × 1$ vector whose components are all equal to 1.
$$[H^{(t)}]^T=\{{\underset{\alpha=1}{\overset{t}{\prod}}}[\beta A(\alpha)+(1-\mu)I]\}= {\underset{\alpha=1}{\overset{t}{\prod}}}[\beta A(\alpha)+(1-\mu)I]= H_*^{(t)}$$
then the spreading influence of all nodes can be described by the vector
$$S(t)={\underset{r=0}{\overset{t-1}{\prod}}} \beta H_*^{(r)} A(r+1)V$$
In addition to the topological information,TDC takes the time into consideration and propose temporal centrality metrics based on the time-ordered graph. It established the method to measure the spreading influence of nodes in temporal networks.
References
- Huang D., Yu Z., 2017. Dynamic-Sensitive centrality of nodes in temporal networks. Scientific Reports, 7.
DOI: 10.1038/srep41454
