On the complexity and approximation of non-unique probe selection using d-disjunct matrix

In this paper, we studied the MINimum-d-Disjunct Submatrix (MIN-d-DS), which can be used to select the minimum number of non-unique probes for viruses identification. We prove that MIN-d-DS is NP-hard for any fixed d. Using d-disjunct matrix, we present an O(log k)-approximation algorithm where k is an upper bound on the maximum number of targets hybridized to a probe. We also present a (1+(d+1)log n)-approximation algorithm to identify at most d targets in the presence of experimental errors. Our approximation algorithms also yield a linear time complexity for the decoding algorithms. The research of T. Znati was supported in part by National Science Foundation under grant CCF-0548895.     

On the approximability of positive influence dominating set in social networks

In social networks, there is a tendency for connected users to match each other’s behaviors. Moreover, a user likely adopts a behavior, if a certain fraction of his family and friends follows that behavior. Identifying people who have the most influential effect to the others is of great advantages, especially in politics, marketing, behavior correction, and so on. Under a graph-theoretical framework, we study the positive influence dominating set (PIDS) problem that seeks for a minimal set of nodes $\mathcal{P}$ such that all other nodes in the network have at least a fraction ρ>0 of their neighbors in $\mathcal{P}$ . We also study a different formulation, called total positive influence dominating set (TPIDS), in which even nodes in $\mathcal{P}$ are required to have a fraction ρ of neighbors inside $\mathcal{P}$ . We show that neither of these problems can be approximated within a factor of (1??)lnmax{Δ,|V|^1/2}, where Δ is the maximum degree. Moreover, we provide a simple proof that both problems can be approximated within a factor lnΔ+O(1). In power-law networks, where the degree sequence follows a power-law distribution, both problems admit constant factor approximation algorithms. Finally, we present a linear-time exact algorithms for trees.     

Maximizing misinformation restriction within time and budget constraints

Online social networks have become popular media worldwide. However, they also allow rapid dissemination of misinformation causing negative impacts to users. With a source of misinformation, the longer the misinformation spreads, the greater the number of affected users will be. Therefore, it is necessary to prevent the spread of misinformation in a specific time period. In this paper, we propose maximizing misinformation restriction (\(\mathsf {MMR}\)) problem with the purpose of finding a set of nodes whose removal from a social network maximizes the influence reduction from the source of misinformation within time and budget constraints. We demonstrate that the \(\mathsf {MMR}\) problem is NP-hard even in the case where the network is a rooted tree at a single misinformation node and show that the calculating objective function is #P-hard. We also prove that objective function is monotone and submodular. Based on that, we propose an \(1{-}1/\sqrt{e}\)-approximation algorithm. We further design efficient heuristic algorithms, named \(\mathsf {PR}\)-\(\mathsf {DAG}\) to show \(\mathsf {MMR}\) in very large-scale networks.     

Immigrant Generation,School Procedural Justice,and Educational Attainment

There is much educational concern about the disproportionate punishment of racial/ethnic minority students within U.S. public schools. Research evidence indicates that school punishment exacerbates the already-known racial/ethnic inequalities within the educational system. What remains uncertain is if and how school punishment, justice, and fairness are moderating educational attainment for the children of immigrants. This study utilizes data from the Education Longitudinal Study of 2002 and incorporates multilevel analysis to examine how school punishment, justice, and fairness influence the educational attainment of children of immigrants. The study draws on straight-line and segmented assimilation frameworks to evaluate variation in these effects by immigrant generation. Findings do suggest that improved school procedural justice and fairness could enhance educational attainment as well as ameliorate the detrimental impact of school punishment; however, these patterns are segmented by immigrant generation and race/ethnicity.     

Does greater household wealth make young children perform better? The case of Vietnam

Our study examines factors affecting children's cognitive ability in Vietnam for the period 2006–2016. We find that conditional wealth has a positive association with the cognitive capacity of 15-year-old children, manifested in all three methods of measurement: vocabulary points, math scores and reading comprehension scores in Vietnamese. Notably, the finding implies that improving household wealth after the children's first 1,000 days still plays an important role in the cognitive development of 5–12-year-olds. Also, it suggests that using conditional wealth enables us to capture the impact of economic shocks, thereby having a significant effect on the cognitive ability of children.     

Robustness of power-law networks: its assessment and optimization

Many practical complex networks, such as the Internet, WWW and social networks, are discovered to follow power-law distribution in their degree sequences, i.e., the number of nodes with degree \(i\) in these networks is proportional to \(i^{-\beta }\) for some exponential factor \(\beta > 0\). However, these networks also expose their vulnerabilities to a great number of threats such as adversarial attacks on the Internet, cyber-crimes on the WWW or malware propagations on social networks. Although power-law networks have been found robust under random attacks and vulnerable to intentional attacks via experimental observations, how to better understand their vulnerabilities from a theoretical point of view still remains open. In this paper, we study the vulnerability of power-law networks under random attacks and adversarial attacks using the in-depth probabilistic analysis on the theory of random power-law graph models. Our results indicate that power-law networks are able to tolerate random failures if their exponential factor \(\beta \) is \(<\)2.9, and they are more robust against intentional attacks if \(\beta \) is smaller. Furthermore, we reveal the best range \([1.8, 2.5]\) for the exponential factor \(\beta \) by optimizing the complex networks in terms of both their vulnerabilities and costs. When \(\beta < 1.8\), the network maintenance cost is very expensive, and when \(\beta > 2.5\) the network robustness is unpredictable since it depends on the specific attacking strategy.     

Online set multicover algorithms for dynamic D2D communications

Motivated by the dynamic resource allocation problem for device-to-device (D2D) communications, we study the online set multicover problem (OSMC). In the online set multicover, the set X of elements to be covered is unknown in advance; furthermore, the coverage requirement of each element \(x \in X\) is initially unknown. Elements of X together with coverage requirements are presented one at a time in an online fashion; and a feasible solution must be maintained at all times. We provide the first deterministic, online algorithms for OSMC with competitive ratios. We consider two versions of OSMC; in the first, each set may be picked only once, while the second version allows each set to be picked multiple times. For both versions, we present the first deterministic, online algorithms, with competitive ratios \(O( \log n \log m )\) and \(O( \log n (\log m + \log k) )\), repectively, where n is the number of elements, m is the number of sets, and k is the maximum coverage requirement. By simulation, we show the efficacy of these algorithms for resource allocation in the D2D setting by analyzing network throughput and other metrics, obtaining a large improvement in running time over offline methods.     

Fifty Shades Flipped: Effects of Reading Erotica Depicting a Sexually Dominant Woman Compared to a Sexually Dominant Man

The present study examined the effects of reading submission- and dominance-themed erotica on attitudes toward women and rape, ideal partner preferences, and subjective sexual arousal. Heterosexual male (n = 241) and female (n = 240) participants read one of three erotic stories depicting male dominance, female dominance, or no dominance, or a fourth nonerotic control story. First, we found that after reading about a sexually dominant man, women reported increased benevolent sexism compared to men, and men reported increased rape myth acceptance compared to women. Second, men and women showed a similar level of preference for partner dominance after reading about a sexually dominant woman. This was in contrast to the typical pattern revealed in all other conditions, whereby women were more likely to favor dominant partners relative to men. Finally, we found no evidence to support the hypothesis that the story describing male dominance would be the most arousing. Rather, all three erotic stories were equally sexually arousing compared to the control condition, and men and women did not differ in the extent to which the erotic stories aroused them. Theoretical and practical implications are discussed.     

An Approximation for Minimum Multicast Route in Optical Networks with Nonsplitting Nodes

Consider the problem of computing the minimum-weight multicast route in an optical network with both nonsplitting and splitting nodes. This problem can be reduced to the minimum Hamiltonian path problem when all nodes are nonsplitting, and the Steiner minimum tree problem when all nodes are splitting. Therefore, the problem is NP-hard. Previously, the best known polynomial-time approximation has the performance ratio 3. In this paper, we present a new polynomial-time approximation with performance ratio of 1+ρ, where ρ is the best known approximation performance ratio for the Steiner minimum tree in graph and it has been known that ρ < 1.55. Support in part by National Science Foundation under grants CCF-0514796 and CNS-0524429