Konstantin Kuzmin

The value of research containing novel combinations of molecules can be seen in many innovative and award-winning research programs. Despite calls to use innovative approaches to address common diseases, an increasing majority of research funding goes toward “safe” incremental research. Counteracting this trend by nurturing novel and potentially transformative scientific research is challenging and it must be supported in competition with established research programs. Therefore, we propose a tool that helps to resolve the tension between safe/fundable research vs. high-risk/potentially transformational research. It does this by identifying hidden overlapping interests around novel molecular research topics. Specifically, it identifies paths of molecular interactions that connect research topics and hypotheses that would not typically be associated, as the basis for scientific collaboration. Because these collaborations are related to the scientists’ present trajectory, they are low risk and can be initiated rapidly. Unlike most incremental steps, these collaborations have the potential for leaps in understanding, as they reposition research for novel disease applications. We demonstrate the use of this tool to identify scientists who could contribute to understanding the cellular role of genes with novel associations with Alzheimer’s disease, which have not been thoroughly characterized, in part due to the funding emphasis on established research.

Biological functions are carried out by groups of interacting molecules, cells or tissues, known as communities. Membership in these communities may overlap when biological components are involved in multiple functions. However, traditional clustering methods detect non-overlapping communities. These detected communities may also be unstable and difficult to replicate, because traditional methods are sensitive to noise and parameter settings. These aspects of traditional clustering methods limit our ability to detect biological communities and therefore our ability to understand biological functions. To address these limitations and detect robust overlapping biological communities, we propose an unorthodox clustering method called SpeakEasy which identifies communities using top-down and bottom-up approaches simultaneously. Specifically, nodes join communities based on their local connections, as well as global information about the network structure. This method can quantify the stability of each community, automatically identify the number of communities and quickly cluster networks with hundreds of thousands of nodes. SpeakEasy shows top performance on synthetic clustering benchmarks and accurately identifies meaningful biological communities in a range of datasets, including: gene microarrays, protein interactions, sorted cell populations, electrophysiology and fMRI brain imaging.

Modularity is widely used to effectively measure the strength of the disjoint community structure found by community detection algorithms. Although several overlapping extensions of modularity were proposed to measure the quality of overlapping community structure, there is lack of systematic comparison of different extensions. To fill this gap, we overview overlapping extensions of modularity to select the best. In addition, we extend the Modularity Density metric to enable its usage for overlapping communities. The experimental results on four real networks using overlapping extensions of modularity, overlapping modularity density, and six other community quality metrics show that the best results are obtained when the product of the belonging coefficients of two nodes is used as the belonging function. Moreover, our experiments indicate that overlapping modularity density is a better measure of the quality of overlapping community structure than other metrics considered.

Communities in networks are groups of nodes whose connections to the nodes in a community are stronger than with the nodes in the rest of the network. Quite often nodes participate in multiple communities; that is, communities can overlap. In this paper, we first analyze what other researchers have done to utilize high performance computing to perform efficient community detection in social, biological, and other networks. We note that detection of overlapping communities is more computationally intensive than disjoint community detection, and the former presents new challenges that algorithm designers have to face. Moreover, the efficiency of many existing algorithms grows superlinearly with the network size making them unsuitable to process large datasets. We use the Speaker-Listener Label Propagation Algorithm (SLPA) as the basis for our parallel overlapping community detection implementation. SLPA provides near linear time overlapping community detection and is well suited for parallelization. We explore the benefits of a multithreaded programming paradigm and show that it yields a significant performance gain over sequential execution while preserving the high quality of community detection. The algorithm was tested on four real-world datasets with up to 5.5 million nodes and 170 million edges. In order to assess the quality of community detection, at least 4 different metrics were used for each of the datasets.

Modularity is widely used to effectively measure the strength of the disjoint community structure found by community detection algorithms. Although several overlapping extensions of modularity were proposed to measure the quality of overlapping community structure, there is lack of systematic comparison of different extensions. To fill this gap, we overview overlapping extensions of modularity to select the best. In addition, we extend the Modularity Density metric to enable its usage for overlapping communities. The experimental results on four real networks using overlapping extensions of modularity, overlapping modularity density, and six other community quality metrics show that the best results are obtained when the product of the belonging coefficients of two nodes is used as the belonging function. Moreover, our experiments indicate that overlapping modularity density is a better measure of the quality of overlapping community structure than other metrics considered.

In this paper, we first discuss the definition of modularity (Q) used as a metric for community quality and then we review the modularity maximization approaches which were used for community detection in the last decade. Then, we discuss two opposite yet coexisting problems of modularity optimization; in some cases, it tends to favor small communities over large ones while in others, large communities over small ones (so-called the resolution limit problem). Next, we overview several community quality metrics proposed to solve the resolution limit problem and discuss Modularity Density (Q _ds ), which simultaneously avoids the two problems of modularity. Finally, we introduce two novel fine-tuned community detection algorithms that iteratively attempt to improve the community quality measurements by splitting and merging the given network community structure. The first one, referred to as Fine-tuned , is based on modularity (Q), while the second is based on Modularity Density (Q _ds ) and denoted as Fine-tuned . Then, we compare the greedy algorithm of modularity maximization (denoted as Greedy ), Fine-tuned , and Fine-tuned on four real networks, and also on the classical clique network and the LFR benchmark networks, each of which is instantiated by a wide range of parameters. The results indicate that Fine-tuned Q _ds is the most effective among the three algorithms discussed. Moreover, we show that Fine-tuned Q _ds can be applied to the communities detected by other algorithms to significantly improve their results.

Social networks consist of various communities that host members sharing common characteristics. Often some members of one community are also members of other communities. Such shared membership of different communities leads to overlapping communities. Detecting such overlapping communities is a challenging and computationally intensive problem. In this paper, we investigate the usability of high performance computing in the area of social networks and community detection. We present highly scalable variants of a community detection algorithm called Speaker-listener Label Propagation Algorithm (SLPA). We show that despite of irregular data dependencies in the computation, parallel computing paradigms can significantly speed up the detection of overlapping communities of social networks which is computationally expensive. We show by experiments, how various parallel computing architectures can be utilized to analyze large social network data on both shared memory machines and distributed memory machines, such as IBM Blue Gene.