| 1. |
- Bae, Seung-Hee, et al.
(författare)
-
Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis
- 2017
-
Ingår i: ACM Transactions on Knowledge Discovery from Data. - : Association for Computing Machinery (ACM). - 1556-4681 .- 1556-472X. ; 11:3
-
Tidskriftsartikel (refereegranskat)abstract
- Community detection is an increasingly popular approach to uncover important structures in large networks. Flow-based community detection methods rely on communication patterns of the network rather than structural properties to determine communities. The Infomap algorithm in particular optimizes a novel objective function called the map equation and has been shown to outperform other approaches in third-party benchmarks. However, Infomap and its variants are inherently sequential, limiting their use for large-scale graphs. In this article, we propose a novel algorithm to optimize the map equation called RelaxMap. RelaxMap provides two important improvements over Infomap: parallelization, so that the map equation can be optimized over much larger graphs, and prioritization, so that the most important work occurs first, iterations take less time, and the algorithm converges faster. We implement these techniques using OpenMP on shared-memory multicore systems, and evaluate our approach on a variety of graphs from standard graph clustering benchmarks as well as real graph datasets. Our evaluation shows that both techniques are effective: RelaxMap achieves 70% parallel efficiency on eight cores, and prioritization improves algorithm performance by an additional 20-50% on average, depending on the graph properties. Additionally, RelaxMap converges in the similar number of iterations and provides solutions of equivalent quality as the serial Infomap implementation.
|
|
| 2. |
- Rosvall, Martin, et al.
(författare)
-
Memory in network flows and its effects on spreading dynamics and community detection
- 2014
-
Ingår i: Nature Communications. - : Springer Science and Business Media LLC. - 2041-1723. ; 5, s. 4630-
-
Tidskriftsartikel (refereegranskat)abstract
- Random walks on networks is the standard tool for modelling spreading processes in social and biological systems. This first-order Markov approach is used in conventional community detection, ranking and spreading analysis, although it ignores a potentially important feature of the dynamics: where flow moves to may depend on where it comes from. Here we analyse pathways from different systems, and although we only observe marginal consequences for disease spreading, we show that ignoring the effects of second-order Markov dynamics has important consequences for community detection, ranking and information spreading. For example, capturing dynamics with a second-order Markov model allows us to reveal actual travel patterns in air traffic and to uncover multidisciplinary journals in scientific communication. These findings were achieved only by using more available data and making no additional assumptions, and therefore suggest that accounting for higher-order memory in network flows can help us better understand how real systems are organized and function.
|
|
| 3. |
- Vilhena, Daril A., et al.
(författare)
-
Finding cultural holes : how structure and culture diverge in networks of scholarly communication
- 2014
-
Ingår i: Sociological Science. - : Society for Sociological Science. - 2330-6696. ; 1, s. 221-238
-
Tidskriftsartikel (refereegranskat)abstract
- Divergent interests, expertise, and language form cultural barriers to communication. No formalism has been available to characterize these "cultural holes." Here we use information theory to measure cultural holes and demonstrate our formalism in the context of scientific communication using papers from JSTOR. We extract scientific fields from the structure of citation flows and infer field-specific cultures by cataloging phrase frequencies in full text and measuring the relative efficiency of between-field communication. We then combine citation and cultural information in a novel topographic map of science, mapping citations to geographic distance and cultural holes to topography. By analyzing the full citation network, we find that communicative efficiency decays with citation distance in a field-specific way. These decay rates reveal hidden patterns of cohesion and fragmentation. For example, the ecological sciences are balkanized by jargon, whereas the social sciences are relatively integrated. Our results highlight the importance of enriching structural analyses with cultural data.
|
|
