Indiana University-Purdue University Indianapolis (IUPUI) / Structural analysis and mining of large and complex graphs for describing the
characteristics of a vertex or an edge in the graph have widespread use in graph
clustering, classification, and modeling. There are various methods for structural
analysis of graphs including the discovery of frequent subgraphs or network motifs,
counting triangles or graphlets, spectral analysis of networks using eigenvectors of
graph Laplacian, and finding highly connected subgraphs such as cliques and quasi
cliques. Unfortunately, the algorithms for solving most of the above tasks are quite
costly, which makes them not-scalable to large real-life networks.
Two such very popular decompositions, k-core and k-truss of a graph give very
useful insight about the graph vertex and edges respectively. These decompositions
have been applied to solve protein functions reasoning on protein-protein networks,
fraud detection and missing link prediction problems.
k-core decomposition with is linear time complexity is scalable to large real-life
networks as long as the input graph fits in the main memory. k-truss on the other
hands is computationally more intensive due to its definition relying on triangles and
their is no linear time algorithm available for it.
In this paper, we propose distributed algorithms on Apache Spark for k-truss and
k-core decomposition of a graph. We also compare the performance of our algorithm
with state-of-the-art Map-Reduce and parallel algorithms using openly available real
world network data. Our proposed algorithms have shown substantial performance
improvement.
| Identifer | oai:union.ndltd.org:IUPUI/oai:scholarworks.iupui.edu:1805/16924 |
| Date | 20 April 2018 |
| Creators | Mandal, Aritra |
| Contributors | Hasan, Mohammad Al, Mohler, George, Song, Fengguang |
| Source Sets | Indiana University-Purdue University Indianapolis |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Rights | Attribution-NoDerivs 3.0 United States, http://creativecommons.org/licenses/by-nd/3.0/us/ |
Page generated in 0.0018 seconds