Information Technology Reference
In-Depth Information
can be displayed as a distribution or a simple average. This measure might be
useful when the empirical evidence being compared against was in the form of
“ego nets” [39].
Geodesic Distance:
The general degree of node separation in a graph is usually
measured through three metrics: average path length, network radius and network
diameter. A geodesic distance is the shortest path between any two nodes (in “hops”).
The average path length is the average of all-geodesic distances on the graph [2]. The
diameter is the largest geodesic distance within the graph. For each node, the eccen-
tricity is the geodesic distance to the node furthest from it; the radius is then the min-
imum eccentricity in the graph. Geodesic distances are important in the presence of
“flood-fill” gossip mechanisms, where messages are passed on to all of a node's
neighbors. The radius of a graph is a lower bound for the “time” (network jumps) for
a message to reach all other nodes, the average path length the average “time” for
nodes to get the message, and the diameter giving an upper bound.
Similarity Measures:
If a set of nodes is the same in two different graphs, we can
calculate the hamming distance between their adjacency matrices to determine as how
many edges are different in each of them [26, 37]. For example, in [1], similarity be-
tween snapshots of the simulated and observed networks was compared in which the
number of agents in the simulated network matched the number of real individuals in
the observed network. This gives a direct count of how many links one may need to
change in order to obtain structurally equivalent graphs. A similar approach is corre-
lating the columns (or rows) in corresponding adjacency matrices (e.g., using the
Pearson Correlation Coefficient) and then using these numbers to measure the differ-
ence. A major drawback of these approaches is that they require corresponding nodes
to exist in both networks.
Eigenvalues and Eigenvector:
The eigenvector [31] approach is an effort to find the
most central actors (i.e., those with the smallest distance from others), in terms of the
“global” or the “overall” structure of the network. The idea is to pay lesser attention
to “local” patterns. A node's importance is determined by the sum of the degree of its
neighboring nodes.
Feature Extraction:
Many network analysis measures require extensive computa-
tional power (e.g., [31]), making their use infeasible for very large graphs. In [9],
Bagrow et al. have introduced a technique to extract a rather small feature representa-
tion matrix from a large graph. For such a graph, a geodesic distance based matrix, B-
Matrix, is calculated where the
n
th
row contains the degree distribution separated by
n
'hops'. For instance, the first row would contain the usual degree distribution of all
nodes; while the last row with the highest
n
, would contain the network diameter. The
distance between the nodes is calculated using the Breadth-First Search (BFS) algo-
rithm. The dimension of this matrix is
the total number of nodes
x
network diameter
.
For structurally equivalent graphs, the calculated B-Matrices would exactly be the
same. This technique can be used to extract featured matrices from large graphs and
then compare them.
