1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.