Abstract | ||
---|---|---|
Graph sampling is a widely used procedure in social network analysis, has attracted great interest in the scientific community and is considered as a very powerful and useful tool in several domains of network analysis. Apart from initial research in this area, which has proposed simple processes such as the classic Random Walk algorithm, Random Node and Random Edge sampling, during the last decade, more advanced graph sampling approaches have been emerged. In this paper, we extensively study the properties of a newly proposed method, the Rank Degree method, which leads to representative graph subgraphs. The Rank Degree is a novel graph exploration method which significantly differs from other existing methods in the literature. The novelty of the Rank Degree lies on the fact that its core methodology corresponds to a deterministic graph exploration; one specific variation corresponds to a number of parallel deterministic traverses that explore the graph. We perform extensive experiments on twelve real-world datasets of a different type, using a variety of measures and comparing our method with Forest Fire, Metropolis Hastings Random Walk and Metropolis Hastings. We provide strong evidence that our approach leads to highly efficient graph sampling; the generated samples preserve several graph properties, to a large extent. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/s13278-017-0441-6 | Social Netw. Analys. Mining |
Keywords | Field | DocType |
Graph sampling,Graph mining,Social network analysis | Strength of a graph,Data mining,Graph property,Theoretical computer science,Null graph,Graph bandwidth,Clique-width,Random geometric graph,Voltage graph,Mathematics,Graph (abstract data type) | Journal |
Volume | Issue | ISSN |
7 | 1 | 1869-5450 |
Citations | PageRank | References |
2 | 0.39 | 30 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nikos Salamanos | 1 | 10 | 2.54 |
Elli Voudigari | 2 | 9 | 1.49 |
E. J. Yannakoudakis | 3 | 37 | 10.64 |