Furong Chang

Community detection in bipartite networks has attracted significant attention due to its broad applications. However, the structural complexity of bipartite networks makes it challenging to directly apply traditional one-mode community detection methods. To address this limitation, this paper proposes a Network Reconstruction Framework (NRF), which enables one-mode algorithms to be directly applied to community detection in bipartite networks by transforming bipartite networks into weighted asymmetric networks. The core of this framework lies in calculating the interaction force based on the common neighbors of node pairs, and reconstructing the network with this as the weight, which retains the original structural information while enhancing the quantitative expression of node associations. To verify the effectiveness of NRF, we integrated three classic one-mode algorithms—Spectral Clustering, Label Propagation, and Louvain—into the framework, conducted experiments on synthetic and real-world network datasets, and compared them with four bipartite network community detection algorithms. The results show that the three NRF-based algorithms not only can stably and accurately identify community structures, but also significantly outperform traditional methods, confirming the superiority of NRF in balancing computational efficiency and structural information retention.

Recently, numerous graph partitioning approaches have been proposed to distribute a big graph to machines in a cluster for distributed computing. Due to heavy communication overhead, these graph partitioning approaches always suffered from long ingress times. Also, heavy communication overhead not only limits the scalability of distributed graph-parallel computing platforms but also reduces the overall performance of clusters. In order to address this problem, this work proposed a near-data source parallel graph partitioning approach noted as NDGP. In NDGP, an edge was preferentially distributed to the machine where it was stored. We implemented NDGP over two classic graph partitioning approaches, Random and Greedy, and one most recently proposed graph partitioning approach, OLPGP, and evaluated its effectiveness. Extensive experiments conducted on real-world data sets verified the effectiveness of NDGP on reducing the communication overhead in the graph partitioning process and demonstrated that NDGP does not induce additional communication and computing workload to the graph-distributed computing that follows.

As the data becomes bigger and more complex, people tend to process it in a distributed system implemented on clusters. Due to the power consumption, cost, and differentiated price-performance, the clusters are evolving into the system with heterogeneous hardware leading to the performance difference among the nodes. Even in a homogeneous cluster, the performance of the nodes is different due to the resource competition and the communication cost. Some nodes with poor performance will drag down the efficiency of the whole system. Existing parallel computing strategies such as bulk synchronous parallel strategy and stale synchronous parallel strategy are not well suited to this problem. To address it, we proposed a free stale synchronous parallel (FSSP) strategy to free the system from the negative impact of those nodes. FSSP is improved from stale synchronous parallel (SSP) strategy, which can effectively and accurately figure out the slow nodes and eliminate the negative effects of those nodes. We validated the performance of the FSSP strategy by using some classical machine learning algorithms and datasets. Our experimental results demonstrated that FSSP was 1.5-12× faster than the bulk synchronous parallel strategy and stale synchronous parallel strategy, and it used 4× fewer iterations than the asynchronous parallel strategy to converge.

Community detection has become a hot topic in complex networks. It plays an important role in information recommendation and public opinion control. Bipartite network, as a special complex network, reflects the characteristics of a kind of network in our life truly and objectively. Therefore, detecting community structure in bipartite networks is of great significance and has practical value. In this work, we first introduce two concepts: a) a micro-bipartite network model Bi-EgoNet which can be used to analyze bipartite network from a micro view to reduce complexity of structure in bipartite networks, and b) a complete bipartite graph that is a special bipartite graph with indivisible property. Then we propose a novel overlapping community detection algorithm based on a complete bipartite graph in micro-bipartite network Bi-EgoNet (CBG&BEN), which combines advantages of both a complete bipartite graph and Bi-EgoNet to get an optimal community structure. CBG&BEN is evaluated on accuracy and effectiveness in several synthetic and real-world bipartite networks. CBG&BEN is compared with other excellent existing algorithms, and our experimental results demonstrated that CBG&BEN is better at detecting overlapping community structure in bipartite networks.