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

• 資料種別: 博士論文
• タイトル: 三角形数え上げに基づくグラフ分割手法によるコミュニティ抽出
• 著者・編者: 李, 彦廷
• 著者標目: 李, 彦廷
• 出版年月日等: 2015-03-25
• 出版年（W3CDTF）: 2015-03-25
• 並列タイトル等: Graph Decomposition Based on Triangle Count for Community Extraction
• 授与機関名: 九州工業大学
• 授与年月日: 2015-03-25
• 授与年月日（W3CDTF）: 2015-03-25
• 報告番号: 甲第296号
• 学位: 博士（情報工学）
• 博論授与番号: 甲情工第296号
• 本文の言語コード: eng
• 件名標目: Triangle; k-truss; Community Extraction; Graph Decomposition
• 対象利用者: 一般
• 一般注記: 九州工業大学博士学位論文 学位記番号:情工博甲第296号 学位授与年月日:平成27年3月25日; 平成26年度
• DOI: 10.18997/00004232; https://doi.org/10.18997/00004232
• 国立国会図書館永続的識別子: info:ndljp/pid/9491425; https://dl.ndl.go.jp/pid/9491425
• コレクション（共通）: 障害者向け資料
• コレクション（障害者向け資料：レベル1）: テキストデータ
• コレクション（個別）: 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• 収集根拠: 博士論文（自動収集）
• 受理日（W3CDTF）: 2015-09-01T13:12:47+09:00
• 記録形式（IMT）: PDF; application/pdf
• オンライン閲覧公開範囲: 国立国会図書館内限定公開
• デジタル化資料送信: 図書館・個人送信対象外
• 遠隔複写可否（NDL）: 可
• 掲載誌（URI）: https://doi.org/10.18997/00004232; http://hdl.handle.net/10228/5452
• 連携機関・データベース: 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

• 要約等: 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
• 記録形式（IMT）: application/pdf
• 一次資料へのリンクURL: jou_k_296.pdf （fulltext）; https://kyutech.repo.nii.ac.jp/record/4238/files/jou_k_296.pdf
• オンライン閲覧公開範囲: インターネット公開
• 連携機関・データベース: 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• 提供元機関・データベース: 九州工業大学 : キューテイカー

目次

2017-04-02 再収集

2017-10-02 再収集

2023-03-04 再収集

2023-08-05 再収集

2023-12-06 再収集