Database Reference
In-Depth Information
a
b
Alice
Alice
Bob
Carol
Bob
Carol
Fig. 4.1
Some basic networks illustrating the different kind of edges in a network. (
a
) A simple
undirected network. Here, links are symmetric or nondirectional (Alice is joined to Bob and vice
versa). (
b
) A simple directed network. Here, links are asymmetric or directional (Bob is joined to
Alice but Alice is
not
joined to Bob)
represent literally
anything
. Starting with the definition of vertices as “users”, we
will present some basic concepts. In future sections we will show how different
definitions for vertices can lead to different questions from the data.
4.1.1.2
Edges
Simply put, edges join vertices. There are several different types of edges that can
join vertices. Undirected edges join vertices in a symmetric fashion. If two people
engage in a conversation, then this is best represented by an undirected edge because
for User A to converse with User B, User B must also converse with User A.
Contrary to undirected edges are directed edges, which signify a one-way
relationship between two users. A retweet relationship can be thought of as a
directed edge because User A can retweet User B without User B reciprocating.
Another property to consider is “edge weight”. The weight of an edge signifies
its importance when compared to other edges. One natural usage of weighted edges
is in a user mention network, where the weight is the number of times the User A
mentions User B.
4.1.1.3
Paths
A
path
is a sequence of nodes connected by a sequence of edges. A path always
starts at one vertex, and ends at another vertex. We follow a path by starting at
the first node in the sequence and traveling to each subsequent node in order. If no
edge exists between two adjacent nodes in the sequence, then the path is invalid. In
Fig.
4.1
b, a path exists from Bob to Carol, however a path does not exist from Carol
to Bob (directed edges cannot be followed in reverse order).
In addition to paths, we also have
shortest paths
. While there may be many ways
to get from one node to another, the shortest path is the shortest sequence of nodes.
It is important to find the shortest path from one node to another, as information will
most often travel along this path.
