Textual network analysis: Detecting prevailing themes and biases in international news and social media

The growing volumes of information available today provide opportunities but also challenges for social scientists. This paper presents textual network analysis—a network analysis procedure that transforms any given text into a visual map of words co‐occurring together. It aims at scholars and students who are not familiar with network analysis, showing step‐by‐step how to use this approach and highlighting its advantages and applications. It demonstrates how to identify the main themes appearing in the text as well as to detect its biases and frames. Researchers can use this procedure as a grounded content analysis to formulate theories or as a basis to test existing hypotheses. The second part of the paper presents two studies that applied textual network analysis: (a) to identify the main themes raised by elite newspapers on the “fake news” discourse and (b) to map the topics related to China on Twitter. Both examples show how textual network analysis can be relevant for communication, international relations, and political science scholars as well as for practitioners, wishing to understand the prevailing discourses and tailor their messages more effectively.     

Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

Horizons for strategic planning

In this paper we present a normative model for setting time horizons for planning. Provided that certain conditions are met, we can state that only part of the future is relevant for present strategic planning, and a study of the future beyond that time horizons is a waste of resources.Following the introduction the impact of predetermined planning horizon on planning is discussed. Next, the model is presented: the problem is defined, developed and solved. The discussion of the model is designed to incorporate—and to show its implication on—existing views and methods for setting time horizons for strategic planning. Thus, simplifying assumptions which facilitate the mathematical solution of the problem, are discussed and relaxed in order to show how realistic situations are illuminated by the model.     

Aggregation of binary evaluations for truth-functional agendas

In the problem of judgment aggregation, a panel of judges has to evaluate each proposition in a given agenda as true or false, based on their individual evaluations and subject to the constraint of logical consistency. We elaborate on the relation between this and the problem of aggregating abstract binary evaluations. For the special case of truth-functional agendas we have the following main contributions: (1) a syntactical characterization of agendas for which the analogs of Arrow’s aggregation conditions force dictatorship; (2) a complete classification of all aggregators that satisfy those conditions; (3) an analysis of the effect of weakening the Pareto condition to surjectivity. This is a sequel to the paper “Aggregation of binary evaluations.” The contents of both papers were presented, under the title “An Arrovian impossibility theorem for social truth functions,” at the Second World Congress of the Game Theory Society, Marseille, July 2004. The first version of “Aggregation of binary evaluations” was completed in June 2005. That working paper was subsequently split into two parts, of which this is the second. The comments of an anonymous referee are gratefully acknowledged. Part of R. Holzman’s work was done while he was a Fellow of the Institute for Advanced Studies at the Hebrew University of Jerusalem.     

Approximating <Emphasis Type="Italic">k</Emphasis>-generalized connectivity via collapsing HSTs

An instance of the k -generalized connectivity problem consists of an undirected graph G=(V,E), whose edges are associated with non-negative costs, and a collection \({\mathcal{D}}=\{(S_{1},T_{1}),\ldots,(S_{d},T_{d})\}\) of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph ??G connects a demand (S _i ,T _i ) when it contains a path with one endpoint in S _i and the other in T _i . Given an integer parameter k, the goal is to identify a minimum cost subgraph that connects at least k demands in \({\mathcal{D}}\).Alon, Awerbuch, Azar, Buchbinder and Naor (SODA ’04) seem to have been the first to consider the generalized connectivity paradigm as a unified machinery for incorporating multiple-choice decisions into network formation settings. Their main contribution in this context was to devise a multiplicative-update online algorithm for computing log-competitive fractional solutions, and to propose provably-good rounding procedures for important special cases. Nevertheless, approximating the generalized connectivity problem in its unconfined form, where one makes no structural assumptions about the underlying graph and collection of demands, has remained an open question up until a recent O(log?² nlog?² d) approximation due to Chekuri, Even, Gupta and Segev (SODA ’08). Unfortunately, the latter result does not extend to connecting a pre-specified number of demands. Furthermore, even the simpler case of singleton demands has been established as a challenging computational task, when Hajiaghayi and Jain (SODA ’06) related its inapproximability to that of dense k -subgraph.In this paper, we present the first non-trivial approximation algorithm for k-generalized connectivity, which is derived by synthesizing several techniques originating in probabilistic embeddings of finite metrics, network design, and randomization. Specifically, our algorithm constructs, with constant probability, a feasible subgraph whose cost is within a factor of O(n ^2/3?polylog(n,k)) of optimal. We believe that the fundamental approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.     

Mobile facility location: combinatorial filtering via weighted occupancy

An instance of the mobile facility location problem consists of a complete directed graph \(G = (V, E)\) , in which each arc \((u, v) \in E\) is associated with a numerical attribute \(\mathcal M (u,v)\) , representing the cost of moving any object from \(u\) to \(v\) . An additional ingredient of the input is a collection of servers \(S = \{ s_1, \ldots , s_k \}\) and a set of clients \(C = \{ c_1, \ldots , c_\ell \}\) , which are located at nodes of the underlying graph. With this setting in mind, a movement scheme is a function \(\psi : S \rightarrow V\) that relocates each server \(s_i\) to a new position, \(\psi ( s_i )\) . We refer to \(\mathcal M ( s_i, \psi ( s_i ) )\) as the relocation cost of \(s_i\) , and to \(\min _{i \in [k]} \mathcal M (c_j, \psi ( s_i ) )\) , the cost of assigning client \(c_j\) to the nearest final server location, as the service cost of \(c_j\) . The objective is to compute a movement scheme that minimizes the sum of relocation and service costs. In this paper, we resolve an open question posed by Demaine et al. (SODA ’07) by characterizing the approximability of mobile facility location through LP-based methods. We also develop a more efficient algorithm, which is based on a combinatorial filtering approach. The latter technique is of independent interest, as it may be applicable in other settings as well. In this context, we introduce a weighted version of the occupancy problem, for which we establish interesting tail bounds, not before demonstrating that existing bounds cannot be extended.