WEKO3
アイテム
三角形数え上げに基づくグラフ分割手法によるコミュニティ抽出
https://doi.org/10.18997/00004232
https://doi.org/10.18997/000042320509ae40-abed-4124-8740-22e2646bd2e1
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
jou_k_296.pdf (1.3 MB)
|
|
| アイテムタイプ | 学位論文 = Thesis or Dissertation(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2015-08-05 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_db06 | |||||||||
| 資源タイプ | doctoral thesis | |||||||||
| タイトル | ||||||||||
| タイトル | Graph Decomposition Based on Triangle Count for Community Extraction | |||||||||
| 言語 | en | |||||||||
| タイトル | ||||||||||
| タイトル | 三角形数え上げに基づくグラフ分割手法によるコミュニティ抽出 | |||||||||
| 言語 | ja | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| 著者 |
李, 彦廷
× 李, 彦廷
|
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | 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. | |||||||||
| 目次 | ||||||||||
| 内容記述タイプ | TableOfContents | |||||||||
| 内容記述 | 1 Introduction||2 Community Extraction from Graphs||3 Quasi-k-truss Decomposition for Bipartite Graphs||4 Experiments and Evaluations||5 Conclusion and Future Work | |||||||||
| 備考 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 九州工業大学博士学位論文 学位記番号:情工博甲第296号 学位授与年月日:平成27年3月25日 | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Triangle | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | k-truss | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Community Extraction | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | Graph Decomposition | |||||||||
| アドバイザー | ||||||||||
| 坂本, 比呂志 | ||||||||||
| 学位授与番号 | ||||||||||
| 学位授与番号 | 甲第296号 | |||||||||
| 学位名 | ||||||||||
| 学位名 | 博士（情報工学） | |||||||||
| 学位授与年月日 | ||||||||||
| 学位授与年月日 | 2015-03-25 | |||||||||
| 学位授与機関 | ||||||||||
| 学位授与機関識別子Scheme | kakenhi | |||||||||
| 学位授与機関識別子 | 17104 | |||||||||
| 学位授与機関名 | 九州工業大学 | |||||||||
| 学位授与年度 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 平成26年度 | |||||||||
| 出版タイプ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
| アクセス権 | ||||||||||
| アクセス権 | open access | |||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||
| ID登録 | ||||||||||
| ID登録 | 10.18997/00004232 | |||||||||
| ID登録タイプ | JaLC | |||||||||
