Abstract Extreme polarization stands as a crucial concern for fostering a healthier web ecosystem. Locating the polarized groups is pivotal in this context. These groups involve nodes forming robust agreements with each other and engaging in collective conflicts with other groups. Previous studies tackle this problem by focusing on the balanced subgraphs in which all (or small) cycles have an even number of negative edges. However, balanced subgraphs in real-world signed networks are often not inherently polarized, such as those with solely positive edges, and any method that targets balanced subgraphs results in sizable communities with dominantly positive interactions. Building on this concern, we propose to utilize cohesion to find polarized subgraphs in this work. Specifically, we identify pairs of cohesively polarized communities where each node within a community has many positive connections with the nodes in the same community and numerous negative connections with the nodes in the opposing community. We introduce a novel measure, called dichotomy, to capture both cohesion and polarization in a given pair of polarized communities. We show that optimizing dichotomy is NP-hard. As a heuristic approach, we employ balanced triangles to develop a hierarchical dense subgraph discovery algorithm, called atom decomposition, that establishes effective seedbeds for polarized communities in signed networks. To address the challenges posed by real-world signed networks, we introduce two additional algorithms to find polarized communities: photon and electron decompositions. Photon decomposition filters out the nodes that engage in unbalanced triangles and yields numerous cohesively balanced communities. Electron decomposition favors polarized triangles over positive triangles to find polarized communities with high dichotomy. Through comprehensive experiments, we demonstrate that our approaches excel in identifying cohesively polarized communities, surpassing the state-of-the-art methods across various metrics. We give interesting anecdotal findings by using our algorithms on a political network among governments in the Cold War era and a business network of company relationships/competitions. Overall, our algorithms exhibit greater effectiveness and efficiency than existing methods, rendering them practical for large-scale networks.

Bipartite graphs are a powerful tool for modeling the interactions between two distinct groups. These bipartite relationships often feature small, recurring structural patterns called motifs which are building blocks for community structure. One promising structure is the induced 6-cycle which consists of three nodes on each node set forming a cycle where each node has exactly two edges. In this paper, we study the problem of counting and utilizing induced 6-cycles in large bipartite networks. We first consider two adaptations inspired by previous works for cycle counting in bipartite networks. Then, we introduce a new approach for node triplets which offer a systematic way to count the induced 6-cycles, used inBatchTripletJoin. Our experimental evaluation shows thatBatchTripletJoinis significantly faster than the other algorithms while being scalable to large graph sizes and number of cores. On a network with$ 112M$edges,BatchTripletJoinis able to finish the computation in 78 mins by using 52 threads. In addition, we provide a new way to identify anomalous node triplets by comparing and contrasting the butterfly and induced 6-cycle counts of the nodes. We showcase several case studies on real-world networks from Amazon Kindle ratings, Steam game reviews, and Yelp ratings.

Complex systems frequently exhibit multi-way, rather than pairwise, interactions. These group interactions cannot be faithfully modeled as collections of pairwise interactions using graphs and instead require hypergraphs. However, methods that analyze hypergraphs directly, rather than via lossy graph reductions, remain limited. Hypergraph motifs hold promise in this regard, as motif patterns serve as building blocks for larger group interactions which are inexpressible by graphs. Recent work has focused on categorizing and counting hypergraph motifs based on the existence of nodes in hyperedge intersection regions. Here, we argue that the relative sizes of hyperedge intersections within motifs contain varied and valuable information. We propose a suite of efficient algorithms for finding top-k triplets of hyperedges based on optimizing the sizes of these intersection patterns. This formulation uncovers interesting local patterns of interaction, finding hyperedge triplets that either (1) are the least similar with each other, (2) have the highest pairwise but not groupwise correlation, or (3) are the most similar with each other. We formalize this as a combinatorial optimization problem and design efficient algorithms based on filtering hyperedges. Our comprehensive experimental evaluation shows that the resulting hyperedge triplets yield insightful information on real-world hypergraphs. Our approach is also orders of magnitude faster than a naive baseline implementation.

Social media has been at the center of discussions about political polarization in the United States. However, scholars are actively debating both the scale of political polarization online, and how important online polarization is to the offline world. One question at the center of this debate is what interactions across parties look like online, and in particular 1) whether increasing the number of such interactions is likely to increase or reduce polarization, and 2) what technological affordances may make it more likely that these cross-party interactions benefit, rather than detract from, existing political challenges. The present work aims to provide insights into the latter; that is, we focus on providing a better understanding of how a set of 400,000 partisan users on a particular social media platform, Twitter, used the platform's affordances to interact within and across parties in a large dataset of tweets about COVID in 2021. Our findings suggest that Republican use of cross-party interaction were both more potent and potentially more strategic during COVID, that cross-party interaction was driven heavily by a small set of users and conversations, and that there exist non-obvious indirect pathways to cross-party exposure when different modes of interaction are chained together (especially retweets of quotes). These findings have implications beyond Twitter, we believe, in understanding how affordances of platforms can help to shape partisan exposure and interaction.

Various complex networks in real-world applications are best represented as a bipartite graph, such as user-product, paper-author, and actor-movie relations. Motif-based analysis has substantial benefits for networks and bipartite graphs are no exception. The smallest non-trivial subgraph in a bipartite graph is a (2,2)-biclique, also known as a butterfly. Although butterflies are succinct, they are limited in capturing the higher-order relations between more than two nodes from the same node set. One promising structure in this context is the induced 6-cycle which consists of three nodes on each node set forming a cycle where each node has exactly two edges. In this paper, we study the problem of counting induced 6-cycles through parallel algorithms. To the best of our knowledge, this is the first study on induced 6-cycle counting. We first consider two adaptations based on previous works for cycle counting in bipartite networks. Then, we introduce a new approach based on the node triplets and offer a systematic way to count the induced 6-cycles. Our final algorithm, BatchTripletJoin, is parallelizable across root nodes and uses minimal global storage to save memory. Our experimental evaluation on a 52 core machine shows that BatchTripletJoin is significantly faster than the other algorithms while being scalable to large graph sizes and number of cores. On a network with 112M edges, BatchTripletJoin is able to finish the computation in 78 mins by using 52 threads.