Finding dense bipartite subgraphs and detecting the relations among them is an important problem for affiliation networks that arise in a range of domains, such as social network analysis, word-document clustering, the science of science, internet advertising, and bioinformatics. However, most dense subgraph discovery algorithms are designed for classic, unipartite graphs. Subsequently, studies on affiliation networks are conducted on the co-occurrence graphs (e.g., co-author and co-purchase) that project the bipartite structure to a unipartite structure by connecting two entities if they share an affiliation. Despite their convenience, co-occurrence networks come at a cost of loss of information and an explosion in graph sizes, which limit the quality and the efficiency of solutions. We study the dense subgraph discovery problem on bipartite graphs. We define a framework of bipartite subgraphs based on the butterfly motif (2,2-biclique) to model the dense regions in a hierarchical structure. We introduce efficient peeling algorithms to find the dense subgraphs and build relations among them. We can identify denser structures compared to the state-of-the-art algorithms on co-occurrence graphs in real-world data. Our analyses on an author-paper network and a user-product network yield interesting subgraphs and hierarchical relations such as the groups of collaborators in the same institution and spammers that give fake ratings.
Literature on analysis of bipartite graphs has two main thrusts: extending unipartite graph concepts to bipartite graphs and methods to projections to unipartite graphs. Borgatti and Everett @cite_24 redefined centrality and density metrics for bipartite graphs. Robins and Alexander @cite_5 defined the clustering coefficients for bipartite networks. Working on the bipartite network, instead of its projection, is also useful for matrix partitioning @cite_36 and clustering @cite_37 algorithms. As for projections methods, Newman introduced the weighted projection for scientific collaboration networks @cite_35 . Everett and Borgatti proposed to use dual projections @cite_7 , where the idea is to create projections for both set of nodes, and use the resulting one-mode networks for analysis.
@cite_35 @cite_37 @cite_7 @cite_36 @cite_24 @cite_5
2053761479 2799012401 2259676875 2221846841
We describe a methodology to examine bipartite relational data structures as exemplified in networks of corporate interlocking. These structures can be represented as bipartite graphs of directors and companies, but direct comparison of empirical datasets is often problematic because graphs have different numbers of nodes and different densities. We compare empirical bipartite graphs to simulated random graph distributions conditional on constraints implicit in the observed datasets. We examine bipartite graphs directly, rather than simply converting them to two 1-mode graphs, allowing investigation of bipartite statistics important to connection redundancy and bipartite connectivity. We introduce a new bipartite clustering coefficient that measures tendencies for localized bipartite cycles. This coefficient can be interpreted as an indicator of inter-company and inter-director closenesss but high levels of bipartite clustering have a cost for long range connectivity. We also investigate degree distributions, path lengths, and counts of localized subgraphs. Using this new approach, we compare global structural properties of US and Australian interlocking company directors. By comparing observed statistics against those from the simulations, we assess how the observed graphs are structured, and make comparisons between them relative to the simulated graph distributions. We conclude that the two networks share many similarities and some differences. Notably, both structures tend to be influenced by the clustering of directors on boards, more than by the accumulation of board seats by individual directorss that shared multiple board memberships (multiple interlocks) are an important feature of both infrastructures, detracting from global connectivity (but more so in the Australian case)s and that company structural power may be relatively more diffuse in the US structure than in Australia. This work develops a representation learning method for bipartite networks. While existing works have developed various embedding methods for network data, they have primarily focused on homogeneous networks in general and overlooked the special properties of bipartite networks. As such, these methods can be suboptimal for embedding bipartite networks. In this paper, we propose a new method named BiNE, short for Bipartite Network Embedding, to learn the vertex representations for bipartite networks. By performing biased random walks purposefully, we generate vertex sequences that can well preserve the long-tail distribution of vertices in the original bipartite network. We then propose a novel optimization framework by accounting for both the explicit relations (i.e., observed links) and implicit relations (i.e., unobserved but transitive links) in learning the vertex representations. We conduct extensive experiments on several real datasets covering the tasks of link prediction (classification), recommendation (personalized ranking), and visualization. Both quantitative results and qualitative analysis verify the effectiveness and rationality of our BiNE method. A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, ( )-decomposition refers to a probability distribution over partitions of the metric into sets of low diameter, such that nearby points (parameterized by ( >0 )) are likely to be “clustered” together. Applying this notion to the shortest-path metric in edge-weighted graphs, it is known that n-vertex graphs admit an (O( n) )-padded decomposition (Bartal, 37th annual symposium on foundations of computer science. IEEE, pp 184–193, 1996), and that excluded-minor graphs admit O(1)-padded decomposition (, 25th annual ACM symposium on theory of computing, pp 682–690, 1993; Fakcharoenphol and Talwar, J Comput Syst Sci 69(3), 485–497, 2004; , Proceedings of the 46th annual ACM symposium on theory of computing. STOC ’14, pp 79–88. ACM, New York, NY, USA, 2014). We design decompositions to the family of p-path-separable graphs, which was defined by Abraham and Gavoille (Proceedings of the twenty-fifth annual acm symposium on principles of distributed computing, PODC ’06, pp 188–197, 2006) and refers to graphs that admit vertex-separators consisting of at most p shortest paths in the graph. Our main result is that every p-path-separable n-vertex graph admits an (O( (p n)) )-decomposition, which refines the (O( n) ) bound for general graphs, and provides new bounds for families like bounded-treewidth graphs. Technically, our clustering process differs from previous ones by working in (the shortest-path metric of) carefully chosen subgraphs. Distributed graph processing platforms have helped emerging application domains use commodity clusters and Clouds to analyze large graphs. Vertex-centric programming models like Google Pregel, and their subgraph-centric variants, specify data-parallel application logic for a single vertex or component that execute iteratively. The locality and balancing of components within partitions affects the performance of such platforms. We propose three partitioning strategies for a subgraph-centric model, and analyze their impact on CPU utilization, communication, iterations, and makespan. We analyze these using Breadth First Search and PageRank algorithms on powerlaw and spatio-planar graphs. They are validated on a commodity cluster using our GoFFish subgraph-centric platform, and compared against Apache Giraph vertex-centric platform. Our experiments show upto 8 times improvement in utilization resulting to upto 5 times improvement of overall makespan for flat and hierarchical partitioning over the default strategy due to improved machine utilization. Further, these also exhibit better horizontal scalability relative to Giraph.