469 research outputs found
Polarization on Social Media
No full textSocial media and the web have provided a foundation where users can easily access diverse information from around the world. However, over the years, various factors, such as user homophily (social network structure), and algorithmic filtering (e.g., news feeds and recommendations) have narrowed the breadth of content that a user consumes. This has lead to an ever-increasing cycle where users on social media only consume content that agrees with their beliefs and hence are recommended more such content, ultimately leading to a polarized society where diverse opinions are not encouraged. This thesis provides a broad overview of polarization on social media, along with algorithmic techniques to identify polarized topics, understanding their properties over time, and finally, to reduce polarization. First, we provide methods to identify polarized topics automatically from social-media streams. Our methods are mainly based on interaction networks, i.e., networks of social media users, connected through certain types of interactions. We first show that polarized topics have a special bi-clustered structure in their retweet network and propose an algorithm to quantify the degree of polarization by using a random walk on this network. We then make use of sub-graph patterns (motifs) in the reply network of users to show that we can easily identify polarized topics using such patterns. Since our analysis does not use content, our methods are able to generalize to any topic, domain and language.
Next, we study the dynamic aspects of the process of polarization. We understand what happens to the interaction networks defined above in case of a sudden increase in interest of users on the topic. We then address the question on whether polarization on Twitter has increased over the last 8 years and find evidence to support that it does.
Finally, given these findings, we design algorithms to reduce polarization. We propose two approaches. In the first approach, we propose connecting users with opposing viewpoints in order to reduce polarization. Our method takes into account the users' interests and their current level of polarization to help them get connected to the people they feel comfortable in doing so. In the second approach, we take an information-diffusion route. We pose the problem of reducing polarization as a task of spreading information that reaches both sides of the polarized topic
The Community-search Problem and How to Plan a Successful Cocktail Party
No full textA lot of research in graph mining has been devoted in the discovery of communities. Most of the work has focused in the
scenario where communities need to be discovered with only
reference to the input graph. However, for many interesting applications one is interested in finding the community
formed by a given set of nodes. In this paper we study a
query-dependent variant of the community-detection problem, which we call the community-search problem: given a
graph G, and a set of query nodes in the graph, we seek to
find a subgraph of G that contains the query nodes and it
is densely connected.
We motivate a measure of density based on minimum degree and distance constraints, and we develop an optimum
greedy algorithm for this measure. We proceed by characterizing a class of monotone constraints and we generalize
our algorithm to compute optimum solutions satisfying any
set of monotone constraints. Finally we modify the greedy
algorithm and we present two heuristic algorithms that find
communities of size no greater than a specified upper bound.
Our experimental evaluation on real datasets demonstrates
the efficiency of the proposed algorithms and the quality of
the solutions we obtain
Explainable Classification of Brain Networks via Contrast Subgraphs
Get PDFMining human-brain networks to discover patterns that can be used to discriminate between healthy individuals and patients affected by some neurological disorder, is a fundamental task in neuro-science. Learning simple and interpretable models is as important as mere classification accuracy. In this paper we introduce a novel approach for classifying brain networks based on extracting contrast subgraphs, i.e., a set of vertices whose induced subgraphs are dense in one class of graphs and sparse in the other. We formally define the problem and present an algorithmic solution for extracting contrast subgraphs. We then apply our method to a brain-network dataset consisting of children affected by Autism Spectrum Disorder and children Typically Developed. Our analysis confirms the interestingness of the discovered patterns, which match background knowledge in the neuro-science literature. Further analysis on other classification tasks confirm the simplicity, soundness, and high explainability of our proposal, which also exhibits superior classification accuracy, to more complex state-of-the-art methods
Scalable Temporal Motif Densest Subnetwork Discovery
Get PDFFinding dense subnetworks, with density based on edges or more complex structures, such as subgraphs or k-cliques, is a fundamental algorithmic problem with many applications. While the problem has been studied extensively in static networks, much remains to be explored for temporal networks. In this work we introduce the novel problem of identifying the temporal motif densest subnetwork, i.e., the densest subnetwork with respect to temporal motifs, which are high-order patterns characterizing temporal networks. Identifying temporal motifs is an extremely challenging task, and thus, efficient methods are required. To address this challenge, we design two novel randomized approximation algorithms with rigorous probabilistic guarantees that provide high-quality solutions. We perform extensive experiments showing that our methods outperform baselines. Furthermore, our algorithms scale on networks with up to billions of temporal edges, while baselines cannot handle such large networks. We use our techniques to analyze a financial network and show that our formulation reveals important network structures, such as bursty temporal events and communities of users with similar interests.</p
Reducing Exposure to Harmful Content via Graph Rewiring (Paper Replication Code)
No full text<div>
<pre>This is the reproducibility package accompanying the following paper: <br><br>Coupette, Corinna, Stefan Neumann, and Aristides Gionis. Reducing exposure to harmful content via graph rewiring. In <em>Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</em>, pp. 323–334. 2023. <br>DOI: <a href="https://dl.acm.org/doi/abs/10.1145/3580305.3599489">10.1145/3580305.3599489</a></pre>
<p> </p>
</div>
Statistical and Probabilistic Methods in Algorithmic Data Analysis (Dagstuhl Seminar 24391)
No full textThis report documents the program and the outcomes of Dagstuhl Seminar "Statistical and Probabilistic Methods in Algorithmic Data Analysis" (24391). Modern algorithms for data analysis require the use of advanced probabilistic methods to achieve the necessary scalability and accuracy guarantees. At the same time, modern tasks of knowledge discovery from data require the use of advanced statistics to handle challenges such as the test of multiple hypotheses or dependency structure of the data points, such as in time series or graphs. Probabilistic methods are also at the core of areas of theoretical computer science such as sub-linear algorithms and average-case analysis. The application of these methods requires careful balancing of theoretical and practical considerations, to obtain efficient algorithms for data analysis. The Dagstuhl Seminar focused on statistical and probabilistic methods to develop and analyze useful, scalable algorithms for knowledge discovery from large, rich datasets. Participants from different countries, at different stages of their careers, and from both industry and academia gave talks on the topics of the seminar, usually presenting their own research, either recently published or soon-to-be. There was ample time for socializing, networking, and starting or continuing collaborations, and new results are expected to be published thanks to these collaborations
Foursquare & Flickr activities in 20 cities
No full text<p>10 millions flickr photos in 10 US & 10 European cities (photo_id, user_id, time_taken, GPS_coordinates, city, if available: associated venue id)</p>
<p>4.5 million checkins (anonymized user_id, venue id, local time, city)</p>
<p>400k venues (venue id, name, GPS_coordinates, city, category id)</p>
<p>Please cite our paper if you're using this data in your own work</p>
<p>@inproceedings{Thesis15,<br>author = {{Le Falher}, G\'{e}raud and Gionis, Aristides and Mathioudakis, Michael},<br>booktitle = {International AAAI Conference on Web and Social Media},<br>title = {{Where Is the Soho of Rome? Measures and Algorithms for Finding Similar Neighborhoods in Cities}},<br>url = {http://www.aaai.org/ocs/index.php/ICWSM/ICWSM15/paper/view/10514},<br>year = {2015}<br>}</p>
<p> </p
Replication data for: Reconciliation k-median: Clustering with non-polarized representatives
No full text# Description
These files contain the data employed in the experiments described in Bruno Ordozgoiti and Aristides Gionis. 2019. Reconciliation k-median: Clustering with Non-Polarized Representatives. In Proceedings of the 2019 World Wide Web Conference (WWW’19), May 13–17, 2019, San Francisco, CA, USA.
Twitter ID's have been anonymized.
# Contents
domain_mentions.txt: Each line contains a domain name, a user ID and the number of times this user has mentioned this domain name in a tweet.
format: domain_name user_id mention_count
domains_ideology_score.txt: Domain names and their ideology score, estimated as described in (Lahoti et al. WSDM 2018). Note: missing scores can be retrieved from supplementary data in https://doi.org/10.1093/poq/nfw006
format: domain_name ideology_score
follow_graph.txt: The Twitter follower graph. Each line contains a user id and the user id of one of its followers.
format: user_id follower_user_id
representatives.txt: US Congress representatives, each with Twitter handle and polarity score computed using Barbera's method (Barbera, 2015).
format: rep_name website_url district twitter_handle party barbera_polarity_score
user_polarity.txt: User ID's and polarity score computed using Barbera's method (Barbera, 2015).
format: user_id barbera_polarity_score</p
Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, Rome
No full textThe volume contains the proceedings of the sixth ACM International Conference on Web Search and Data Mining (WSDM 2013) held on February 4-8, 2013, in Rome, Italy. As in the previous years, WSDM has attracted an impressive number of submissions tackling the most recent technical challenges in Web search and data mining, with an ever-growing interest in their social aspects. We received a total of 387 submissions from 36 countries and regions, out of which 73 were accepted for full paper publication in the proceedings, thus reaching an acceptance rate of 18.9%. The authors of the accepted papers are from 20 countries, spanning four continents - making this a truly international forum
Collaborative Procrastination
Get PDFThe problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation (for instance, experienced by the authors while working on this paper) that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder.
In this paper we adopt the model of Kleinberg and Oren (EC'14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost.
We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of collaborative procrastination. We show that whereas a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard
- …
