1,721,022 research outputs found
Symetrický a homofilii zachovávající model šíření názorů
Get PDFWe define and study a symmetric homophily-preserving opinion diffusion model on clusters of voters. This model is symmetric, which means that clusters of voters influence each other. The model is also homophily-preserving, meaning when a voter changes their opinion, their neighborhood also changes, which is a frequently observed property of social sites. We present properties of the diffusion model, such as convergence, ϵ-convergence for some types of graphs, and polyhedral description of the set of fixed points, as well as generalizations on graphs with weighted edges and directed graphs and their properties. We provide the definition of the threshold diffusion process. We study fixed points of the diffusion and threshold diffusion process. We also provide a program for experimentation on our model. 1Definujeme a studujeme symetrický a homofilii zachovávající model šíření názorů na skupinách voličů. Tento model je symetrický, což znamená, že se skupiny voličů ovlivňují navzájem. Tento model také zachovává homofilii, tedy pokud volič změní svůj názor, tak se spolu s tím změní jeho okolí, což je často pozorovaná vlastnost sociálních sítí. Uvádíme vlastnosti našeho modelu šíření názorů, mezi které patří konvergence, ϵ-konvergence na některých typech grafů, dále také polyedrický popis množiny pevných bodů a zobecnění procesu na grafy s váženými hranami a orientované grafy společně s jejich vlastnostmi. Poskytujeme definici prahové verze našeho šíření názorů. Studujeme pevné body difuze a prahové difuze. Také poskytujeme program pro experimentování na našem modelu. 1Informatický ústav Univerzity KarlovyComputer Science Institute of Charles UniversityFaculty of Mathematics and PhysicsMatematicko-fyzikální fakult
A Symmetric Homophily-preserving Opinion Diffusion Model
No full textWe define and study a symmetric homophily-preserving opinion diffusion model on clusters of voters. This model is symmetric, which means that clusters of voters influence each other. The model is also homophily-preserving, meaning when a voter changes their opinion, their neighborhood also changes, which is a frequently observed property of social sites. We present properties of the diffusion model, such as convergence, ϵ-convergence for some types of graphs, and polyhedral description of the set of fixed points, as well as generalizations on graphs with weighted edges and directed graphs and their properties. We provide the definition of the threshold diffusion process. We study fixed points of the diffusion and threshold diffusion process. We also provide a program for experimentation on our model.
Algorithmische Aspekte der Manipulation und Anonymisierung in der Sozialwahltheorie und in sozialen Netzwerken
No full textPublished in print by Universitätsverlag der TU Berlin, ISBN 978-3-7983-2804-4 (ISSN 2199-5249)This thesis presents a study of several combinatorial problems related to social choice and social networks. The main concern is their computational complexity, with an emphasis on their parameterized complexity. The goal is to devise efficient algorithms for each of the problems studied here, or to prove that, under widely-accepted assumptions, such algorithms cannot exist.
The problems discussed in Chapter 3 and in Chapter 4 are about manipulating a given election, where some relationships between the entities of the election are assumed. This can be seen as if the election occurs on top of an underlying social network, connecting the voters participating in the election or the candidates which the voters vote on.
The problem discussed in Chapter 3, Combinatorial Candidate Control, is about manipulating an election by changing the set of candidates which the voters vote on. That is, there is an external agent who can add new candidates or delete existing candidates. A combinatorial structure over the candidates is assumed, such that whenever the external agent adds or removes a candidate, a predefined set of candidates (related to the chosen candidate) are added or removed from the election.
The problem discussed in Chapter 4, Combinatorial Shift Bribery, is also about manipulating an election. Here, however, the external agent can change the way some voters vote. Specifically, a combinatorial structure over the voters is assumed, such that the external agent can change the position of its preferred candidate in sets of voters, following some predefined patterns.
The problem discussed in Chapter 5, Election Anonymization, is also about elections. The main concern here, however, is preserving the privacy of the voters, when the votes are published, along with some additional (private) information.
The task is to transform a given election such that each vote would appear at least k times. By doing so, even an adversary which knows how some voters vote, cannot identify individual voters.
The problems discussed in Chapter 6 and in Chapter 7 are also about privacy. Specifically, a social network (modeled as a graph) is to become publicly available. The task is to anonymize the graph; that is, to transform the graph such that, for every vertex, there will be at least other vertices with the same degree. By doing so, even an adversary which knows the degrees of some vertices cannot identify individual vertices.
In the problem discussed in Chapter 6, Degree Anonymization by Vertex Addition, the way to achieve anonymity is by introducing new vertices.
In the problem discussed in Chapter 7, Degree Anonymization By Graph Contractions, the way to achieve anonymity is by contracting as few edges as possible.
The main aim of this thesis, considering the problems mentioned above, is to explore some boundaries between tractability and intractability. Specifically, as most of these problems are computationally intractable (that is, NP-hard or even hard to approximate), some restricted cases and parameterizations for these problems are considered.
The goal is to devise efficient algorithms for them, running in polynomial-time when some parameters are assumed to be constant, or, even better, to show that the problems are fixed-parameter tractable for the parameters considered.
If such algorithms cannot be devised, then the goal is to prove that these problems are indeed not fixed-parameter tractable with respect to some parameters, or, even better, to show that the problems are NP-hard even when some parameters are assumed to be constant.Diese Dissertation stellt eine Untersuchung von verschiedenen kombinatorischen Problemen im Umfeld von Wahlen und sozialen Netzwerken dar. Das Hauptziel ist die Analyse der Berechnungskomplexität mit dem Schwerpunkt auf der parametrisierten Komplexität.
Dabei werden für jedes der untersuchten Probleme effiziente Algorithmen entworfen oder aber gezeigt, dass unter weit akzeptierten Annahmen solche Algorithmen nicht existieren können.
Die Probleme, welche im Kapitel 3 und im Kapitel 4 diskutiert werden, modellieren das Manipulieren einer gegebenen Wahl, bei welcher gewisse Beziehungen zwischen den Beteiligten angenommen werden. Dies kann so interpretiert werden, dass die Wahl innerhalb eines Sozialen Netzwerks stattfindet, in dem die Wähler oder die Kandidaten miteinander in Verbindung stehen.
Das Problem Combinatorial Candidate Control ONTROL, welches in Kapitel 3 untersucht wird, handelt von der Manipulation einer Wahl durch die änderung der Kandidatenmenge über welche die Wähler abstimmen. Genauer gesagt, gibt es einen externen Agenten, welcher neue Kandidaten hinzufügen oder existierende Kandidaten entfernen kann. Es wird eine kombinatorische Struktur über der Kandidatenmenge angenommen, so dass immer wenn der externe Agent einen Kandidaten hinzufügt oder entfernt, eine vordefinierte Kandidatenmenge (welche mit den ausgewählten Kandidaten in Beziehung steht) ebenfalls hinzugefügt bzw. entfernt wird.
Das Problem Combinatorial Shift Bribery, welches in Kapitel 4 untersucht wird, thematisiert ebenfalls die Manipulation einer Wahl. Hier allerdings kann der externe Agent Änderungen des Abstimmungsverhaltens einiger Wähler herbeiführen. Dabei wird eine kombinatorische Struktur über den Wählern angenommen, so dass der externe Agent die Position des von ihm präferierten Kandidaten bei mehreren Wählern entsprechend vordefinierter Muster gleichzeitig ändern kann.
Das Problem Election Anonymization, welches in Kapitel 5 untersucht wird, befasst sich ebenso mit Wahlen. Das Hauptanliegen hier ist es jedoch, die Privatsphäre der Wähler bei der Veröffentlichung der Stimmenabgaben zusammen mit einigen zusätzlichen (privaten) Informationen aufrecht zu erhalten. Die Aufgabe ist es eine gegebene Wahl so zu verändern, dass jede Stimmenabgabe mindestens k-fach vorkommt. Dadurch kann noch nicht einmal ein Gegenspieler einzelne Wähler identifizieren, wenn er die Stimmenabgaben einiger Wähler bereits kennt.
Die in Kapitel 6 und 7 untersuchten Probleme behandeln gleichermaßen Privatsphärenaspekte. Präziser gesagt, geht es darum, dass ein soziales Netzwerk (modelliert als Graph) veröffentlicht werden soll. Die Aufgabe ist es den Graphen zu anonymisieren; dies bedeutet man verändert den Graphen, so dass es für jeden Knoten mindestens k − 1 weitere Knoten mit dem selben Grad gibt. Dadurch wird erreicht, dass selbst ein Gegenspieler, welcher die Knotengrade einiger Knoten kennt, nicht in der Lage ist einzelne Knoten zu identifizieren.
Bei dem Problem Degree Anonymization by Vertex Addition, welches in Kapitel 6 untersucht wird, wird Anonymität durch Einführung neuer Knoten erreicht. Bei dem Problem Degree Anonymization by Graph Contractions, welches in Kapitel 7 untersucht wird, wird Anonymität durch die Kontraktion von möglichst wenigen Kanten erreicht.
Das Hauptanliegen dieser Dissertation in Bezug auf die obig genannten Probleme ist es die Grenzen der effizienten Lösbarkeit auszuloten. Insbesondere da die meisten dieser Probleme berechnungsschwer (genauer NP-schwer bzw. sogar schwer zu approximieren) sind, werden einige eingeschränkte Fälle und Parametrisierungen der Probleme betrachtet. Das Ziel ist es effiziente Algorithmen für sie zu entwickeln, welche in Polynomzeit laufen, wenn einige Parameter konstante Werte aufweisen, oder besser noch zu zeigen, dass die Probleme “fixed-parameter tractable” für die betrachteten Parameter sind. Wenn solche Algorithmen nicht gefunden werden können, dann ist es das Ziel zu beweisen, dass diese Probleme tatsächlich nicht “fixed-parameter tractable” bezüglich der entsprechenden Parameter sind, oder noch besser zu zeigen, dass die Probleme NP-schwer sind, sogar wenn die entsprechenden Parameter konstante Werte aufweisen
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe 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
Get PDF“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
Get PDFWe 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
Multi-Party Campaigning
No full textWe study a social choice setting of manipulation in elections and extend the usual model in two major ways: first, instead of considering a single manipulating agent, in our setting there are several, possibly competing ones; second, instead of evaluating an election after the first manipulative action, we allow several back-and-forth rounds to take place. We show that in certain situations, such as in elections with only a few candidates, optimal strategies for each of the manipulating agents can be computed efficiently. Our algorithmic results rely on formulating the problem of finding an optimal strategy as sentences of Presburger arithmetic that are short and only involve small coefficients, which we show is fixed-parameter tractable -- indeed, one of our contributions is a general result regarding fixed-parameter tractability of Presburger arithmetic that might be useful in other settings. Following our general theorem, we design quite general algorithms; in particular, we describe how to design efficient algorithms for various settings, including settings in which we model diffusion of opinions in a social network, complex budgeting schemes available to the manipulating agents, and various realistic restrictions on adversary actions
Efficient Social Choice via NLP and Sampling
Get PDFAttention-Aware Social Choice tackles the fundamental conflict faced by some
agent communities between their desire to include all members in the decision
making processes and the limited time and attention that are at the disposal of
the community members. Here, we investigate a combination of two techniques for
attention-aware social choice, namely Natural Language Processing (NLP) and
Sampling. Essentially, we propose a system in which each governance proposal to
change the status quo is first sent to a trained NLP model that estimates the
probability that the proposal would pass if all community members directly vote
on it; then, based on such an estimation, a population sample of a certain size
is being selected and the proposal is decided upon by taking the sample
majority. We develop several concrete algorithms following the scheme described
above and evaluate them using various data, including such from several
Decentralized Autonomous Organizations (DAOs)
- …
