Big graph data mining and processing have emerged as a crucial area of study. Distributed graph frameworks are commonly employed to process such big graph data in various applications. These frameworks have proven to be highly effective in improving both the accuracy and efficiency of processing large-scale graph data, but little attention has been paid to the algorithmic fairness of such methods. In this paper, we propose a novel graph reweighting algorithm, Homophily-Based Graph Reweighting (HBGR), which can be used with different distributed community detection frameworks. The findings of our study demonstrate that HBGR can significantly enhance the fairness of detected community results, without altering the overall distributed community detection algorithm workflow. Our analysis demonstrates that HBGR outperforms traditional performance-based distributed graph data processing frameworks in terms of fairness across 13 real social network datasets. This enhancement enables us to achieve fairness levels that are comparable, or even superior, to those achieved by linear community detection algorithms while maintaining good efficiency performance. Additionally, we examine the causes of unfairness in distributed community detection algorithms and conduct an interpretability analysis of HBGR's improved fairness performance. Finally, we provide a comprehensive evaluation of the trade-offs between efficiency, accuracy, and fairness in distributed community detection algorithms.

The dynamics of charitable donor co-attendance networks can help fundraisers assess and improve fundraising outcomes. To improve understanding of donor-giving patterns, this study examines a large, multi-year network describing the co-attendance of donors at charitable fundraising events. We analyze the dynamics of co-attendance networks based on their topological structure, shift in node characteristics, and various network properties. Among other results, we observe a 76% increase in giving value for donors that showed increased centrality rank over nonoverlapped snapshots. In the data we examined, 19.14% of the donors whose giving increased and 16.24% of donors that remained in the same giving range exhibited increased co-attendance with high-capacity donors, whereas none of the donors that shifted to a lower class exhibited increased co-attendance with high-capacity donors over the periods, potentially illustrating a positive peer effect on donors. Some similarity was also observed in the giving characteristics of donors who co-attend events, with a 0.211 assortativity coefficient for the giving class of donors as a characteristic of donors when considering network dynamics using a rolling window size of 3 years. This is followed by analyzing the group-level similarities that reveal an interlinked clique of communities with diverse sizes. Our results show that large communities have a higher fraction of wealthy donors.

In the era of big data, distributed graph processing frameworks have become important in processing large-scale graph datasets. Such distributed frameworks exhibit major advantages with respect to scalability, and provide various ways to speed up sequential graph algorithms. However, the literature lacks an analysis on the fairness properties of such distributed algorithms. In this work, we analyze several important distributed frameworks and graph analysis algorithms with respect to their fairness properties. Across numerous real-world network datasets, we demonstrate that distributed algorithms often exhibit worse fairness performance as compared to their sequential counterparts. Moreover, we observe that this phenomenon is often strongly connected to the homophily of the graph dataset– the tendency of nodes to connect to other nodes of the same class.

Social networks form a major parts of people’s lives, and individuals often make important life decisions based on information that spreads through these networks. For this reason, it is important to know whether individuals from different protected groups have equal access to information flowing through a network. In this article, we define theInformation Unfairness (IUF)metric, which quantifies inequality in access to information across protected groups. We then introduceMinIUF, an algorithm for reducing inequalities in information flow by adding edges to the network. Finally, we provide an in-depth analysis of information flow with respect to an attribute of interest, such as gender, across different types of networks to evaluate whether the structure of these networks allows groups to equally access information flowing in the network. Moreover, we investigate the causes of unfairness in such networks and how it can be improved.

In the early stages of a pandemic, epidemiological knowledge of the disease is limited and no vaccination is available. This poses the problem of determining an Early Mitigation Strategy. Previous studies have tackled this problem through finding globally influential nodes that contribute the most to the spread. These methods are often not practical due to their assumptions that (1) accessing the full contact social network is possible; (2) there is an unlimited budget for the mitigation strategy; (3) healthy individuals can be isolated for indefinite amount of time, which in practice can have serious mental health and economic consequences. In this work, we study the problem of developing an early mitigation strategy from a community perspective and propose a dynamic Community-based Mitigation strategy, ComMit. The distinguishing features of ComMit are: (1) It is agnostic to the dynamics of the spread; (2) does not require prior knowledge of contact network; (3) it works within a limited budget; and (4) it enforces bursts of short-term restriction on small communities instead of long-term isolation of healthy individuals. ComMit relies on updated data from test-trace reports and its strategy evolves over time. We have tested ComMit on several real-world social networks. The results of our experiments show that, within a small budget, ComMit can reduce the peak of infection by 73% and shorten the duration of infection by 90%, even for spreads that would reach a steady state of non-zero infections otherwise (e.g., SIS contagion model).

In many network applications, dense subgraphs have proven to be extremely useful. One particular type of dense subgraph known as the k-core has received a great deal of attention. k-cores have been used in a number of important applications, including identifying important nodes, speeding up community detection, network visualization, and others. However, little work has investigated the ‘skeletal’ structure of the k-core, and the effect of such structures on the properties of the overall k-core and network itself. In this paper, we propose the Skeletal Core Subgraph, which describes the backbone of the k-core structure of a graph. We show how to categorize graphs based on their skeletal cores, and demonstrate how to efficiently decompose a given graph into its Skeletal Core Subgraph. We show both theoretically and experimentally the relationship between the Skeletal Core Subgraph and properties of the graph, including its core resilience.

In this article, we consider the problem of crawling a multiplex network to identify the community structure of a layer-of-interest. A multiplex network is one where there are multiple types of relationships between the nodes. In many multiplex networks, some layers might be easier to explore (in terms of time, money etc.). We propose MCS+ , an algorithm that can use the information from the easier to explore layers to help in the exploration of a layer-of-interest that is expensive to explore. We consider the goal of exploration to be generating a sample that is representative of the communities in the complete layer-of-interest. This work has practical applications in areas such as exploration of dark (e.g., criminal) networks, online social networks, biological networks, and so on. For example, in a terrorist network, relationships such as phone records, e-mail records, and so on are easier to collect; in contrast, data on the face-to-face communications are much harder to collect, but also potentially more valuable. We perform extensive experimental evaluations on real-world networks, and we observe that MCS+ consistently outperforms the best baseline—the similarity of the sample that MCS+ generates to the real network is up to three times that of the best baseline in some networks. We also perform theoretical and experimental evaluations on the scalability of MCS+ to network properties, and find that it scales well with the budget, number of layers in the multiplex network, and the average degree in the original network.

Social networks play a vital role in the spread of information through a population, and individuals in networks make important life decisions on the basis of the information to which they have access. In many cases, it is important to evaluate whether information is spreading fairly to all groups in a network. For instance, are male and female students equally likely to hear about a new scholarship? In this paper, we present the information unfairness criterion, which measures whether information spreads fairly to all groups in a network. We perform a thorough case study on the DBLP computer science co-authorship network with respect to gender. We then propose MaxFair, an algorithm to add edges to a network to decrease information unfairness, and evaluate on several real-world network datasets.

In many online social networking platforms, the participation of an individual is motivated by the participation of others. If an individual chooses to leave a platform, this may produce a cascade in which that person's friends then choose to leave, causing their friends to leave, and so on. In some cases, it may be possible to incentivize key individuals to stay active within the network, thus preventing such a cascade. This problem is modeled using the anchored k-core of a network, which, for a network G and set of anchor nodes A, is the maximal subgraph of G in which every node has a total of at least k neighbors between the subgraph and anchors. In this work, we propose Residual Core Maximization (RCM), a novel algorithm for finding b anchor nodes so that the size of the anchored k-core is maximized. We perform a comprehensive experimental evaluation on numerous real-world networks and compare RCM to various baselines. We observe that RCM is more effective and efficient than the state-of-the-art methods: on average, RCM produces anchored k-cores that are 1.65 times larger than those produced by the baseline algorithm, and is approximately 500 times faster on average.

When studying a network, it is often of interest to understand the robustness of that network to noise. Network robustness has been studied in a variety of contexts, examining network properties such as the number of connected components and the lengths of shortest paths. In this work, we present a new network robustness measure, which we refer to as 'sampling robustness'. The goal of the sampling robustness measure is to quantify the extent to which a network sample collected from a graph with errors is a good representation of a network sample collected from that same graph, but without errors. These errors may be introduced by humans or by the system (e.g., mistakes from the respondents or a bug in an API program), and may affect the performance of a data collection algorithm and the quality of the obtained sample. Thus, when data analysts analyze the sampled network, they may wish to know whether such errors will affect future analysis results.

When performing any analysis task, some information may be leaked or scattered among individuals who may not willing to share their information (e.g., number of individual's friends and who they are). Secure multi-party computation (MPC) allows individuals to jointly perform any computation without revealing each individual's input. Here, we present two novel secure frameworks which allow node to securely compute its clustering coefficient, which we evaluate the trade off between efficiency and security of several proposed instantiations. Our results show that the cost for secure computing highly depends on network structure.

Over the past two decades, online social networks have attracted a great deal of attention from researchers. However, before one can gain insight into the behavior or structure of a network, one must first collect appropriate data. Data collection poses several challenges, such as API or bandwidth limits, which require the data collector to carefully consider which queries to make. Many network crawling methods have been proposed; however, their performance depends on network structure. In particular, our previous work in [1] has shown that existing algorithms tend to either (1) Do well at exploring dense areas of a network, but have difficulty in transitioning to new areas of the network, or (2) Easily move between network regions, but fail to fully explore each region. In this work, we introduce DE-Crawler, a novel network crawler that attempts to capture the best of both worlds. DE-Crawler consists of two main stages: Densification, in which the crawler aims to find as many nodes as possible in the current dense region (or community), and Expansion, in which the crawler tries to escape from its current region and move to another dense region. We show that DE-Crawler performs well across networks with different structural properties, outperforming baseline algorithms by up to 28%.

The concept of k-cores is important for understanding the global structure of networks, as well as for identifying central or important nodes within a network. It is often valuable to understand the resilience of the k-cores of a network to attacks and dropped edges (i.e., damaged communications links). We provide a formal definition of a network»s core resilience, and examine the problem of characterizing core resilience in terms of the network»s structural features: in particular, which structural properties cause a network to have high or low core resilience? To measure this, we introduce two novel node properties,Core Strength andCore Influence, which measure the resilience of individual nodes» core numbers and their influence on other nodes» core numbers. Using these properties, we propose theMaximize Resilience of k-Core algorithm to add edges to improve the core resilience of a network. We consider two attack scenarios - randomly deleted edges and randomly deleted nodes. Through experiments on a variety of technological and infrastructure network datasets, we verify the efficacy of our node-based resilience measures at predicting the resilience of a network, and evaluate MRKC at the task of improving a network»s core resilience. We find that on average, for edge deletion attacks, MRKC improves the resilience of a network by 11.1% over the original network, as compared to the best baseline method, which improves the resilience of a network by only 2%. For node deletion attacks, MRKC improves the core resilience of the original network by 19.7% on average, while the best baseline improves it by only 3%.

The structure of real-world complex networks has long been an area of interest, and one common way to describe the structure of a network has been with the k-core decomposition. The core number of a node can be thought of as a measure of its centrality and importance, and is used by applications such as community detection, understanding viral spreads, and detecting fraudsters. However, we observe that the k-core decomposition suffers from an important flaw: namely, it is calculated globally, and so if the network contains distinct regions of different densities, the sparser among these regions may be neglected.

We address the problem of estimating core numbers of nodes by reading edges of a large graph stored in external memory. The core number of a node is the highest k-core in which the node participates. Core numbers are useful in many graph mining tasks, especially ones that involve finding communities of nodes, influential spreaders and dense subgraphs. Large graphs often do not fit on the memory of a single machine. Existing external memory solutions do not give bounds on the required space. In practice, existing solutions also do not scale with the size of the graph. We propose NimbleCore, an iterative external-memory algorithm, which estimates core numbers of nodes using O(n log dmax) space, where n is the number of nodes and dmaxis the maximum node-degree in the graph. We also show that NimbleCore requires O(n) space for graphs with power-law degree distributions. Experiments on forty-eight large graphs from various domains demonstrate that NimbleCore gives space savings up to 60X, while accurately estimating core numbers with average relative error less than 2.3%.

Real-world network datasets are often incomplete. Subsequently, any analysis on such networks is likely to produce skewed results. We examine the following problem: given an incomplete network, which b nodes should be probed to bring as many new nodes as possible into the observed network? For instance, consider someone who has observed a portion (say 1%) of the Twitter network. How should she use a limited budget to reduce the incompleteness of the network? In this work, we propose a novel algorithm, called MAXREACH, which uses a budget b to increase the number of nodes in the observed network. Our experiments, across a range of datasets and conditions, demonstrate the efficacy of MAXREACH.

We present a detailed study on data collection, graph construction, and sampling in Twitter. We observe that sampling on semantic graphs (i.e., graphs with multiple edge types) presents fundamentally distinct challenges from sampling on traditional graphs. The purpose of our work is to present new challenges and initial solutions for sampling semantic graphs. Novel elements of our work include the following: (1) We provide a thorough discussion of problems encountered with naïve breadth-first search on semantic graphs. We argue that common sampling methods such as breadth-first search face specific challenges on semantic graphs that are not encountered on graphs with homogeneous edge types. (2) We present two competing methods for creating semantic graphs from data collects, corresponding to the interactions between sampling of different edge types. (3) We discuss new metrics specific to graphs with multiple edge types, and discuss the effect of the sampling method on these metrics. (4) We discuss issues and potential solutions pertaining to sampling semantic graphs.

In this work, we propose Max-Node sampling, a novel sampling algorithm for data collection. The goal of Max-Node is to maximize the number of nodes observed in the sample, given a budget constraint. Max-Node is based on the intuition that networks contain many densely connected regions (i.e., communities), that may be only weakly connected to another, and to maximize the number of nodes observed, it is critical to transition between communities. The two key phases of our algorithm are Expansion and Densification. The goal of the Expansion phase is to transition to unobserved regions, while the Densification phase aims to collect as many nodes in the current community. We conduct experiments on several real networks, and show an improvement of up to 40% vs. the baselines.

Sampling through crawling is an important research topic in social network analysis. However there is very little existing work on sampling through crawling in directed networks. In this paper we present a new method of sampling a directed network, with the objective of maximizing the node coverage. Our proposed method, Predicted Max Degree (PMD) Sampling, works by predicting which k open nodes are most likely to have the highest number of unobserved neighbors in a particular iteration. These nodes are queried, and the whole process repeats until all the available budget has been used up. We compared PMD against three baseline algorithms with three networks, and saw large improvements vs. baseline sampling algorithms: With a budget of 2000, PMD found 15%, 87.4% and 170.2% more nodes than the closest baseline algorithm in the wiki-Votes, soc-Slashdot and webGoogle networks respectively.

The recent interest in networks has inspired a broad range of work on algorithms and techniques to characterize, identify, and extract communities from networks. Such efforts are complicated by a lack of consensus on what a “community” truly is, and these disagreements have led to a wide variety of mathematical formulations for describing communities. Often, these mathematical formulations, such as modularity and conductance, have been founded in the general principle that communities, like a G ( n , p ) graph, are “round,” with connections throughout the entire community, and so algorithms were developed to optimize such mathematical measures. More recently, a variety of algorithms have been developed that, rather than expecting connectivity through the entire community, seek out very small groups of well-connected nodes and then connect these groups into larger communities. In this article, we examine seven real networks, each containing external annotation that allows us to identify “annotated communities.” A study of these annotated communities gives insight into why the second category of community detection algorithms may be more successful than the first category. We then present a flexible algorithm template that is based on the idea of joining together small sets of nodes. In this template, we first identify very small, tightly connected “subcommunities” of nodes, each corresponding to a single node’s “perception” of the network around it. We then create a new network in which each node represents such a subcommunity, and then identify communities in this new network. Because each node can appear in multiple subcommunities, this method allows us to detect overlapping communities. When evaluated on real data, we show that our template outperforms many other state-of-the-art algorithms.

We consider the problem of determining how similar two networks (without known node-correspondences) are. This problem occurs frequently in real-world applications such as transfer learning and change detection. Many network-similarity methods exist; and it is unclear how one should select from amongst them. We provide the first empirical study on the relationships between different network-similarity methods. Specifically, we present (1) an approach for identifying groups of comparable network-similarity methods and (2) an approach for computing the consensus among a given set of network-similarity methods. We compare and contrast twenty network-similarity methods by applying our approaches to a variety of real datasets spanning multiple domains. Our experiments demonstrate that (1) different network-similarity methods are surprisingly well correlated, (2) some complex network-similarity methods can be closely approximated by a much simpler method, and (3) a few network-similarity methods produce rankings that are very close to the consensus ranking.

Four major factors govern the intricacies of community extraction in networks: (1) the literature offers a multitude of disparate community detection algorithms whose output exhibits high structural variability across the collection, (2) communities identified by algorithms may differ structurally from real communities that arise in practice, (3) there is no consensus characterizing how to discriminate communities from noncommunities, and (4) the application domain includes a wide variety of networks of fundamentally different natures. In this article, we present a class separability framework to tackle these challenges through a comprehensive analysis of community properties. Our approach enables the assessment of the structural dissimilarity among the output of multiple community detection algorithms and between the output of algorithms and communities that arise in practice. In addition, our method provides us with a way to organize the vast collection of community detection algorithms by grouping those that behave similarly. Finally, we identify the most discriminative graph-theoretical properties of community signature and the small subset of properties that account for most of the biases of the different community detection algorithms. We illustrate our approach with an experimental analysis, which reveals nuances of the structure of real and extracted communities. In our experiments, we furnish our framework with the output of 10 different community detection procedures, representative of categories of popular algorithms available in the literature, applied to a diverse collection of large-scale real network datasets whose domains span biology, online shopping, and social systems. We also analyze communities identified by annotations that accompany the data, which reflect exemplar communities in various domain. We characterize these communities using a broad spectrum of community properties to produce the different structural classes. As our experiments show that community structure is not a universal concept, our framework enables an informed choice of the most suitable community detection method for identifying communities of a specific type in a given network and allows for a comparison of existing community detection algorithms while guiding the design of new ones.

Three major factors govern the intricacies of community extraction in networks: (1) the application domain includes a wide variety of networks of fundamentally different natures, (2) the literature offers a multitude of disparate community detection algorithms, and (3) there is no consensus characterizing how to discriminate communities from non-communities. In this paper, we present a comprehensive analysis of community properties through a class separability framework. Our approach enables the assessement of the structural dissimilarity among the output of multiple community detection algorithms and between the output of algorithms and communities that arise in practice. To demostrate this concept, we furnish our method with a large set of structural properties and multiple community detection algorithms. Applied to a diverse collection of large scale network datasets, the analysis reveals that (1) the different detection algorithms extract fundamentally different structures; (2) the structure of communities that arise in practice is closest to that of communities that random-walk-based algorithms extract, although still siginificantly different from that of the output of all the algorithms; and (3) a small subset of the properties are nearly as discriminative as the full set, while making explicit the ways in which the algorithms produce biases. Our framework enables an informed choice of the most suitable community detection method for a given purpose and network and allows for a comparison of existing community detection algorithms while guiding the design of new ones.