Detecting communities or the modular structure of real-life networks (e.g. a social
 network or a product purchase network) is an important task because the way a
 network functions is often determined by its communities.
 The traditional approaches to community detection involve modularity-based approaches,
 which generally speaking, construct partitions based on heuristics that
 seek to maximize the ratio of the edges within the partitions to those between
 them. Node embedding approaches, which represent each node in a graph as a
 real-valued vector, transform the problem of community detection in a graph to
 that of clustering a set of vectors. Existing node embedding approaches are primarily
 based on first initiating uniform random walks from each node to construct
 a context of a node and then seeks to make the vector representation of
 the node close to its context. However, standard node embedding approaches do
 not directly take into account the community structure of a network while constructing
 the context around each node. To alleviate this, we explore two different
 threads of work. First, we investigate the use of biased random walks (specifically,
 maximum entropy based walks) to obtain more centrality preserving embedding
 of nodes, which we hypothesize may lead to more effective clusters in the embedded
 space. Second, we propose a community structure aware node embedding
 approach where we incorporate modularity-based partitioning heuristics into
 the objective function of node embedding. We demonstrate that our proposed approach
 for community detection outperforms a number of modularity-based baselines
 as well as K-means on a standard node-embedded vector space (specifically,
 node2vec) on a wide range of real-life networks of different sizes and densities. Partitioning a network (graph) into communities usually leads to better analyzing the functionality of the network and is of immense practical interest for real-world networks, because such communities potentially represent organizational units in social networks, scientific disciplines in authorshipcitation academic publications networks, or functional units in biological networks (e.g. proteinprotein interactions) (Girvan & Newman, 2002; Newman & Girvan, 2004; Waltman & Van Eck, 2013) . A network community represents a set of nodes with a relatively dense set of connections between its members and relatively sparse connections between its member nodes and the ones outside the community. Traditional approaches of community detection incrementally construct a community (set of nodes) by employ an objective function that seeks to maximize its internal connectivity and minimize the number of external edges (Newman & Girvan, 2004; Newman, 2006; Blondel et al., 2008; PratPérez et al., 2014) . Graph representation learning approaches such as (Perozzi et al., 2014; Grover & Leskovec, 2016) represent each node of a graph as a real-valued vector seeking to preserve the correlation between the topological properties of the discrete graph with the distance measures in the embedded metric space. For example, the vectors corresponding to a pair of nodes in the embedded space is usually close (low distance or high inner product similarity) if it is likely to visit a node of the pair with a random walk started at the other one. However, a major limitation of the random walk based node representation learning approach is that a random walk may span across the community from which it stared with, which eventually could lead to representing nodes from different communities in close proximity in the embedding space. This in turn can may not result in effective community detection on application of a standard clustering algorithm, e.g. K-means, in the space of embedded node vectors. Ideally speaking, for effective community detection with a clustering algorithm operating on the embedded space of node vectors, a node embedding algorithm should preserve the community structure from the discrete space of the sets of nodes to the continuous space of real-valued vectors as perceived with the conventional definitions of the distance metric (e.g. l 2 distance) and the inner product between pairs of vectors denoting the similarity between them. In other words, a central (hub) node of a community in the discrete graph representation should be transformed in the embedded space in such a way so that it contains other vectors, corresponding to the nodes of the other members in the community, in its close neighborhood. In our study, we investigate two methods to achieve such a transformation. Our Contributions First, in contrast to the uniform random walk (URW) based contextualization of nodes in standard node embedding approaches, such as node2vec (Grover & Leskovec, 2016) and DeepWalk (Perozzi et al., 2014) , we investigate a maximum-entropy based biased random walk (MERW) Sinatra et al. (2011) , where in contrast to URW, the transition probabilities are non-local, i.e., they depend on the structure of the entire graph. Alternately, in our second proposed approach, we investigate if traditional approaches to community detection that operate on a discrete graph (adjacency matrix), e.g. modularity-heuristic (Clauset et al., 2004) or InfoMap (Rosvall & Bergstrom, 2008) , can be useful to contextualize a node for the purpose of obtaining its embedded representation. In other words, while training a classifier for a node vector that learns to predict its context, we favour those cases where the context nodes are a part of the same community as that of the current node, as predicted by a modularity-based heuristic). We also investigate a combination of the two different community aware embedding approaches, i.e. employing MERW to first contextualize the nodes and then using the weighted training based on the modularity heuristic. The rest of the paper is organized as follows. We first review the literature on community detection and node embedding. We then describe the details about the MERW-based node embedding and community-structure aware node embedding. Next, we describe the setup of our experiments, which is followed by a presentation and analysis of the results. Finally, we conclude the paper with directions for future work.
A community preserving node embedding algorithm that results in more effective detection of communities with a clustering on the embedded space