![](https://csdnimg.cn/release/download_crawler_static/18632780/bg2.jpg)
714 J. Tang et al. / Digital Signal Processing 22 (2012) 713–725
similarity of two graphs is quantified by comparing all pairs of
shortest path lengths [16]. This kind of kernel can prevent totter-
ing and be usually faster than random walk kernels. Ramon and
Gartner proposed subtree kernel on graphs by comparing subtree-
like patterns in two graphs [17]. Comparing to walk based kernel,
it can give richer representation of graph structure. Moreover, a
statistical method can be used to compute the similarity of graphs.
For example, Christmas et al. used probability distribution func-
tions to model the pairwise attribute relationships on graph edges
and developed an evidence combining framework for graph match-
ing [19]. Wilson and Hancock proposed an approach to measure
the similarity of graphs by using a probability distribution that
models the numbers of relabeling nodes and graph edit opera-
tions when structure errors exist [20]. Additionally, graph match-
ing provides a measure of the distance between structures [21,
22].
The aforementioned methods provided excellent measurements
of the distance between graph structures. However, they did not
result in an ordering of the graphs that had metric significance
under structural variations due to graded shape changes. Hence,
we want to address the problem of organizing graphs into a pat-
tern space in which similar structures are close to one another,
and dissimilar structures are separated far away from each other.
In particular, we aim to embed graphs in a vector-space where
the dimensions correspond to principal modes in structural vari-
ation. Moreover, if the graph can be embedded on a manifold in
a pattern space, then the modes of shape variation can be ex-
plored by traversing the manifold in a systematic way. The pro-
cess of constructing low-dimensional space or manifolds is a rou-
tine procedure with pattern vectors. Various techniques, such as
multi-dimensional scaling (MDS), principal components analysis
(PCA), independent components analysis and Laplacian eigenmap,
exist for achieving this purpose. However, there are few analogous
methods which can be used to construct low-dimensional pattern
spaces for sets of graphs. One way to achieve this purpose is to
represent the graphs by pattern vectors. Topological descriptors
methods can be achieved to address this problem [23–25]. These
methods can be done by first mapping each graph to a feature
vector, then using distances and metrics on vectors for learning on
graphs. Different from edit distance and graph kernel, topological
descriptors based methods can not only propose a way to measure
the similarity of graphs, but also embed the graphs in a pattern
space in which graph structure variation can be analyzed by using
manifold learning theory. For instance, Luo, Wilson and Hancock
mapped the structure of a graph into a feature vector of fixed
length by using spectral graph theory [23]. Based on the spectral
feature vectors extracted from the graph, they provided a way to
measure the distance of graphs and analyze graph structures based
on MDS and PCA methods. Recently, Gao et al. represented the
graph by histogram feature vectors [24]. Similar to Luo et al. [23],
this method avoided formulating the cost function or the similarity
criterion of corresponding nodes and edges in two graphs, both of
which are difficult to define. The main drawback of their method
is that they did not explore the graph structures based on his-
togram feature vectors. In order to further study the problems of
graph structure mapping into a vector of fixed length and the mea-
surement of the similarity of graphs, we chose to use the complex
network representation method.
Complex networks can be described as a marriage of graph
theory and probability theory, which has been used extensively
in computer science, mathematics, and physics [26–30] and at-
tracted great interest in many fields of science. The popularity of
complex networks results from their flexibility and generality in
representing any given data structure, either natural or discrete,
including those that are undergoing dynamic changes of topology.
Other interesting problems associated with complex networks are
characterizing the topology changes and the connectivity of the in-
vestigated structures during the evolution process and measuring
the structural properties of the evolving network.
State-of-the-art efforts have been conducted in attempts to ap-
ply complex networks to real-world data, including the represen-
tation of real problems as complex networks and analysis of the
growth of network dynamics and identification of their topolog-
ical characteristics. Complex networks have been used to model
texts, image textures, and face images [31–33] in which feature
vectors were extracted for classification and recognition by analyz-
ing the topological measurements of the network. Moreover, shape
descriptors based on a small-world network model were proposed
in [34,35] in which the shape format was shown to be correlated
with the structure of a small-world network during many of the
networks evolutionary stages. The topological and dynamic char-
acteristics of the network were used to describe the shape of the
boundaries.
In this paper, a novel graph structure representation method
based on a complex network is presented. First, we modeled the
graph structure as a complex network, and, then, we extracted
the topological and dynamic characteristics of the complex net-
work to characterize the structure of the graph. By considering
the spatial relationships among edges that are basic elements of
the graph structure, our complex network representation of graphs
was adept at characterizing the connectivity differences of graphs,
i.e., directions and lengths of the edges. This is related to GED,
which considers the connectivity differences of graphs by editing
the sequence of the operations, consisting of edge/node insertion,
deletion, and substitution. Moreover, based on these complex net-
work characteristics, we were able to map the graph structures
into vectors and then investigate two alternative routes to embed
them into a pattern space. The first route is based on MDS, and
the second route is using PCA, which projects the feature vectors
onto the leading eigenvectors of the co-variance matrix to give a
graph pattern space.
2. Related work on complex networks
In this section, we briefly recall the basic concepts of complex
networks that are related to our work. We start by giving an in-
troduction to complex networks and present several topological
measurements used in the paper; then, we introduce the dynamic
evolution of a network.
2.1. Complex network
Complex networks are represented by graphs consisting of a
set of vertices connected by edges. According to their properties,
complex networks can be classified into three main models, i.e.,
random networks, small-world networks, and scale-free networks.
In the random network model, which is considered to be the sim-
plest model [28], the edges are added randomly. The small-world
network model proposed by Watts and Strogatz [29] presents the
small-world properties, i.e., all vertices can be reached from any of
the other vertices through a small number of edges, and there are
many order three loops (high clustering coefficients exist). Barabási
and Albert proposed a scale invariant network, which they called
thescale-freenetwork[30],inwhichthedistributionofconnected
vertices follows a scale-free distribution given by p
(k) = k
−γ
.
As a graph, the edges of a complex network can be binary,
weighted, and directed. Our paper is limited to the non-directed
case. The undirected complex network model is typically repre-
sented by a matrix W , where W
(i, j) is the weight of the edge
connecting node i and node j. The characterization of the topo-
logical and connectivity properties of a complex network can be