<p>There are several measures like clustering coefficients that sort of satisfy this, such as <strong>edge embeddedness</strong>. But this looks at the number of neighbours in common to two adjacent nodes. </p>

<p>The property of v being <strong>simplicial</strong> is an important structural property used in algorithmic graph theory, and is fully characterized by only the neighbourhood of v.</p>

<p>Notice that the two examples you gave are: (1) the number of nodes in v's neighbourhood, and (2) the number of edges in v's neighbourhood. Perhaps You might also be interested in the number of triangles in v's neighbourhood (i.e. the number of K4s that v is in) or perhaps the number of $P_3$s in v's neighbourhood, etc.</p>

<p>Perhaps you could loosen your requirement of locality, or else you will only be asking about properties such as "the number of <strong>_</strong> in v's neighbourhood," which might be too limiting. </p>

<p>How about the number of connected components in v's neighbourhood? Something similar to this was used in a recent Kleinberg paper on predicting spouses by looking at Facebook egonets.</p>

CC BY-SA 3.0
2014-03-13T20:57:46.677Z
2014-03-13T20:57:46.677Z
JimN
<p>I'm looking for graph properties which only consider neighbours of a node and do not go beyond that. For example, nodes degree only considers neighbours or clustering coefficient also consider only neighbours, but shortest path considers all nodes in the graph. Are there any other property (except node degree and node coefficient clustering) which only considers neighbours of a node in its calculation?</p>

<graph-theory><graph-algorithms>
What graph properties only consider neighbours of a node in their calculations?
HHH
# What graph properties only consider neighbours of a node in their calculations?

(Asked by: username_0 on 2014-03-13)

I'm looking for graph properties which only consider neighbours of a node and do not go beyond that. For example, nodes degree only considers neighbours or clustering coefficient also consider only neighbours, but shortest path considers all nodes in the graph. Are there any other property (except node degree and node coefficient clustering) which only considers neighbours of a node in its calculation?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2014-03-13. Score: 1

There are several measures like clustering coefficients that sort of satisfy this, such as **edge embeddedness**. But this looks at the number of neighbours in common to two adjacent nodes.

The property of v being **simplicial** is an important structural property used in algorithmic graph theory, and is fully characterized by only the neighbourhood of v.

Notice that the two examples you gave are: (1) the number of nodes in v's neighbourhood, and (2) the number of edges in v's neighbourhood. Perhaps You might also be interested in the number of triangles in v's neighbourhood (i.e. the number of K4s that v is in) or perhaps the number of $P\_3$s in v's neighbourhood, etc.

Perhaps you could loosen your requirement of locality, or else you will only be asking about properties such as "the number of **\_** in v's neighbourhood," which might be too limiting.

How about the number of connected components in v's neighbourhood? Something similar to this was used in a recent Kleinberg paper on predicting spouses by looking at Facebook egonets.


---

