+ Node degree simply measures how many neighbors a node has, but this is not
necessarily sufficient to measure the importance of a node in a graph.
+ We define a node’s eigenvector centrality e(u) via a recurrence relation in which the node’s centrality is proportional to the average centrality of its neighbors.

Saint Olaf College

Includes:
 + Node degree.
 + Node centrality.
 + The clustering coefficient.
 + Closed triangles, ego graphs, and motifs.



Node-level statistics and features


+ The most obvious and straightforward node feature to examine is 'degree', which is usually denoted d(u) for a node u ∈ V and simply counts the number of edges incident to a node. 
+  The degree of a node is an essential statistic to consider, and it is often one of the
most informative features in traditional machine learning models applied to node-level tasks.


Node degree

Node centrality

+ Measures the proportion of closed triangles in a node’s local neighborhood.
+ The popular local variant of the clustering coefficient is computed as follows [Watts and Strogatz, 1998]:

The clustering coefficient

+ An alternative way of viewing the clustering coefficient—rather than as a measure of local clustering—is that it counts the number of closed triangles within each node’s local neighborhood.
+ Rather than just counting triangles, we could consider more complex structures, such as cycles of a particular length. We could also characterize nodes by counts of how often these different motifs occur in their ego graph.

Learn Before

Related