1,720,965 research outputs found
Better bounds on the adaptivity gap of influence maximization under full-adoption feedback
No full textIn the influence maximization (IM) problem, we are given a social network and a budget k, and we look for a set of k nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since this definition by Kempe et al. [26]. However, most of the work focuses on the non-adaptive version of the problem where all the k seed nodes must be selected before the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the i-th seed can be based on the observed cascade produced by the first i−1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed under the independent cascade model where each edge is associated with an independent probability of diffusing influence. Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only work for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by n3+1, where n is the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from 2e/(e−1)≈3.16 to 2e2/(e2−1)≈2.31. Then, we consider (β,γ)-bounded-activation graphs, where all nodes but β influence in expectation at most γ∈[0,1) neighbors each; for this class of influence graphs we show that the adaptivity gap is at most [Formula presented]. Finally, we study α-bounded-degree graphs, that is the class of undirected graphs in which the sum of node degrees higher than two is at most α, and show that the adaptivity gap is upper-bounded by α+O(1); we also show that in 0-bounded-degree graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3e3/(e3−1)≈3.16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest
Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback
No full textIn the influence maximization (IM) problem, we are given a social network and a budget k, and we look for a set of k nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since his definition by Kempe, Kleinberg, and Tardos (2003). However, most of the work focuses on the nonadaptive version of the problem where all the k seed nodes must be selected before that the cascade starts. In this paperwe study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the i-th seed can be based on the observed cascade produced by the first i - 1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence. Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only works for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by 3 √n+1, where = is the number of nodes in the graph. Moreover we improve over the known upper bound for in-arborescences from 2e/(e-1) ≈ 3.16 to 2e2/(e2-1) ≈ 2.31. Finally, we study α-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most α, and show that the adaptivity gap is upper-bounded by √α +O(1). Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3e3/e3-1) ≈ 3.16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest
Haematological risk factors for pregnancy outcome in Jamaican women with homozygous sickle cell disease
No full textObjective: to examine the association between fetal outcome and the steady state haematology of mothers with homozygous sickle cell disease.Design: a retrospective observational study. The data were taken from dockets kept at the Sickle Cell Clinic and verified by interview with 45% of the patients.Setting: the Sickle Cell Clinic at the University Hospital of the West Indies or two peripheral clinics operated by the staff of the MRC Laboratories.Subjects: all women aged 14 years or older with homozygous sickle cell disease who had experienced at least one pregnancy in the period 1977 to 1986.Main outcome measures: three fetal outcomes including miscarriages, perinatal deaths, and birthweight.Results: there were 270 singleton pregnancies in 175 women with an overall fetal wastage of 32.2%. There was a significant increased risk of perinatal death with low maternal fetal haemoglobin level, but there were no haematological associations with miscarriages or birthweight.Conclusions: these data suggest that maternal steady-state haematology has little influence on fetal outcome, with the exception that mothers with high HbF levels are less prone to perinatal deaths. Further study is required to investigate acute haematological changes associated with pregnanc
Improved approximation factor for adaptive influence maximization via simple greedy strategies
Full text linkIn the adaptive influence maximization problem, we are given a social network and a budget k, and we iteratively select k nodes, called seeds, in order to maximize the expected number of nodes that are reached by an influence cascade that they generate according to a stochastic model for influence diffusion. The decision on the next seed to select is based on the observed cascade of previously selected seeds. We focus on the myopic feedback model, in which we can only observe which neighbors of previously selected seeds have been influenced and on the independent cascade model, where each edge is associated with an independent probability of diffusing influence. While adaptive policies are strictly stronger than non-adaptive ones, in which all the seeds are selected beforehand, the latter are much easier to design and implement and they provide good approximation factors if the adaptivity gap, the ratio between the adaptive and the non-adaptive optima, is small. Previous works showed that the adaptivity gap is at most 4, and that simple adaptive or non-adaptive greedy algorithms guarantee an approximation of 1/4 (1 - 1/e) ≈ 0.158 for the adaptive optimum. This is the best approximation factor known so far for the adaptive influence maximization problem with myopic feedback. In this paper, we directly analyze the approximation factor of the non-adaptive greedy algorithm, without passing through the adaptivity gap, and show an improved bound of 1/2(1 - 1/e) ≈ 0.316. Therefore, the adaptivity gap is at most 2e/e-1 ≈ 3.164. To prove these bounds, we introduce a new approach to relate the greedy non-adaptive algorithm to the adaptive optimum. The new approach does not rely on multi-linear extensions or random walks on optimal decision trees, which are commonly used techniques in the field. We believe that it is of independent interest and may be used to analyze other adaptive optimization problems. Finally, we also analyze the adaptive greedy algorithm, and show that guarantees an improved approximation factor of 1 - 1/√e ≈ 0.393
Better bounds on the adaptivity gap of influence maximization under full-adoption feedback
No full textIn the influence maximization (IM) problem, we are given a social network and a budget k, and we look for a set of k nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since his definition by Kempe, Kleinberg, and Tardos (2003). However, most of the work focuses on the non-adaptive version of the problem where all the k seed nodes must be selected before that the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the i-th seed can be based on the observed cascade produced by the first i-1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence.
Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only works for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by ∛n+1, where n is the number of nodes in the graph. Moreover we improve over the known upper bound for in-arborescences from 2e/(e-1)≈3.16 to 2e²/(e²-1)≈2.31. Finally, we study α-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most α, and show that the adaptivity gap is upper-bounded by √α+O(1). Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3e³/(e³-1)≈3.16.
To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
