Ensuring generalized fairness in batch classification.

In this paper, we consider the problem of batch classification and propose a novel framework for achieving fairness in such settings. The problem of batch classification involves selection of a set of individuals, often encountered in real-world scenarios such as job recruitment, college admissions etc. This is in contrast to a typical classification problem, where each candidate in the test set is considered separately and independently. In such scenarios, achieving the same acceptance rate (i.e., probability of the classifier assigning positive class) for each group (membership determined by the value of sensitive attributes such as gender, race etc.) is often not desirable, and the regulatory body specifies a different acceptance rate for each group. The existing fairness enhancing methods do not allow for such specifications and hence are unsuited for such scenarios. In this paper, we define a configuration model whereby the acceptance rate of each group can be regulated and further introduce a novel batch-wise fairness post-processing framework using the classifier confidence-scores. We deploy our framework across four real-world datasets and two popular notions of fairness, namely demographic parity and equalized odds. In addition to consistent performance improvements over the competing baselines, the proposed framework allows flexibility and significant speed-up. It can also seamlessly incorporate multiple overlapping sensitive attributes. To further demonstrate the generalizability of our framework, we deploy it to the problem of fair gerrymandering where it achieves a better fairness-accuracy trade-off than the existing baseline method.

Classifying and Summarizing Information from Microblogs During Epidemics.

During a new disease outbreak, frustration and uncertainties among affected and vulnerable population increase. Affected communities look for known symptoms, prevention measures, and treatment strategies. On the other hand, health organizations try to get situational updates to assess the severity of the outbreak, known affected cases, and other details. Recent emergence of social media platforms such as Twitter provide convenient ways and fast access to disseminate and consume information to/from a wider audience. Research studies have shown potential of this online information to address information needs of concerned authorities during outbreaks, epidemics, and pandemics. In this work, we target three types of end-users (i) vulnerable population-people who are not yet affected and are looking for prevention related information (ii) affected population-people who are affected and looking for treatment related information, and (iii) health organizations-like WHO, who are interested in gaining situational awareness to make timely decisions. We use Twitter data from two recent outbreaks (Ebola and MERS) to build an automatic classification approach useful to categorize tweets into different disease related categories. Moreover, the classified messages are used to generate different kinds of summaries useful for affected and vulnerable communities as well as health organizations. Results obtained from extensive experimentation show the effectiveness of the proposed approach.

Epidemic spreading through direct and indirect interactions.

In this paper we study the susceptible-infected-susceptible epidemic dynamics, considering a specialized setting where popular places (termed passive entities) are visited by agents (termed active entities). We consider two types of spreading dynamics: direct spreading, where the active entities infect each other while visiting the passive entities, and indirect spreading, where the passive entities act as carriers and the infection is spread via them. We investigate in particular the effect of selection strategy, i.e., the way passive entities are chosen, in the spread of epidemics. We introduce a mathematical framework to study the effect of an arbitrary selection strategy and derive formulas for prevalence, extinction probabilities, and epidemic thresholds for both indirect and direct spreading. We also obtain a very simple relationship between the extinction probability and the prevalence. We pay special attention to preferential selection and derive exact formulas. The analysis reveals that an increase in the diversity in the selection process lowers the epidemic thresholds. Comparing the direct and indirect spreading, we identify regions in the parameter space where the prevalence of the indirect spreading is higher than the direct one.

Intergroup networks as random threshold graphs.

Similar-minded people tend to form social groups. Due to pluralistic homophily as well as a sort of heterophily, people also participate in a wide variety of groups. Thus, these groups generally overlap with each other; an overlap between two groups can be characterized by the number of common members. These common members can play a crucial role in the transmission of information between the groups. As a step towards understanding the information dissemination, we perceive the system as a pruned intergroup network and show that it maps to a very basic graph theoretic concept known as a threshold graph. We analyze several structural properties of this network such as degree distribution, largest component size, edge density, and local clustering coefficient. We compare the theoretical predictions with the results obtained from several online social networks (LiveJournal, Flickr, YouTube) and find a good match.

Constant communities in complex networks.

Identifying community structure is a fundamental problem in network analysis. Most community detection algorithms are based on optimizing a combinatorial parameter, for example modularity. This optimization is generally NP-hard, thus merely changing the vertex order can alter their assignments to the community. However, there has been less study on how vertex ordering influences the results of the community detection algorithms. Here we identify and study the properties of invariant groups of vertices (constant communities) whose assignment to communities are, quite remarkably, not affected by vertex ordering. The percentage of constant communities can vary across different applications and based on empirical results we propose metrics to evaluate these communities. Using constant communities as a pre-processing step, one can significantly reduce the variation of the results. Finally, we present a case study on phoneme network and illustrate that constant communities, quite strikingly, form the core functional units of the larger communities.

Coverage maximization under resource constraints using a nonuniform proliferating random walk.

Information management services on networks, such as search and dissemination, play a key role in any large-scale distributed system. One of the most desirable features of these services is the maximization of the coverage, i.e., the number of distinctly visited nodes under constraints of network resources as well as time. However, redundant visits of nodes by different message packets (modeled, e.g., as walkers) initiated by the underlying algorithms for these services cause wastage of network resources. In this work, using results from analytical studies done in the past on a K-random-walk-based algorithm, we identify that redundancy quickly increases with an increase in the density of the walkers. Based on this postulate, we design a very simple distributed algorithm which dynamically estimates the density of the walkers and thereby carefully proliferates walkers in sparse regions. We use extensive computer simulations to test our algorithm in various kinds of network topologies whereby we find it to be performing particularly well in networks that are highly clustered as well as sparse.

Correlations in complex networks under attack.

For any initially correlated network after any kind of attack where either nodes or edges are removed, we obtain general expressions for the degree-degree probability matrix and degree distribution. We show that the proposed analytical approach predicts the correct topological changes after the attack by comparing the evolution of the assortativity coefficient for different attack strategies and intensities in theory and simulations. We find that it is possible to turn an initially assortative network into a disassortative one, and vice versa, by fine-tuning removal of either nodes or edges. For an initially uncorrelated network, on the other hand, we discover that only a targeted edge-removal attack can induce such correlations.

Coverage-maximization in networks under resource constraints.

Efficient coverage algorithms are essential for information search or dispersal in all kinds of networks. We define an extended coverage problem which accounts for constrained resources of consumed bandwidth B and time T . Our solution to the network challenge is here studied for regular grids only. Using methods from statistical mechanics, we develop a coverage algorithm with proliferating message packets and temporally modulated proliferation rate. The algorithm performs as efficiently as a single random walker but O(B(d-2)/d) times faster, resulting in significant service speed-up on a regular grid of dimension d . The algorithm is numerically compared to a class of generalized proliferating random walk strategies and on regular grids shown to perform best in terms of the product metric of speed and efficiency.

Modeling discrete combinatorial systems as alphabetic bipartite networks: theory and applications.

Genes and human languages are discrete combinatorial systems (DCSs), in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence, and letters or words in a language. Different combinations of these finite units give rise to potentially infinite numbers of genes or sentences. This type of DCSs can be represented as an alphabetic bipartite network (ABN) where there are two kinds of nodes, one type represents the elementary units while the other type represents their combinations. Here, we extend and generalize recent analytical findings for ABNs derived in [Peruani, Europhys. Lett. 79, 28001 (2007)] and empirically investigate two real world systems in terms of ABNs, the codon gene and the phoneme-language network. The one-mode projections onto the elementary basic units are also studied theoretically as well as in real world ABNs. We propose the use of ABNs as a means for inferring the mechanisms underlying the growth of real world DCSs.

Generalized theory for node disruption in finite-size complex networks.

After a failure or attack the structure of a complex network changes due to node removal. Here, we show that the degree distribution of the distorted network, under any node disturbances, can be easily computed through a simple formula. Based on this expression, we derive a general condition for the stability of noncorrelated finite complex networks under any arbitrary attack. We apply this formalism to derive an expression for the percolation threshold f_{c} under a general attack of the form f_{k} approximately k;{gamma} , where f_{k} stands for the probability of a node of degree k of being removed during the attack. We show that f_{c} of a finite network of size N exhibits an additive correction which scales as N;{-1} with respect to the classical result for infinite networks.

Design and characterization of cellular automata based associative memory for pattern recognition.

This paper reports a cellular automata (CA) based model of associative memory. The model has been evolved around a special class of CA referred to as generalized multiple attractor cellular automata (GMACA). The GMACA based associative memory is designed to address the problem of pattern recognition. Its storage capacity is found to be better than that of Hopfield network. The GMACA are configured with nonlinear CA rules that are evolved through genetic algorithm (GA). Successive generations of GA select the rules at the edge of chaos. The study confirms the potential of GMACA to perform complex computations like pattern recognition at the edge of chaos.