A no selfedge stochastic block model and a heuristic algorithm for balanced anticommunity detection in networks Abstract   Many realworld networks own the characteristic of anticommunity structure, i.e. disassortative structure, where nodes share no or few connections inside their groups but most of their connections outside. Detecting anticommunity structure can explore negative relations among objects. However, the structures output by the existing algorithms are unbalanced, leading to no or few negative relations to be explored in some groups. Stochastic block models are promising methods for exploring disassortative structures in networks, but their results are highly dependent on the observed structure of a network. In this paper, we first improve the classic stochastic block model and propose a No sElfedge Stochastic blOck Model (NESOM) for anticommunity structure. NESOM considers the edges inside and among groups, respectively, and evolves a new objective function for evaluating anticommunity structure. And then, a new heuristic algorithm NESOMAC is proposed for balanced anticommunity detection, which consists of three stages: creation of initial structure, decomposition of redundant group, and adjustment of group membership. Inspired by NESOM, we finally develop a new synthetic benchmark NESOMNet for performance comparison. Experimental results on NESOMNet with up to 100,000 nodes and 16 realworld networks demonstrate the effectiveness of NESOMAC in anticommunity detection when compared with five stateoftheart algorithms.

Discrete Overlapping Community Detection with Pseudo Supervision Community detection is of significant importance in understanding the structures and functions of networks. Recently, overlapping community detection has drawn much attention due to the ubiquity of overlapping community structures in realworld networks. Nonnegative matrix factorization (NMF), as an emerging standard framework, has been widely employed for overlapping community detection, which obtains nodesu0027 soft community memberships by factorizing the adjacency matrix into lowrank factor matrices. However, in order to determine the ultimate community memberships, we have to postprocess the realvalued factor matrix by manually specifying a threshold on it, which is undoubtedly a difficult task. Even worse, a unified threshold may not be suitable for all nodes. To circumvent the cumbersome postprocessing step, we propose a novel discrete overlapping community detection approach, i.e., Discrete Nonnegative Matrix Factorization (DNMF), which seeks for a discrete (binary) community membership matrix directly. Thus DNMF is able to assign explicit community memberships to nodes without postprocessing. Moreover, DNMF incorporates a pseudo supervision module into it to exploit the discriminative information in an unsupervised manner, which further enhances its robustness. We thoroughly evaluate DNMF using both synthetic and realworld networks. Experiments show that DNMF has the ability to outperform stateoftheart baseline approaches.