Node Conductance


Definition

$Node Conductance$ effectively detects spanning structural hole nodes and predict the formation of new edges. $Node Conductance$ is the sum of the probability that node $i$ is revisited at $r$-th step, where $r$ is an integer between $1$ and infinity. Moreover, with the help of node embedding techniques, Node Conductance is able to be approximately calculated on big networks effectively and efficiently.

Conductance measures how hard it is to leave a set of nodes. It named the Node Conductance as it measures how hard it is to leave a certain node. For an undirected graph $G$, and for simplicity, it assumed that $G$ is unweighted, although all of the results apply to weighted graphs equally. A random walk on $G$ defines an associated Markov chain and it defined the $Node Conductance$ of a vertex $i$, $NC_{\infty}$, as the sum of the probability that $i$ is revisited at $s$-th step, where $s$ is the integer between $1$ and $\infty$.

$$NC_{\infty}(i)={\underset{s=1}{\overset{\infty}{\sum}}} P(i|i,s).$$

Node Conductance, measuring the node influence from a global view. The intuition behind Node Conductance is the probability of revisiting the target node in a random walk. Node Conductance also show its effectiveness on mining influential node on both static and dynamic network.


References

  • Lyu, T., Sun, F. and Zhang, Y., 2020, May. Node Conductance: A Scalable Node Centrality Measure on Big Networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 529-541). Springer, Cham. DOI: 10.1007/978-3-030-47436-2_40 Publisher web site


Comments

There are no comment yet.

Add your comment

Name:
Email:
Sum of    and  

The rendering mode: