FALCON or how to compute measures time efficiently on dynamically evolving dense complex networks?
A large number of topics in biology, medicine, neuroscience, psychology and sociology can be generally described via complex networks in order to investigate fundamental questions of structure, connectivity, information exchange and causality. Especially, research on biological networks like functional spatiotemporal brain activations and changes, caused by neuropsychiatric pathologies, is promising. Analyzing those so-called complex networks, the calculation of meaningful measures can be very long-winded depending on their size and structure. Even worse, in many labs only standard desktop computers are accessible to perform those calculations. Numerous investigations on complex networks regard huge but sparsely connected network structures, where most network nodes are connected to only a few others. Currently, there are several libraries available to tackle this kind of networks. A problem arises when not only a few big and sparse networks have to be analyzed, but hundreds or thousands of smaller and conceivably dense networks (e.g. in measuring brain activation over time). Then every minute per network is crucial. For these cases there several possibilities to use standard hardware more efficiently. It is not sufficient to apply just standard algorithms for dense graph characteristics. This article introduces the new library FALCON developed especially for the exploration of dense complex networks. Currently, it offers 12 different measures (like clustering coefficients), each for undirected-unweighted, undirected-weighted and directed-unweighted networks. It uses a multi-core approach in combination with comprehensive code and hardware optimizations. There is an alternative massively parallel GPU implementation for the most time-consuming measures, too. Finally, a comparing benchmark is integrated to support the choice of the most suitable library for a particular network issue.
Institute of Computer Science, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany. Electronic address: rfranke@informatik.hu-berlin.de.
R
R
Franke
Institute of Computer Science, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany. Electronic address: givanova@informatik.hu-berlin.de.
G
G
Ivanova
D000465:Algorithms; D001921:Brain / Q000502:physiology; D001931:Brain Mapping; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D016208:Databases, Factual; D030562:Databases, Protein; D006801:Humans; D051188:Knowledge Bases; D015233:Models, Statistical; D011381:Programming Languages; D025941:Protein Interaction Mapping / Q000379:methods*; D012984:Software
Brain network; Code optimization; Complex network; GPGPU; OpenCL; SSE