SIGNED A-POLYNOMIALS OF GRAPHS AND POINCARÉ POLYNOMIALS OF REAL TORIC MANIFOLDS

Seo, Seunghyun,Shin, Heesung Korean Mathematical Society 2015 대한수학회보 Vol.52 No.2

Choi and Park introduced an invariant of a finite simple graph, called signed a-number, arising from computing certain topological invariants of some specific kinds of real toric manifolds. They also found the signed a-numbers of path graphs, cycle graphs, complete graphs, and star graphs. We introduce a signed a-polynomial which is a generalization of the signed a-number and gives a-, b-, and c-numbers. The signed a-polynomial of a graph G is related to the $Poincar\acute{e}$ polynomial $P_{M(G)}(z)$, which is the generating function for the Betti numbers of the real toric manifold M(G). We give the generating functions for the signed a-polynomials of not only path graphs, cycle graphs, complete graphs, and star graphs, but also complete bipartite graphs and complete multipartite graphs. As a consequence, we find the Euler characteristic number and the Betti numbers of the real toric manifold M(G) for complete multipartite graphs G.

대용량 그래프에서 효율적인 동적 그래프요약 기법

서호진,김현욱,박기성,이영구 한국정보과학회 2016 데이타베이스 연구 Vol.32 No.1

Graph summarization is a technique for compressing highly dense subgraphs in a massive graph. This technique can be utilized for analyzing the topological characteristics of graphs such as connectivity and skewness of graphs. The state-of-the-art graph summarization technique incrementally divides a large graph into subgraphs based on the hub nodes having higher degrees, and then summarizes each of the divided subgraphs. However, This summarization technique does not consider the frequent changes in a dynamic graph. Therefore, this technique requires a very long execution time since it must summarize the whole graph again whenever the graph changes. In this paper, we propose an efficient dynamic graph summarization technique for a massive graph. The proposed technique updates only the previously summarized subgraphs which are the subjects to be changed. Our technique can identify those summarized subgraphs using the set of hub node candidates without considering the whole graph. In our experiments, we observe that the proposed summarization technique can reduce the runtime by up to 57% compared to the state-of-the-art graph summarization technique. 그래프 요약은 대용량 그래프에서 밀집도가 높은 부분그래프를 압축 표현하는 기법이다. 이러한 그래프 요약은 연결성, 정도 비대칭성 등과 같은 그래프가 갖는 고유한 구조적 정보를 분석하기 위해 사용된다. 기존그래프 요약 기법은 그래프를 차수가 높은 허브 정점을 기준으로 다수의 부분 그래프들로 반복적으로 분할하고, 분할된 부분 그래프들을 각각 요약하였다. 그러나 동적 환경을 고려하지 않아 그래프가 변경될 때마다전체 그래프에 대해 다시 요약 구조를 탐색해야하기 때문에 매우 오랜 수행시간을 갖게 된다. 본 논문은 대용량 그래프에서 효율적인 동적 그래프 요약 기법을 제안한다. 제안하는 기법은 허브 후보 집합과 이전 주기의분할된 부분 그래프를 이용하여 전체 그래프에 대한 재분할 없이 효율적으로 이전 주기의 요약 구조를 갱신한다. 실험을 통하여 제안하는 기법이 기존의 기법보다 최대 57% 수행시간이 향상됨을 보인다.

LSTM 오토인코더를 이용한 가중 그래프 임베딩 기법

서민지(Minji Seo),이기용(Ki Yong Lee) Korean Institute of Information Scientists and Eng 2021 정보과학회논문지 Vol.48 No.1

Graph embedding is the representation of graphs as vectors in a low-dimensional space. Recently, research on graph embedding using deep learning technology have been conducted. However, most research to date has focused mainly on the topology of nodes, and there are few studies on graph embedding for weighted graphs, which has an arbitrary weight on the edges between the nodes. Therefore, in this paper, we proposed a new graph embedding technique for weighted graphs. Given weighted graphs to be embedded, the proposed technique first extracts node-weight sequences that exist inside the graphs, and then encodes each node-weight sequence into a fixed-length vector using an LSTM (Long Short-Term Memory) autoencoder. Finally, for each graph, the proposed technique combines the encoding vectors of node-weight sequences extracted from the graph to generate one final embedding vector. The embedding vectors of the weighted graphs obtained by the proposed technique can be used for measuring the similarity between weighted graphs or classifying weighted graphs. Experiments on synthetic and real datasets consisting of groups of similar weighted graphs showed that the proposed technique provided more than 94% accuracy in finding similar weighted graphs.

Enumerating typical abelian prime-fold coverings of a circulant graph

Feng, R.,Kwak, J.H.,Kwon, Y.S. North-Holland Pub. Co ; Elsevier Science Ltd 2009 Discrete mathematics Vol.309 No.8

Enumerating the isomorphism classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory (see [R. Feng, J.H. Kwak, J. Kim, J. Lee, Isomorphism classes of concrete graph coverings, SIAM J. Discrete Math. 11 (1998) 265-272; R. Feng, J.H. Kwak, Typical circulant double coverings of a circulant graph, Discrete Math. 277 (2004) 73-85; R. Feng, J.H. Kwak, Y.S. Kwon, Enumerating typical circulant covering projections onto a circulant graph, SIAM J. Discrete Math. 19 (2005) 196-207; SIAM J. Discrete Math. 21 (2007) 548-550 (erratum); M. Hofmeister, Graph covering projections arising from finite vector spaces over finite fields, Discrete Math. 143 (1995) 87-97; M. Hofmeister, Enumeration of concrete regular covering projections, SIAM J. Discrete Math. 8 (1995) 51-61; M. Hofmeister, A note on counting connected graph covering projections, SIAM J. Discrete Math. 11 (1998) 286-292; J.H. Kwak, J. Chun, J. Lee, Enumeration of regular graph coverings having finite abelian covering transformation groups, SIAM J. Discrete Math. 11 (1998) 273-285; J.H. Kwak, J. Lee, Isomorphism classes of graph bundles, Canad. J. Math. XLII (1990) 747-761]). A covering is called abelian (or circulant, respectively) if its covering graph is a Cayley graph on an abelian (or a cyclic, respectively) group. A covering p from a Cayley graph Cay(A,X) onto another Cay (Q,Y) is called typical if the map p:A->Q on the vertex sets is a group epimorphism. Recently, the isomorphism classes of connected typical circulant r-fold coverings of a circulant graph are enumerated in [R. Feng, J.H. Kwak, Typical circulant double coverings of a circulant graph, Discrete Math. 277 (2004) 73-85] for r=2 and in [R. Feng, J.H. Kwak, Y.S. Kwon, Enumerating typical circulant covering projections onto a circulant graph, SIAM J. Discrete Math. 19 (2005) 196-207; SIAM J. Discrete Math. 21 (2007) 548-550 (erratum)] for any r. As a continuation of these works, we enumerate in this paper the isomorphism classes of typical abelian prime-fold coverings of a circulant graph.

중학교 교과서의 경제학습에 활용한 수요와 공급 그래프 분석

박영석 한국경제교육학회 2022 경제교육연구 Vol.29 No.2

This study analyzed the supply and demand graphs in middle school textbooks. The analysis criteria were the elements of graph learning, the relevance of graph learning to real life, and the purpose of graph learning. Results of the study were as follows. First, in the learning of supply and demand, the graph did not go beyond the role of an auxiliary means to effectively analyze the learning of economic content. It was necessary to supplement the graph function learning to understand the compositional characteristics of graphs and effectively express information. Second, basic learning related to the construction of the supply and demand graph was insufficient, whereas the example of the graph interpretation and reasoning process was too detailed. Third, when learning the supply and demand graph using the line graph in economics, it is necessary to pay attention to the selection of the axis and the combination of the graph. Fourth, using real life contexts in economic graph learning has the advantage of increasing the learning effect by being familiar with the learner's life experience. However, more research is needed on the reflection of real life contexts in that economic graphs have an advantage in simplifying and analyzing the complex reality. 이 연구는 시장 경제를 학습하는 중학교 교과서에 나타난 수요와 공급 그래프를 그래프 학습의 요소, 그래프 학습의 실생활 관련성, 그래프 학습의 목적을 기준으로 분석하였다. 연구 결과는 다음과 같다. 첫째, 수요와 공급 학습에서 그래프는 경제 내용 학습을 효과적으로 분석하는 보조 수단의 역할을 넘어서지 못하고 있었다. 그래프의 구성 특징을 이해하고 정보를 효과적으로 표현하는 그래프 기능학습이 보완될 필요가 있었다. 둘째, 수요 공급 그래프의 구성과 관련하여 기본적인 학습이 미흡했으며, 이에 비해 그래프의 해석과 추론 과정의 예시는 지나치게 상세했다. 효과적인 그래프 학습전략 모색이 필요하다. 셋째, 경제학에서 선 그래프를 활용하여 수요 공급 그래프를 학습할 때 학습자들이 어렵게 여기는 축의 선택과 그래프의 융합에 유의할 필요가 있다. 넷째, 경제 그래프 학습에서 실생활 맥락을 활용하는 것은 학습자의 생활경험에 친숙하여 학습효과가 높아지는 장점이 있다. 그러나 경제 그래프가 복잡한 현실을 단순화시켜 분석하는 것도 장점이 있다는 점에서 실생활 맥락 반영에 대해서는 더 연구가 필요하다.

The Classification of random graph models using graph centralities

Tae-Soo Cho(조태수),Chi-Geun Han(한치근),Sang-Hoon Lee(이상훈) 한국컴퓨터정보학회 2019 韓國컴퓨터情報學會論文誌 Vol.24 No.7

In this paper, a classification method of random graph models is proposed and it is based on centralities of the random graphs. Similarity between two random graphs is measured for the classification of random graph models. The similarity between two random graph models G<SUP>R₁</SUP> and G<SUP>R₂</SUP>is defined by the distance of G<SUP>R₁</SUP> and G<SUP>R₂</SUP>, where G<SUP>R₂</SUP> is a set of random graph G<SUP>R₂</SUP> ={G₁<SUP>R₂</SUP>,...,Gp<SUP>R₂</SUP> that have the same number of nodes and edges as random graph G<SUP>R₁</SUP>. The distance(G<SUP>R₁</SUP> ,G<SUP>R₂</SUP>) is obtained by comparing centralities of G<SUP>R₁</SUP> and G<SUP>R₂</SUP>. Through the computational experiments, we show that it is possible to compare random graph models regardless of the number of vertices or edges of the random graphs. Also, it is possible to identify and classify the properties of the random graph models by measuring and comparing similarities between random graph models.

A Graph Embedding Technique for Weighted Graphs Based on LSTM Autoencoders

( Minji Seo ),( Ki Yong Lee ) 한국정보처리학회 2020 Journal of information processing systems Vol.16 No.6

A graph is a data structure consisting of nodes and edges between these nodes. Graph embedding is to generate a low dimensional vector for a given graph that best represents the characteristics of the graph. Recently, there have been studies on graph embedding, especially using deep learning techniques. However, until now, most deep learning-based graph embedding techniques have focused on unweighted graphs. Therefore, in this paper, we propose a graph embedding technique for weighted graphs based on long short-term memory (LSTM) autoencoders. Given weighted graphs, we traverse each graph to extract node-weight sequences from the graph. Each node-weight sequence represents a path in the graph consisting of nodes and the weights between these nodes. We then train an LSTM autoencoder on the extracted node-weight sequences and encode each nodeweight sequence into a fixed-length vector using the trained LSTM autoencoder. Finally, for each graph, we collect the encoding vectors obtained from the graph and combine them to generate the final embedding vector for the graph. These embedding vectors can be used to classify weighted graphs or to search for similar weighted graphs. The experiments on synthetic and real datasets show that the proposed method is effective in measuring the similarity between weighted graphs.

SIGNED A-POLYNOMIALS OF GRAPHS AND POINCAR´E POLYNOMIALS OF REAL TORIC MANIFOLDS

서승현,신희성 대한수학회 2015 대한수학회보 Vol.52 No.2

Choi and Park introduced an invariant of a finite simple graph, called signed a-number, arising from computing certain topological invariants of some specific kinds of real toric manifolds. They also found the signed a-numbers of path graphs, cycle graphs, complete graphs, and star graphs. We introduce a signed a-polynomial which is a generalization of the signed a-number and gives a-, b-, and c-numbers. The signed a-poly- nomial of a graph G is related to the Poincar´e polynomial PM(G)(z), which is the generating function for the Betti numbers of the real toric manifold M(G). We give the generating functions for the signed a- polynomials of not only path graphs, cycle graphs, complete graphs, and star graphs, but also complete bipartite graphs and complete multipartite graphs. As a consequence, we find the Euler characteristic number and the Betti numbers of the real toric manifold M(G) for complete multi- partite graphs G.

중고등학생들의 과학 그래프 작성 및 해석 능력

김태선,김범기 한국과학교육학회 2002 한국과학교육학회지 Vol.22 No.4

그래프의 상징적인 의미를 학생들이 해석할 수 있다고 교사들이 종종 가정하는 반면, 이러한 가정은 견고한 연구에 기초를 두고 있지 않다. 따라서 그래프를 구성하거나 해석하는 능력을 학생들이 지니고 있는지 알아보는 연구가 필요하다. 또한 불행하게도 많은 학생들이 이러한 그래프 기능을 제대로 갖추지 못하고 있다는 연구결과들을 결부시켜 생각해 볼 때, 이 영역이 연구할 가치와 내용이 많음을 알 수 있다. 따라서 우리나라 7학년에서 12학년에 이르는 학생들의 그래프 능력은 어떠한지 알고자 TOGS(The Test of Graphing in Science)검사를 실시하였다. 학년이 올라감에 따라 그래프 능력도 점차적으로 향상되는 결과를 보였다. 그러나 그래프 능력의 하위요소로 선정된 9가지 요소 중에서 그래프를 작성하는 능력과 관련된 세 가지 하위 요소, 즉 축에 눈금을 매기는 기능, 축에 관련된 변수를 지정하는 기능 및 경향을 알도록 실험데이터로부터 적적한 하나의 선을 그리는 기능에서 부족함을 보였다. 이러한 결과는 그래프와 관련된 교육에서 그래프를 작성하는 것보다 해석하는 쪽에 상대적으로 더 치중하였음을 시사해준다. TOGS검사에서 좋은 점수를 받은 학생들일수록 이러한 차이점이 더 두드러지게 나타났다. Science teachers often suppose that students are able to know the symbolical meaning of graphs when they see the graphs. But such a assumption is not based on the firm theories but a mere image. And we need to search them for holding the abilities to construct and to interpret. In addition, unfortunately, many researchers show that they scarcely have the graphing skills. And then, The Test of Graphing in Science(TOGS) was administered to 535 7th to 12th graders, for we search them for holding the graphing abilities to some degree. Though the higher grade, the better score, they lack the first three among 9 objectives of TOGS which are scaling axes, assigning variables to the axes, using a best fit line, plotting points, translating a graph that displays the data, selecting the corresponding value for y(or x), interrelating/extrapolating graphs, describing the relationship between variables, interrelating the results of the two graphs. It was concluded from this that subjects' graph construction is lower than their graph interpretation in graph skills. It suggests that school science have a bias toward graph interpretation. This tendency represents more strikingly in the case of upper students in TOGS than the others'.

n-th power signed graphs

Siva Kota Reddy,Vijay,Lokesha 장전수학회 2009 Proceedings of the Jangjeon mathematical society Vol.12 No.3

A signed graph (marked graph) is an ordered pair S = (G, σ) (S = (G, μ)), where G = (V,E) is a graph called the underlying graph of S and σ : E → {+, −} (μ : V → {+, −}) is a function. The n-th power graph of a graph G = (V,E) is a graph Gn = (V,E'), with same vertex set as G, and has two vertices u and v are adjacent if their distance in G is n or less. Analogously, one can define the nth power signed graph of a signed graph S = (G, σ). Consider the marking μ on vertices of S defined as follows: each vertex v ∈ V , μ(v) is the product of the signs on the edges incident at v. The nth power signed graph of S is a signed graph Sn = (Gn, σ') where Gn is the underlying graph of Sn, where for any edge e = uv 2 Gn, 0(uv) = μ(u)μ(v). It is shown that for any signed graph S, its nth power signed graph Sn is balanced. We then give structural characterization of n-th power signed graphs. Two signed graphs S1 and S2 are switiching equivalent written S1 ~ S2, whenever there exists a marking μ of S1 such that the signed graph Sμ(S1) obtained by changing the sign of every edge of S1 to its opposite whenever its end vertices are of opposite signs, is isomorphic to S2. Further, we present solutions of some signed graph switching equations involving the line signed graph, complement and n-th power signed graph operations. One such equation (L(S))n ~ S generalizes a result of P. Siva Kota Reddy and M. S. Subramanya (L(S) ~ S) [11].