Search results for: directed graph

Authors: Arun Prabhakar

Abstract:

Threat modeling is an important activity carried out in the initial stages of the development lifecycle that helps in building proactive security measures in the product. Though there are many techniques and tools available today, one of the common challenges with the traditional methods is the lack of a systematic approach in identifying security threats. The proposed solution describes an organized model by defining ontologies that help in building patterns to enumerate threats. The concepts of graph theory are applied to build the pattern for discovering threats for any given scenario. This graph-based solution also brings in other benefits, making it a customizable and scalable model.

Keywords: directed acyclic graph, ontology, patterns, threat identification, threat modeling

Procedia PDF Downloads 108

Authors: U. Mary

Abstract:

Let be a graph with a finite, nonempty set of objects called vertices together with a set of unordered pairs of distinct vertices of called edges. The vertex set is denoted by and the edge set by. Given two graphs and the wiener index of, wiener index for the splitting graph of a graph, the first Zagreb index of and its splitting graph, the 3-steiner wiener index of, the 3-steiner wiener index of a special graph are explored in this paper.

Keywords: complementary prism graph, first Zagreb index, neighborhood corona graph, steiner distance, splitting graph, steiner wiener index, wiener index

Procedia PDF Downloads 533

Authors: Sofia Ait Bouazza

Abstract:

We consider the problem of finding a minimum identifying code in a graph. This problem was initially introduced in 1998 and has been since fundamentally connected to a wide range of applications (fault diagnosis, location detection …). Suppose we have a building into which we need to place fire alarms. Suppose each alarm is designed so that it can detect any fire that starts either in the room in which it is located or in any room that shares a doorway with the room. We want to detect any fire that may occur or use the alarms which are sounding to not only to not only detect any fire but be able to tell exactly where the fire is located in the building. For reasons of cost, we want to use as few alarms as necessary. The first problem involves finding a minimum domination set of a graph. If the alarms are three state alarms capable of distinguishing between a fire in the same room as the alarm and a fire in an adjacent room, we are trying to find a minimum locating domination set. If the alarms are two state alarms that can only sound if there is a fire somewhere nearby, we are looking for a differentiating domination set of a graph. These three areas are the subject of much active research; we primarily focus on the third problem. An identifying code of a graph G is a dominating set C such that every vertex x of G is distinguished from other vertices by the set of vertices in C that are at distance at most r≥1 from x. When only vertices out of the code are asked to be identified, we get the related concept of a locating dominating set. The problem of finding an identifying code (resp a locating dominating code) of minimum size is a NP-hard problem, even when the input graph belongs to a number of specific graph classes. Therefore, we study this problem in some restricted classes of undirected graphs like split graph, line graph and path in a directed graph. Then we present some results on the identifying code by giving an exact value of upper total locating domination and a total 2-identifying code in directed and undirected graph. Moreover we determine exact values of locating dominating code and edge identifying code of thin headless spider and locating dominating code of complete suns.

Keywords: identiying codes, locating dominating set, split graphs, thin headless spider

Procedia PDF Downloads 428

Authors: Prateek Chharia, Biswa Bhusan Ghosh

Abstract:

Graph coloring is one of the prominent concepts in graph coloring. It can be defined as a coloring of the various regions of the graph such that all the constraints are fulfilled. In this paper various graphs coloring approaches like greedy coloring, Heuristic search for maximum independent set and graph coloring using edge table is described. Graph coloring can be used in various real time applications like student time tabling generation, Sudoku as a graph coloring problem, GSM phone network.

Keywords: graph coloring, greedy coloring, heuristic search, edge table, sudoku as a graph coloring problem

Procedia PDF Downloads 508

Authors: Mehmet Hakan Karaata

Abstract:

In this paper, we first coin a new graph theocratic problem with numerous applications. Second, we provide two algorithms for the problem. The first solution is using a brute-force techniques, whereas the second solution is based on an initial identification of the cycles in the given graph. We then provide a correctness proof of the algorithm. The applications of the problem include graph analysis, graph drawing and network structuring.

Keywords: algorithm, cycle, graph algorithm, graph theory, network structuring

Procedia PDF Downloads 355

Authors: Severino Gervacio, Velimor Almonte, Emmanuel Natalio

Abstract:

A simple graph is planar if it there is a way of drawing it in the plane without edge crossings. A planar graph which is not a proper spanning subgraph of another planar graph is a maximal planar graph. We prove that for complete tripartite graphs of order at most 9, the only ones that contain a spanning maximal planar subgraph are K1,1,1, K2,2,2, K2,3,3, and K3,3,3. The main result gives a necessary and sufficient condition for the complete tripartite graph Kx,y,z to contain a spanning maximal planar subgraph.

Keywords: complete tripartite graph, graph, maximal planar graph, planar graph, subgraph

Procedia PDF Downloads 342

Authors: Nileshkumar Vaishnav, Aditya Tatu

Abstract:

An algebraic framework for processing graph signals axiomatically designates the graph adjacency matrix as the shift operator. In this setup, we often encounter a problem wherein we know the filtered output and the filter coefficients, and need to find out the input graph signal. Solution to this problem using direct approach requires O(N3) operations, where N is the number of vertices in graph. In this paper, we adapt the spectral graph partitioning method for partitioning of graphs and use it to reduce the computational cost of the filtering problem. We use the example of denoising of the temperature data to illustrate the efficacy of the approach.

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

Procedia PDF Downloads 276

Authors: E. R. Swart, S. J. Gismondi, N. R. Swart, C. E. Bell

Abstract:

We present an heuristic algorithm that decides graph non-Hamiltonicity. All graphs are directed, each undirected edge regarded as a pair of counter directed arcs. Each of the n! Hamilton cycles in a complete graph on n+1 vertices is mapped to an n-permutation matrix P where p(u,i)=1 if and only if the ith arc in a cycle enters vertex u, starting and ending at vertex n+1. We first create exclusion set E by noting all arcs (u, v) not in G, sufficient to code precisely all cycles excluded from G i.e. cycles not in G use at least one arc not in G. Members are pairs of components of P, {p(u,i),p(v,i+1)}, i=1, n-1. A doubly stochastic-like relaxed LP formulation of the Hamilton cycle decision problem is constructed. Each {p(u,i),p(v,i+1)} in E is coded as variable q(u,i,v,i+1)=0 i.e. shrinks the feasible region. We then implement the Weak Closure Algorithm (WCA) that tests necessary conditions of a matching, together with Boolean closure to decide 0/1 variable assignments. Each {p(u,i),p(v,j)} not in E is tested for membership in E, and if possible, added to E (q(u,i,v,j)=0) to iteratively maximize |E|. If the WCA constructs E to be maximal, the set of all {p(u,i),p(v,j)}, then G is decided non-Hamiltonian. Only non-Hamiltonian G share this maximal property. Ten non-Hamiltonian graphs (10 through 104 vertices) and 2000 randomized 31 vertex non-Hamiltonian graphs are tested and correctly decided non-Hamiltonian. For Hamiltonian G, the complement of E covers a matching, perhaps useful in searching for cycles. We also present an example where the WCA fails.

Keywords: Hamilton cycle decision problem, computational complexity theory, graph theory, theoretical computer science

Procedia PDF Downloads 337

Authors: Saieed Akbari, Yousef Bagheri, Amir Hossein Ghodrati, Sima Saadat Akhtar

Abstract:

Let G be a simple graph with the vertex set V (G) and with the adjacency matrix A (G). The energy E (G) of G is defined to be the sum of the absolute values of all eigenvalues of A (G). Also let n and m be number of edges and vertices of the graph respectively. A regular graph is a graph where each vertex has the same number of neighbours. Given a graph G, its line graph L(G) is a graph such that each vertex of L(G) represents an edge of G; and two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint in G. In this paper we show that for every regular graphs and also for every line graphs such that (G) 3 we have, E(G) 2nm + n 1. Also at the other part of the paper we prove that 2 (G) E(G) for an arbitrary graph G.

Keywords: eigenvalues, energy, line graphs, matching number

Procedia PDF Downloads 197

Authors: Nileshkumar Vishnav, Aditya Tatu

Abstract:

A recent approach of representing graph signals and graph filters as polynomials is useful for graph signal processing. In this approach, the adjacency matrix plays pivotal role; instead of the more common approach involving graph-Laplacian. In this work, we follow the adjacency matrix based approach and corresponding algebraic signal model. We further expand the theory and introduce the concept of similarity of two graphs. The similarity of graphs is useful in that key properties (such as filter-response, algebra related to graph) get transferred from one graph to another. We demonstrate potential applications of the relation between two similar graphs, such as nonuniform filter design, DTMF detection and signal reconstruction.

Keywords: graph signal processing, algebraic signal processing, graph similarity, isospectral graphs, nonuniform signal processing

Procedia PDF Downloads 316

Authors: M. Hussain, Aqsa Farooq

Abstract:

Let G = (V,E) be a connected graph and distance between any two vertices a and b in G is a−b geodesic and is denoted by d(a, b). A set of vertices W resolves a graph G if each vertex is uniquely determined by its vector of distances to the vertices in W. A metric dimension of G is the minimum cardinality of a resolving set of G. In this paper line graph of honeycomb network has been derived and then we calculated the metric dimension on line graph of honeycomb network.

Keywords: Resolving set, Metric dimension, Honeycomb network, Line graph

Procedia PDF Downloads 151

Authors: Qiuyi Lyu, Bin Gong

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, improve 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

Procedia PDF Downloads 101

Authors: Elias Ogutu Azariah Tembe, Hussain Abdullah Habib Al-Salamin

Abstract:

There is decagram of strategic decisions of operations and production/service management (POSM) within operational research (OR) which must collate, namely: design, inventory, quality, location, process and capacity, layout, scheduling, maintain ace, and supply chain. This paper presents an architectural configuration conceptual framework of a decagram of sets decisions in a form of mathematical complete graph and abelian graph. Mathematically, a complete graph is undirected (UDG), and directed (DG) a relationship where every pair of vertices are connected, collated, confluent, and holomorphic. There has not been any study conducted which, however, prioritizes the holomorphic sets which of POMS within OR field of study. The study utilizes OR structured technique known as The Analytic Hierarchy Process (AHP) analysis for organizing, sorting and prioritizing (ranking) the sets within the decagram of POMS according to their attribution (propensity), and provides an analysis how the prioritization has real-world application within the 21st century.

Keywords: holomorphic, decagram, decagon, confluent, complete graph, AHP analysis, SCM, HRM, OR, OM, abelian graph

Procedia PDF Downloads 376

Authors: Gowtham Kalkere Jayanna, Mohamad Nazri Husin

Abstract:

Graph theory, chemistry, and technology are all combined in cheminformatics. The structure and physiochemical properties of organic substances are linked using some useful graph invariants and the corresponding molecular graph. In this paper, we study specific reverse topological indices such as the reverse sum-connectivity index, the reverse Zagreb index, the reverse arithmetic-geometric, and the geometric-arithmetic, the reverse Sombor, the reverse Nirmala indices for the bistar graphs B (n: m) and the corona product Kₘ∘Kₙ', where Kₙ' Represent the complement of a complete graph Kₙ.

Keywords: reverse topological indices, bistar graph, the corona product, graph

Procedia PDF Downloads 55

Authors: Yasmeen A. S. Essawy, Khaled Nassar

Abstract:

With the rapid increase of complexity in the building industry, professionals in the A/E/C industry were forced to adopt Building Information Modeling (BIM) in order to enhance the communication between the different project stakeholders throughout the project life cycle and create a semantic object-oriented building model that can support geometric-topological analysis of building elements during design and construction. This paper presents a model that extracts topological relationships and geometrical properties of building elements from an existing fully designed BIM, and maps this information into a directed acyclic Elemental Graph Data Model (EGDM). The model incorporates BIM-based search algorithms for automatic deduction of geometrical data and topological relationships for each building element type. Using graph search algorithms, such as Depth First Search (DFS) and topological sortings, all possible construction sequences can be generated and compared against production and construction rules to generate an optimized construction sequence and its associated schedule. The model is implemented in a C# platform.

Keywords: building information modeling (BIM), elemental graph data model (EGDM), geometric and topological data models, graph theory

Procedia PDF Downloads 343

Authors: S. R. Nayaka, Putta Swamy

Abstract:

Graph polynomial is one of the algebraic representations of the Graph. The degree polynomial is one of the simple algebraic representations of graphs. The degree polynomial of a graph G of order n is the polynomial Deg(G, x) with the coefficients deg(G,i) where deg(G,i) denotes the number of vertices of degree i in G. In this article, we investigate the behavior of the roots of some families of Graphs in the complex field. We investigate for the graphs having only integral roots. Further, we characterize the graphs having single roots or having real roots and behavior of the polynomial at the particular value is also obtained.

Keywords: degree polynomial, regular graph, minimum and maximum degree, graph operations

Procedia PDF Downloads 212

Authors: Mouataz Zreika, Maria Estela Varua

Abstract:

Stock investment decisions are often made based on current events of the global economy and the analysis of historical data. Conversely, visual representation could assist investors’ gain deeper understanding and better insight on stock market trends more efficiently. The trend analysis is based on long-term data collection. The study adopts a hybrid method that combines the Clustering algorithm and Force-directed algorithm to overcome the scalability problem when visualizing large data. This method exemplifies the potential relationships between each stock, as well as determining the degree of strength and connectivity, which will provide investors another understanding of the stock relationship for reference. Information derived from visualization will also help them make an informed decision. The results of the experiments show that the proposed method is able to produced visualized data aesthetically by providing clearer views for connectivity and edge weights.

Keywords: clustering, force-directed, graph drawing, stock investment analysis

Procedia PDF Downloads 276

Authors: Ladznar S. Laja, Rosalio G. Artes, Jr.

Abstract:

This paper introduced a graph polynomial relating convexity concepts. A graph polynomial is a polynomial representing a graph given some parameters. On the other hand, a subgraph H of a graph G is said to be convex in G if for every pair of vertices in H, every shortest path with these end-vertices lies entirely in H. We define the convex subgraph polynomial of a graph G to be the generating function of the sequence of the numbers of convex subgraphs of G of cardinalities ranging from zero to the order of G. This graph polynomial is monic since G itself is convex. The convex index which counts the number of convex subgraphs of G of all orders is just the evaluation of this polynomial at 1. Relationships relating algebraic properties of convex subgraphs polynomial with graph theoretic concepts are established.

Keywords: convex subgraph, convex index, generating function, polynomial ring

Procedia PDF Downloads 181

Authors: Samai'la Abdullahi

Abstract:

A graph is a pair of two set and so that a graph is a pictorial representation of a system using two basic element nodes and edges. A node is represented by a circle (either hallo shade) and edge is represented by a line segment connecting two nodes together. In this paper, we present a circuit network in the concept of graph theory application and also circuit models of graph are represented in logical connection method were we formulate matrix method of adjacency and incidence of matrix and application of truth table.

Keywords: euler circuit and path, graph representation of circuit networks, representation of graph models, representation of circuit network using logical truth table

Procedia PDF Downloads 521

Authors: Vadim E. Levit, Eugen Mandrescu

Abstract:

A graph is well-covered if all its maximal independent sets are of the same size. A well-covered graph is 1-well-covered if deletion of every vertex of the graph leaves it well-covered. It is known that a graph without isolated vertices is 1-well-covered if and only if every two disjoint independent sets are included in two disjoint maximum independent sets. Well-covered graphs are related to combinatorial commutative algebra (e.g., every Cohen-Macaulay graph is well-covered, while each Gorenstein graph without isolated vertices is 1-well-covered). Our intent is to construct several infinite families of 1-well-covered graphs using the following known graph operations: corona, join, and rooted product of graphs. Adopting some known techniques used to advantage for well-covered graphs, one can prove that: if the graph G has no isolated vertices, then the corona of G and H is 1-well-covered if and only if H is a complete graph of order two at least; the join of the graphs G and H is 1-well-covered if and only if G and H have the same independence number and both are 1-well-covered; if H satisfies the property that every three pairwise disjoint independent sets are included in three pairwise disjoint maximum independent sets, then the rooted product of G and H is 1-well-covered, for every graph G. These findings show not only how to generate some more families of 1-well-covered graphs, but also that, to this aim, sometimes, one may use graphs that are not necessarily 1-well-covered.

Keywords: maximum independent set, corona, concatenation, join, well-covered graph

Procedia PDF Downloads 171

Authors: Po-Jen Chen, Jian-Jiun Ding, Hung-Wei Hsu, Chien-Yao Wang, Jia-Ching Wang

Abstract:

A more accurate scene classification algorithm using label relations and the hierarchy neural network was developed in this work. In many classification algorithms, it is assumed that the labels are mutually exclusive. This assumption is true in some specific problems, however, for scene classification, the assumption is not reasonable. Because there are a variety of objects with a photo image, it is more practical to assign multiple labels for an image. In this paper, two label relations, which are exclusive relation and hierarchical relation, were adopted in the classification process to achieve more accurate multiple label classification results. Moreover, the hierarchy neural network (hierarchy NN) is applied to classify the image and the directed acyclic graph structure is used for predicting a more reasonable result which obey exclusive and hierarchical relations. Simulations show that, with these techniques, a much more accurate scene classification result can be achieved.

Keywords: convolutional neural network, label relation, hierarchy neural network, scene classification

Procedia PDF Downloads 422

Authors: Khidir R. Sharaf, Didar A. Ali

Abstract:

The nullity η (G) of a graph is the occurrence of zero as an eigenvalue in its spectra. A zero-sum weighting of a graph G is real valued function, say f from vertices of G to the set of real numbers, provided that for each vertex of G the summation of the weights f (w) over all neighborhood w of v is zero for each v in G.A high zero-sum weighting of G is one that uses maximum number of non-zero independent variables. If G is graph with an end vertex, and if H is an induced sub-graph of G obtained by deleting this vertex together with the vertex adjacent to it, then, η(G)= η(H). In this paper, a high zero-sum weighting technique and the end vertex procedure are applied to evaluate the nullity of t-tupple and generalized t-tupple graphs are derived and determined for some special types of graphs. Also, we introduce and prove some important results about the t-tupple coalescence, Cartesian and Kronecker products of nut graphs.

Keywords: graph theory, graph spectra, nullity of graphs, statistic

Procedia PDF Downloads 202

Authors: Krishnendra Shekhawat

Abstract:

Given a graph G = (V, E), a rectangular dual of G represents the vertices of G by a set of interior-disjoint rectangles such that two rectangles touch if and only if there is an edge between the two corresponding vertices in G. Rectangular duals do not exist for every graph, so we can define maximal rectangular duals. A maximal rectangular dual is a rectangular dual of a graph G such that there exists no graph G ′ with a rectangular dual where G is a subgraph of G ′. In this paper, we enumerate all maximal rectangular duals (or, to be precise, the corresponding planar graphs) up to six nodes and presents a necessary condition for the existence of a rectangular dual. This work allegedly has applications in integrated circuit design and architectural floor plans.

Keywords: adjacency, degree sequence, dual graph, rectangular dual

Procedia PDF Downloads 226

Authors: Asraful Islam

Abstract:

Extended dependency graph (EDG) is a state-of-the-art isomorphic graph to represent normal logic programs (NLPs) that can characterize the consistency of NLPs by graph analysis. To construct the vertices and arcs of an EDG, additional renaming atoms and rules besides those the given program provides are used, resulting in higher space complexity compared to the corresponding traditional dependency graph (TDG). In this article, we propose an extended labeled dependency graph (ELDG) to represent an NLP that shares an equal number of nodes and arcs with TDG and prove that it is isomorphic to the domain program. The number of nodes and arcs used in the underlying dependency graphs are formulated to compare the space complexity. Results show that ELDG uses less memory to store nodes, arcs, and cycles compared to EDG. To exhibit the desirability of ELDG, firstly, the stable models of the kernel form of NLP are characterized by the admissible coloring of ELDG; secondly, a relation of the stable models of a kernel program with the handles of the minimal, odd cycles appearing in the corresponding ELDG has been established; thirdly, to our best knowledge, for the first time an inverse transformation from a dependency graph to the representing NLP w.r.t. ELDG has been defined that enables transferring analytical results from the graph to the program straightforwardly.

Keywords: normal logic program, isomorphism of graph, extended labelled dependency graph, inverse graph transforma-tion, graph colouring

Procedia PDF Downloads 179

Authors: Silmy A. Humaira'

Abstract:

There is an issue about Asian students including Indonesian students that tend to behave passively in the classroom and depend on the teachers’ instruction. Regarding this statement, this study attempts to address the Indonesian high school students’ attitudes on whether they have initiative and be responsible for their learning out of the classroom and if so, why. Therefore, 30 high school students were asked to fill out the questionnaires and interviewed in order to figure out their attitudes towards self-directed learning. The descriptive qualitative research analysis adapted Knowles’s theory (1975) about Self-directed learning (SDL) to analyze the data. The findings show that the students have a potential to possess self-directed learning through ICT, but they have difficulties in choosing appropriate learning strategy, doing self-assessment and conducting self-reflection. Therefore, this study supports the teacher to promote self-directed learning instruction for successful learning by assisting students in dealing with those aforementioned problems. Furthermore, it is expected to be a beneficial reference which gives new insights on the self-directed learning practice in specific context.

Keywords: ICT, learning autonomy, students’ attitudes, self-directed learning

Procedia PDF Downloads 198

Authors: Puttaswamy, Anwar Alwardi, Nayaka S. R.

Abstract:

One of the algebraic representation of a graph is the graph polynomial. In this article, we introduce the paired-domination polynomial of a graph G. The paired-domination polynomial of a graph G of order n is the polynomial Dp(G, x) with the coefficients dp(G, i) where dp(G, i) denotes the number of paired dominating sets of G of cardinality i and γpd(G) denotes the paired-domination number of G. We obtain some properties of Dp(G, x) and its coefficients. Further, we compute this polynomial for some families of standard graphs. Further, we obtain some characterization for some specific graphs.

Keywords: domination polynomial, paired dominating set, paired domination number, paired domination polynomial

Procedia PDF Downloads 193

Authors: A. Kulandai Therese

Abstract:

The eccentric connectivity index based on degree and eccentricity of the vertices of a graph is a widely used graph invariant in mathematics.In this paper, we present the explicit eccentric connectivity index, first and second Zagreb indices for a Corona graph and sub division-related corona graphs.

Keywords: corona graph, degree, eccentricity, eccentric connectivity index, first zagreb index, second zagreb index, subdivision graphs

Procedia PDF Downloads 304

Authors: T. Pathinathan, M. Peter

Abstract:

Fuzzy graphs incorporate concepts from graph theory with fuzzy principles. In this paper, we make a study on the properties of fuzzy graphs which are non-cyclic and are of two-dimensional in structure. In particular, this paper presents 2D structure or the structure of double layer for a non-cyclic fuzzy graph whose underlying crisp graph is non-cyclic. In any graph structure, introducing 2D structure may lead to an inherent cycle. We propose relevant conditions for 2D structured non-cyclic fuzzy graphs. These conditions are extended even to fuzzy graphs of the 3D structure. General theoretical properties that are studied for any fuzzy graph are verified to 2D structured or double layered fuzzy graphs. Concepts like Order, Degree, Strong and Size for a fuzzy graph are studied for 2D structured or double layered non-cyclic fuzzy graphs. Using different types of fuzzy graphs, the proposed concepts relating to 2D structured fuzzy graphs are verified.

Keywords: double layered fuzzy graph, double layered non–cyclic fuzzy graph, order, degree and size

Procedia PDF Downloads 363

Authors: Zhifei Hu, Feng Xia

Abstract:

In recent years, Graph neural network has been widely used in knowledge graph recommendation. The existing recommendation methods based on graph neural network extract information from knowledge graph through entity and relation, which may not be efficient in the way of information extraction. In order to better propose useful entity information for the current recommendation task in the knowledge graph, we propose an end-to-end Neural network Model based on multi-stream graph attentional Mechanism (MSGAT), which can effectively integrate the knowledge graph into the recommendation system by evaluating the importance of entities from both users and items. Specifically, we use the attention mechanism from the user's perspective to distil the domain nodes information of the predicted item in the knowledge graph, to enhance the user's information on items, and generate the feature representation of the predicted item. Due to user history, click items can reflect the user's interest distribution, we propose a multi-stream attention mechanism, based on the user's preference for entities and relationships, and the similarity between items to be predicted and entities, aggregate user history click item's neighborhood entity information in the knowledge graph and generate the user's feature representation. We evaluate our model on three real recommendation datasets: Movielens-1M (ML-1M), LFM-1B 2015 (LFM-1B), and Amazon-Book (AZ-book). Experimental results show that compared with the most advanced models, our proposed model can better capture the entity information in the knowledge graph, which proves the validity and accuracy of the model.

Keywords: graph attention network, knowledge graph, recommendation, information propagation

Procedia PDF Downloads 85

Authors: Ezgi Kaya, A. Dilek Maden

Abstract:

A topological index is a number related to graph which is invariant under graph isomorphism. In theoretical chemistry, molecular structure descriptors (also called topological indices) are used for modeling physicochemical, pharmacologic, toxicologic, biological and other properties of chemical compounds. Let G be a graph with n vertices and m edges. For a given edge uv, the quantity nu(e) denotes the number of vertices closer to u than v, the quantity nv(e) is defined analogously. The vertex PI index defined as the sum of the nu(e) and nv(e). Here the sum is taken over all edges of G. The energy of a graph is defined as the sum of the eigenvalues of adjacency matrix of G and the Laplacian energy of a graph is defined as the sum of the absolute value of difference of laplacian eigenvalues and average degree of G. In theoretical chemistry, the π-electron energy of a conjugated carbon molecule, computed using the Hückel theory, coincides with the energy. Hence results on graph energy assume special significance. The Laplacian matrix of a graph G weighted by the vertex PI weighting is the Laplacian vertex PI matrix and the Laplacian vertex PI eigenvalues of a connected graph G are the eigenvalues of its Laplacian vertex PI matrix. In this study, Laplacian vertex PI energy of a graph is defined of G. We also give some bounds for the Laplacian vertex PI energy of graphs in terms of vertex PI index, the sum of the squares of entries in the Laplacian vertex PI matrix and the absolute value of the determinant of the Laplacian vertex PI matrix.

Keywords: energy, Laplacian energy, laplacian vertex PI eigenvalues, Laplacian vertex PI energy, vertex PI index

Procedia PDF Downloads 203