三角形数え上げに基づくグラフ分割手法によるコミュニティ抽出

• Material Type: 博士論文
• Title: 三角形数え上げに基づくグラフ分割手法によるコミュニティ抽出
• Author/Editor: 李, 彦廷
• Author Heading: 李, 彦廷
• Publication Date: 2015-03-25
• Publication Date (W3CDTF): 2015-03-25
• Alternative Title: Graph Decomposition Based on Triangle Count for Community Extraction
• Degree Grantor: 九州工業大学
• Date Granted: 2015-03-25
• Date Granted (W3CDTF): 2015-03-25
• Dissertation Number: 甲第296号
• Degree Type: 博士（情報工学）
• Conferring No. (Dissertation): 甲情工第296号
• Text Language Code: eng
• Subject Heading: Triangle; k-truss; Community Extraction; Graph Decomposition
• Target Audience: 一般
• Note (General): 九州工業大学博士学位論文 学位記番号:情工博甲第296号 学位授与年月日:平成27年3月25日; 平成26年度
• DOI: 10.18997/00004232; https://doi.org/10.18997/00004232
• Persistent ID (NDL): info:ndljp/pid/9491425; https://dl.ndl.go.jp/pid/9491425
• Collection: 障害者向け資料
• Collection (Materials For Handicapped People:1): テキストデータ
• Collection (particular): 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• Acquisition Basis: 博士論文（自動収集）
• Date Accepted (W3CDTF): 2015-09-01T13:12:47+09:00
• Format (IMT): PDF; application/pdf
• Access Restrictions: 国立国会図書館内限定公開
• Service for the Digitized Contents Transmission Service: 図書館・個人送信対象外
• Availability of remote photoduplication service: 可
• Periodical Title (URI): https://doi.org/10.18997/00004232; http://hdl.handle.net/10228/5452
• Data Provider (Database): 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

• Summary, etc.: A community in a graph is a group of nodes holding similar characteristics or sharing common properties within the graph. It is also referred to as a cluster or a module of graphs. A graph is considered to have the community structure if its nodes can be clustered into several subsets of nodes within a certain degree or density. The community structure is, therefore, one of the most relevant characteristics of graphs. The community structure has attracted tremendous interest in recent years for its various scientific applications. The community structure represents real world network systems, and models many kinds of real world relations, such as biological networks, web pages and social networks. Furthermore, the community structure can be used for analyzing the hierarchical organizations of real world network systems, and for understanding the structure of complicated network systems. Various efficient and effective techniques have been proposed and developed for identifying communities in graphs. Among various community extraction and graph analysis techniques, graph decomposition techniques play a vital role in identifying communities in graphs. The graph decomposition is to divide a graph into a set of dense subgraphs interpreted as communities so that the communities in the graph can be identified and extracted. Then, it is feasible and available to focus on smaller but more crucial areas of the graph when the input graph becomes exceedingly massive. As a definition of dense subgraph, the k-truss formed by triangles is one of the simplest cohesive subgraphs since triangle is the smallest non-trivial clique. By the definition, every edge of the dense subgraph to be decomposed is contained in at least （k .2）-triangle. The task of k-truss decomposition is to find all trusses in a graph. The cohesive subgraphs in a graph can be extracted hierarchically based on the k-truss decomposition method. A triangle （or 3-clique）, consists of three fully connected nodes. It is the densest substructure in a graph. Therefore, the k-truss keeps a good trade-off between computational efficiency and clique approximation. However, the k-truss is not available for bipartite graphs because no triangle occurs in bipartite graphs. The k-truss decomposition method is not applicable to bipartite graphs. In this research, by adding additional edges to a bipartite graph, we extend the notion of k-truss to bipartite graphs, name it the quasi-k-truss, so that the communities as cohesive subgraphs can be extracted from a bipartite graph. Then, the original bipartite graph G is transformed to another graph G′. When a k-truss T is computed from G, the quasi-k-truss is the subgraph whose edges are included in both T and G′, that is, the graph obtained by removing all additional edges from T. Every edge in the quasi-k-truss is contained in at least （k-2）-triangle while a bipartite graph contains no triangles inside. In order to extract triangles virtually in a given bipartite graph, we introduce the auxiliary edges. Alternative to the originally existed edges, the auxiliary edges do not originally exist in bipartite graphs. An auxiliary edge is generated between any two nodes in the same node set if these two nodes share at least one common neighbor node in the other node set. The set of auxiliary edges is generated among all nodes with the same characteristics in a given bipartite graph. The set of auxiliary edges is generated for forming triangles in a given bipartite graph. According to the notion of quasi-k-truss of bipartite graphs, the quasi-k-truss decomposition algorithm is developed for decomposing a bipartite graph, and extracting communities represented by dense subgraphs from a bipartite graph. In the proposed algorithm, initially, a set of auxiliary edges is generated to form triangles in a given bipartite graph. Then, to extract communities from a bipartite graph, the number of triangles containing an edge of the bipartite graph is counted. Communities can be extracted hierarchically from a bipartite graph based on an iterated procedure. In order to improve the computational efficiency, some data structures have been applied to the implementation of the proposed algorithm. Finally, experiments for real world datasets have been conducted to verify the effectiveness and efficiency of the proposed method compared with baseline methods.
• DOI: 10.18997/00004232; https://doi.org/10.18997/00004232
• Format (IMT): application/pdf
• Source: jou_k_296.pdf （fulltext）; https://kyutech.repo.nii.ac.jp/record/4238/files/jou_k_296.pdf
• Access Restrictions: インターネット公開
• Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• Original Data Provider (Database): 九州工業大学 : キューテイカー

Table of Contents

2017-04-02 再収集

2017-10-02 再収集

2023-03-04 再収集

2023-08-05 再収集

2023-12-06 再収集