2
$\begingroup$

I am looking for a formal definition of a network metric I am using in a scientific article. Let $i$ be a vertex in a graph $G$ and $N(i)$ are the first order neighbors of vertex $i$. I am interested in the number of 1st order neighbors of degree 1 (i.e. neighbors only connected to the vertex $i$).

To remain consistent with the rest of the article, I used the vertical bar (i.e. $|$) to identify the cardinality of a set of vertices.

Edition: The graph is undirected meaning that the edges do not have a direction. For two connected vertices $i$ and $j$, $(i,j)$ is equivalent to $(j,i)$. There is also no self-edges $(i,i)$.

$\endgroup$
5
  • $\begingroup$ That sounds like a formal definition to me, assuming you have already defined "degree" and "first order neighbors" somewhere. (What distinction do you make between adjacent vertices and "first order neighbors"?) It's even pretty safe to assume readers understand what "degree" means in this context because it's such a widely known basic concept in graph theory. So, wouldn't "$|N(i)|$" be perfectly fine? If you need anything even more formal, then please tell us whether your graph is directed or not. $\endgroup$
    – whuber
    Oct 11 '19 at 19:32
  • $\begingroup$ Isn't $\vert N(i)\vert$ the total number of neighbors of point $i$ and not just the number of neighbors of $i$ who have no other neighbors? $\endgroup$
    – Dave
    Oct 11 '19 at 20:40
  • $\begingroup$ @Dave In the question, $N(i)$ has been explicitly characterized as the set of "first order neighbors," not all neighbors. Because "first order" and "neighbor" are redundant terms, I took "first order" to mean the neighbors of degree $1,$ but evidently that was wrong: your interpretation looks like the intended one. $\endgroup$
    – whuber
    Oct 12 '19 at 13:16
  • $\begingroup$ @Whuber First order neighbors is similar to adjacent vertices $\endgroup$
    – Proto Man
    Oct 13 '19 at 21:44
  • $\begingroup$ @Dave $|N(i)$ is indeed the number of neighbors of vertex $i$ and not the number of neighbors who have no other neighbors $\endgroup$
    – Proto Man
    Oct 13 '19 at 21:46
1
$\begingroup$

A graph $\Gamma$ is an ordered pair $(V,E)$ where $V$ (the vertices) is any set and $E\subset V\times V$ (the edges) is a collection of ordered pairs of vertices. We usually depict the vertices with point symbols at distinct locations in the plane and the edges $(v,w)$ as arrows running from the location of $v$ (the origin) to the location of $w$ (the destination). Here is an example:

Figure illustrating a graph with various kinds of degree-1 neighbors

All vertices in this plot are distinct and distinguished by color. The edge colors correspond to their origins. Loops are used (without arrowheads) to depict edges connecting a vertex with itself.

To facilitate talking about graphs, let's think of any edge as "pointing" from its origin to its destination.

Generally, there are two kinds of neighbors of any vertex $v\in V$: the "inward pointing" neighbors $w$ for which $(w,v)\in E$ and the "outward pointing" neighbors for which $(v,w)\in E.$ In the figure, $w_1,w_2,w_3,w_8,$ and $w_9$ (roughly to the right of $v$) are inward-pointing neighbors of $v$ while $w_3,w_4,w_5,w_6,$ and $w_7$ (roughly to the left of $v$) are outward-pointing neighbors. Notice that $w_3$ is both kinds of neighbor.

Thus, the inward-pointing neighbors of $v$ are the set

$$N_i(v) = \{w\in V\mid (w,v)\in E\}$$

and, likewise, the outward-pointing neighbors are

$$N_o(v) = \{w\in V\mid (v,w)\in E\}.$$

The union of these sets may be written

$$N(v) = N_i(v)\cup N_o(v),$$

the set of all vertices connected (in either direction or both) to $v.$

From these definitions arise at least nine possible meanings of "first order neighbor of degree 1." Examples are

  • $w_8$ is an inward-pointing neighbor of $v$ and the only neighbor of $w_8$ is $v.$ Thus, $$w_8\in N_i(v) \text{ and }\{v\} = N(w_8).$$

  • $w_9$ is an inward-pointing neighbor of $v$ and $v$ is the only outward-pointing neighbor of $w_9$ distinct from $w_9$ itself. Thus, $$w_9 \in N_i(v) \text{ and }\{v\} = N_o(w_9) \setminus\{w_9\}.$$

  • $w_1$ is an inward-pointing neighbor of $v$ and $w_1$ itself has no inward-pointing neighbors. Thus, $$w_1 \in N_i(v) \text{ and }N_i(w_1) = \emptyset.$$

  • $w_2$ is an inward-pointing neighbor of $v$ and $v$ is the only outward-pointing neighbor of $w_2.$ Thus, $$w_2 \in N_i(v) \text{ and }\{v\} = N_o(w_2).$$

  • $w_3$ is an inward-pointing neighbor of $v$ and $v$ is the only outward-pointing neighbor of $w_3.$ Thus, $$w_3 \in N_i(v) \text{ and }\{v\} = N_i(w_3).$$ Equivalently, $$w_3 \in N_o(v) \text{ and }\{v\} = N_o(w_3).$$

The relationships between $v$ and the other $w_j$ (which are outward-pointing neighbors of $v$) can be similarly expressed. Notice that the concept of degree is not needed to define these relationships.

Thus, for instance, if $w_3$ exemplifies the kind of relationship you mean, then the quantity in the expression can be expressed as

$$|\{w\in N_i(v) \mid \{v\} = N(w)\}|.$$

This involves two (implicit) subscripts: the "i" in the first $N_i(v)$ and the "" (no subscript) in the second $N(w).$ By choosing how to subscript these two expressions, you obtain many of the possible answers to the question. By adding conditions on self-edges, you obtain a few more possible answers.


For undirected graphs (where the edges $(v,w)$ and $(w,v)$ are considered equivalent and therefore may be represented by the set $\{v,w\}$) and for graphs without self-edges $\{v,v\}=\{v\},$ the possibilities are fewer and the definitions simplify. All three concepts of neighborhoods coincide with $$N(v) = \{w\in V\mid \{w,v\}\in E\}$$ and now the numbers of neighbors of degree $1$--including any self-edges--can be characterized as

$$|\{w\in N(v)\mid \{v\}=N(w)\}|.$$

Figure showing possible types of neighbors in an undirected graph

In this figure, that would include neighbors like $w_1$ but not $w_2.$ Where self-edges are not included in the definition of $N(v),$ it would also include $w_2.$

$\endgroup$
3
  • $\begingroup$ Thank you for the detailed answer. I should have specified in my question that I am working with undirected graphs without self edges. I have edited my question to clarify this. $\endgroup$
    – Proto Man
    Oct 13 '19 at 22:02
  • $\begingroup$ Thank you: that was the clarification I requested in the first comment to your question. In the meantime I elected to answer the more difficult interpretation (of directed graphs with self edges), because--as my final remarks indicate--the same considerations apply to undirected graphs but the results are simpler. $\endgroup$
    – whuber
    Oct 14 '19 at 12:14
  • 1
    $\begingroup$ I saw that. Thanks for the detailed answer, it's gonna be useful for future works. I'll be more clear next time I'll post a question. $\endgroup$
    – Proto Man
    Oct 18 '19 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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