**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**667

# Search results for: Graph similarity

##### 667 Application of a Similarity Measure for Graphs to Web-based Document Structures

**Authors:**
Matthias Dehmer,
Frank Emmert Streib,
Alexander Mehler,
Jürgen Kilian,
Max Mühlhauser

**Abstract:**

**Keywords:**
Graph similarity,
hierarchical and directed graphs,
hypertext,
generalized trees,
web structure mining.

##### 666 New Graph Similarity Measurements based on Isomorphic and Nonisomorphic Data Fusion and their Use in the Prediction of the Pharmacological Behavior of Drugs

**Authors:**
Irene Luque Ruiz,
Manuel Urbano Cuadrado,
Miguel Ángel Gómez-Nieto

**Abstract:**

New graph similarity methods have been proposed in this work with the aim to refining the chemical information extracted from molecules matching. For this purpose, data fusion of the isomorphic and nonisomorphic subgraphs into a new similarity measure, the Approximate Similarity, was carried out by several approaches. The application of the proposed method to the development of quantitative structure-activity relationships (QSAR) has provided reliable tools for predicting several pharmacological parameters: binding of steroids to the globulin-corticosteroid receptor, the activity of benzodiazepine receptor compounds, and the blood brain barrier permeability. Acceptable results were obtained for the models presented here.

**Keywords:**
Graph similarity,
Nonisomorphic dissimilarity,
Approximate similarity,
Drug activity prediction.

##### 665 Measuring the Structural Similarity of Web-based Documents: A Novel Approach

**Authors:**
Matthias Dehmer,
Frank Emmert Streib,
Alexander Mehler,
Jürgen Kilian

**Abstract:**

Most known methods for measuring the structural similarity of document structures are based on, e.g., tag measures, path metrics and tree measures in terms of their DOM-Trees. Other methods measures the similarity in the framework of the well known vector space model. In contrast to these we present a new approach to measuring the structural similarity of web-based documents represented by so called generalized trees which are more general than DOM-Trees which represent only directed rooted trees.We will design a new similarity measure for graphs representing web-based hypertext structures. Our similarity measure is mainly based on a novel representation of a graph as strings of linear integers, whose components represent structural properties of the graph. The similarity of two graphs is then defined as the optimal alignment of the underlying property strings. In this paper we apply the well known technique of sequence alignments to solve a novel and challenging problem: Measuring the structural similarity of generalized trees. More precisely, we first transform our graphs considered as high dimensional objects in linear structures. Then we derive similarity values from the alignments of the property strings in order to measure the structural similarity of generalized trees. Hence, we transform a graph similarity problem to a string similarity problem. We demonstrate that our similarity measure captures important structural information by applying it to two different test sets consisting of graphs representing web-based documents.

**Keywords:**
Graph similarity,
hierarchical and directed graphs,
hypertext,
generalized trees,
web structure mining.

##### 664 Using Spectral Vectors and M-Tree for Graph Clustering and Searching in Graph Databases of Protein Structures

**Authors:**
Do Phuc,
Nguyen Thi Kim Phung

**Abstract:**

**Keywords:**
Eigenvalues,
m-tree,
graph database,
protein
structure,
spectra graph theory.

##### 663 Graph Cuts Segmentation Approach Using a Patch-Based Similarity Measure Applied for Interactive CT Lung Image Segmentation

**Authors:**
Aicha Majda,
Abdelhamid El Hassani

**Abstract:**

**Keywords:**
Graph cuts,
lung CT scan,
lung parenchyma
segmentation,
patch based similarity metric.

##### 662 Graph Codes-2D Projections of Multimedia Feature Graphs for Fast and Effective Retrieval

**Authors:**
Stefan Wagenpfeil,
Felix Engel,
Paul McKevitt,
Matthias Hemmje

**Abstract:**

Multimedia Indexing and Retrieval is generally de-signed and implemented by employing feature graphs. These graphs typically contain a significant number of nodes and edges to reflect the level of detail in feature detection. A higher level of detail increases the effectiveness of the results but also leads to more complex graph structures. However, graph-traversal-based algorithms for similarity are quite inefficient and computation intensive, espe-cially for large data structures. To deliver fast and effective retrieval, an efficient similarity algorithm, particularly for large graphs, is mandatory. Hence, in this paper, we define a graph-projection into a 2D space (Graph Code) as well as the corresponding algorithms for indexing and retrieval. We show that calculations in this space can be performed more efficiently than graph-traversals due to a simpler processing model and a high level of parallelisation. In consequence, we prove that the effectiveness of retrieval also increases substantially, as Graph Codes facilitate more levels of detail in feature fusion. Thus, Graph Codes provide a significant increase in efficiency and effectiveness (especially for Multimedia indexing and retrieval) and can be applied to images, videos, audio, and text information.

**Keywords:**
indexing,
retrieval,
multimedia,
graph code,
graph algorithm

##### 661 Graph-Based Text Similarity Measurement by Exploiting Wikipedia as Background Knowledge

**Authors:**
Lu Zhang,
Chunping Li,
Jun Liu,
Hui Wang

**Abstract:**

**Keywords:**
Text classification,
Text clustering,
Text similarity,
Wikipedia

##### 660 Towards Clustering of Web-based Document Structures

**Authors:**
Matthias Dehmer,
Frank Emmert Streib,
Jürgen Kilian,
Andreas Zulauf

**Abstract:**

**Keywords:**
Clustering methods,
graph-based patterns,
graph similarity,
hypertext structures,
web structure mining

##### 659 Combining Similarity and Dissimilarity Measurements for the Development of QSAR Models Applied to the Prediction of Antiobesity Activity of Drugs

**Authors:**
Irene Luque Ruiz,
Manuel Urbano Cuadrado,
Miguel Ángel Gómez-Nieto

**Abstract:**

**Keywords:**
Graph similarity,
Nonisomorphic dissimilarity,
Approximate similarity,
Drugs activity prediction.

##### 658 Maximum Common Substructure Extraction in RNA Secondary Structures Using Clique Detection Approach

**Authors:**
Shih-Yi Chao

**Abstract:**

**Keywords:**
Clique detection,
labeled vertices,
RNA secondary
structures,
subgraph,
similarity.

##### 657 Efficient Filtering of Graph Based Data Using Graph Partitioning

**Authors:**
Nileshkumar Vaishnav,
Aditya Tatu

**Abstract:**

**Keywords:**
Graph signal processing,
graph partitioning,
inverse
filtering on graphs,
algebraic signal processing.

##### 656 A Neighborhood Condition for Fractional k-deleted Graphs

**Authors:**
Sizhong Zhou,
Hongxia Liu

**Abstract:**

Abstract–Let k ≥ 3 be an integer, and let G be a graph of order n with n ≥ 9k +3- 42(k - 1)2 + 2. Then a spanning subgraph F of G is called a k-factor if dF (x) = k for each x ∈ V (G). A fractional k-factor is a way of assigning weights to the edges of a graph G (with all weights between 0 and 1) such that for each vertex the sum of the weights of the edges incident with that vertex is k. A graph G is a fractional k-deleted graph if there exists a fractional k-factor after deleting any edge of G. In this paper, it is proved that G is a fractional k-deleted graph if G satisfies δ(G) ≥ k + 1 and |NG(x) ∪ NG(y)| ≥ 1 2 (n + k - 2) for each pair of nonadjacent vertices x, y of G.

**Keywords:**
Graph,
minimum degree,
neighborhood union,
fractional k-factor,
fractional k-deleted graph.

##### 655 The Extremal Graph with the Largest Merrifield-Simmons Index of (n, n + 2)-graphs

**Authors:**
M. S. Haghighat,
A. Dolati,
M. Tabari,
E. Mohseni

**Abstract:**

The Merrifield-Simmons index of a graph G is defined as the total number of its independent sets. A (n, n + 2)-graph is a connected simple graph with n vertices and n + 2 edges. In this paper we characterize the (n, n+2)-graph with the largest Merrifield- Simmons index. We show that its Merrifield-Simmons index i.e. the upper bound of the Merrifield-Simmons index of the (n, n+2)-graphs is 9 × 2n-5 +1 for n ≥ 5.

**Keywords:**
Merrifield-Simmons index,
(n,
n+2)-graph.

##### 654 N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs

**Authors:**
R. Anitha,
R. S. Lekshmi

**Abstract:**

**Keywords:**
Decomposition,
Hamilton cycle,
n-sun graph,
perfect matching,
spanning tree.

##### 653 Ranking Genes from DNA Microarray Data of Cervical Cancer by a local Tree Comparison

**Authors:**
Frank Emmert-Streib,
Matthias Dehmer,
Jing Liu,
Max Muhlhauser

**Abstract:**

The major objective of this paper is to introduce a new method to select genes from DNA microarray data. As criterion to select genes we suggest to measure the local changes in the correlation graph of each gene and to select those genes whose local changes are largest. More precisely, we calculate the correlation networks from DNA microarray data of cervical cancer whereas each network represents a tissue of a certain tumor stage and each node in the network represents a gene. From these networks we extract one tree for each gene by a local decomposition of the correlation network. The interpretation of a tree is that it represents the n-nearest neighbor genes on the n-th level of a tree, measured by the Dijkstra distance, and, hence, gives the local embedding of a gene within the correlation network. For the obtained trees we measure the pairwise similarity between trees rooted by the same gene from normal to cancerous tissues. This evaluates the modification of the tree topology due to tumor progression. Finally, we rank the obtained similarity values from all tissue comparisons and select the top ranked genes. For these genes the local neighborhood in the correlation networks changes most between normal and cancerous tissues. As a result we find that the top ranked genes are candidates suspected to be involved in tumor growth. This indicates that our method captures essential information from the underlying DNA microarray data of cervical cancer.

**Keywords:**
Graph similarity,
generalized trees,
graph alignment,
DNA microarray data,
cervical cancer.

##### 652 The Diameter of an Interval Graph is Twice of its Radius

**Authors:**
Tarasankar Pramanik,
Sukumar Mondal,
Madhumangal Pal

**Abstract:**

In an interval graph G = (V,E) the distance between two vertices u, v is de£ned as the smallest number of edges in a path joining u and v. The eccentricity of a vertex v is the maximum among distances from all other vertices of V . The diameter (δ) and radius (ρ) of the graph G is respectively the maximum and minimum among all the eccentricities of G. The center of the graph G is the set C(G) of vertices with eccentricity ρ. In this context our aim is to establish the relation ρ = δ 2 for an interval graph and to determine the center of it.

**Keywords:**
Interval graph,
interval tree,
radius,
center.

##### 651 Completion Number of a Graph

**Authors:**
Sudhakar G

**Abstract:**

In this paper a new concept of partial complement of a graph G is introduced and using the same a new graph parameter, called completion number of a graph G, denoted by c(G) is defined. Some basic properties of graph parameter, completion number, are studied and upperbounds for completion number of classes of graphs are obtained , the paper includes the characterization also.

**Keywords:**
Completion Number,
Maximum Independent subset,
Partial complements,
Partial self complementary

##### 650 On Fractional (k,m)-Deleted Graphs with Constrains Conditions

**Authors:**
Sizhong Zhou,
Hongxia Liu

**Abstract:**

Let G be a graph of order n, and let k 2 and m 0 be two integers. Let h : E(G) [0, 1] be a function. If e∋x h(e) = k holds for each x V (G), then we call G[Fh] a fractional k-factor of G with indicator function h where Fh = {e E(G) : h(e) > 0}. A graph G is called a fractional (k,m)-deleted graph if there exists a fractional k-factor G[Fh] of G with indicator function h such that h(e) = 0 for any e E(H), where H is any subgraph of G with m edges. In this paper, it is proved that G is a fractional (k,m)-deleted graph if (G) k + m + m k+1 , n 4k2 + 2k − 6 + (4k 2 +6k−2)m−2 k−1 and max{dG(x), dG(y)} n 2 for any vertices x and y of G with dG(x, y) = 2. Furthermore, it is shown that the result in this paper is best possible in some sense.

**Keywords:**
Graph,
degree condition,
fractional k-factor,
fractional (k,
m)-deleted graph.

##### 649 Another Approach of Similarity Solution in Reversed Stagnation-point Flow

**Authors:**
Vai Kuong Sin,
Chon Kit Chio

**Abstract:**

**Keywords:**
reversed stagnation-point flow,
similarity solutions,
asymptotic solution

##### 648 Metric Dimension on Line Graph of Honeycomb Networks

**Authors:**
M. Hussain,
Aqsa Farooq

**Abstract:**

**Keywords:**
Resolving set,
metric dimension,
honeycomb network,
line graph.

##### 647 Comparison of Full Graph Methods of Switched Circuits Solution

**Authors:**
Zdeňka Dostálová,
David Matoušek,
Bohumil Brtnik

**Abstract:**

**Keywords:**
Switched capacitors of two phases,
switched
currents of two phases,
transformation graph,
two-graph,
Mason's
formula,
voltage transfer,
summary graph.

##### 646 Speedup Breadth-First Search by Graph Ordering

**Abstract:**

Breadth-First Search (BFS) is a core graph algorithm that is widely used for graph analysis. As it is frequently used in many graph applications, improving the BFS performance is essential. In this paper, we present a graph ordering method that could reorder the graph nodes to achieve better data locality, thus, improving the BFS performance. Our method is based on an observation that the sibling relationships will dominate the cache access pattern during the BFS traversal. Therefore, we propose a frequency-based model to construct the graph order. First, we optimize the graph order according to the nodes’ visit frequency. Nodes with high visit frequency will be processed in priority. Second, we try to maximize the child nodes’ overlap layer by layer. As it is proved to be NP-hard, we propose a heuristic method that could greatly reduce the preprocessing overheads.We conduct extensive experiments on 16 real-world datasets. The result shows that our method could achieve comparable performance with the state-of-the-art methods while the graph ordering overheads are only about 1/15.

**Keywords:**
Breadth-first search,
BFS,
graph ordering,
graph algorithm.

##### 645 On Detour Spectra of Some Graphs

**Authors:**
S.K.Ayyaswamy,
S.Balachandran

**Abstract:**

**Keywords:**
Detour eigenvalue (of a graph),
detour spectrum(of a graph),
detour energy(of a graph),
detour - equienergetic graphs.

##### 644 Analysis of Electrical Networks Using Phasors: A Bond Graph Approach

**Authors:**
Israel Núñez-Hernández,
Peter C. Breedveld,
Paul B. T. Weustink,
Gilberto Gonzalez-A

**Abstract:**

This paper proposes a phasor representation of electrical networks by using bond graph methodology. A so-called phasor bond graph is built up by means of two-dimensional bonds, which represent the complex plane. Impedances or admittances are used instead of the standard bond graph elements. A procedure to obtain the steady-state values from a phasor bond graph model is presented. Besides the presentation of a phasor bond graph library in SIDOPS code, also an application example is discussed.

**Keywords:**
Bond graphs,
phasor theory,
steady-state,
complex
power,
electrical networks.

##### 643 Topological Queries on Graph-structured XML Data: Models and Implementations

**Authors:**
Hongzhi Wang,
Jianzhong Li,
Jizhou Luo

**Abstract:**

**Keywords:**
XML,
Graph Structure,
Topological query.

##### 642 A New Similarity Measure on Intuitionistic Fuzzy Sets

**Authors:**
Binyamin Yusoff,
Imran Taib,
Lazim Abdullah,
Abd Fatah Wahab

**Abstract:**

**Keywords:**
Intuitionistic fuzzy sets,
similarity measures,
multicriteriadecision making.

##### 641 An Efficient Graph Query Algorithm Based on Important Vertices and Decision Features

**Authors:**
Xiantong Li,
Jianzhong Li

**Abstract:**

**Keywords:**
Decision Feature,
Frequent Feature,
Graph Dataset,
Graph Query

##### 640 Notes on Fractional k-Covered Graphs

**Authors:**
Sizhong Zhou,
Yang Xu

**Abstract:**

**Keywords:**
graph,
binding number,
fractional k-factor,
fractional k-covered graph.

##### 639 A New Similarity Measure Based On Edge Counting

**Authors:**
T. Slimani,
B. Ben Yaghlane,
K. Mellouli

**Abstract:**

In the field of concepts, the measure of Wu and Palmer [1] has the advantage of being simple to implement and have good performances compared to the other similarity measures [2]. Nevertheless, the Wu and Palmer measure present the following disadvantage: in some situations, the similarity of two elements of an IS-A ontology contained in the neighborhood exceeds the similarity value of two elements contained in the same hierarchy. This situation is inadequate within the information retrieval framework. To overcome this problem, we propose a new similarity measure based on the Wu and Palmer measure. Our objective is to obtain realistic results for concepts not located in the same way. The obtained results show that compared to the Wu and Palmer approach, our measure presents a profit in terms of relevance and execution time.

**Keywords:**
Hierarchy,
IS-A ontology,
Semantic Web,
Similarity
Measure.

##### 638 Syntactic Recognition of Distorted Patterns

**Authors:**
Marek Skomorowski

**Abstract:**

**Keywords:**
Syntactic pattern recognition,
Distorted patterns,
Random graphs,
Graph grammars.