Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTies That Bind - Characterizing Classes by Attributes and Social Ties
85
0
0.0
(
0
)
Added by
Bryan Perozzi
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a set of attributed subgraphs known to be from different classes, how can we discover their differences? There are many cases where collections of subgraphs may be contrasted against each other. For example, they may be assigned ground truth labels (spam/not-spam), or it may be desired to directly compare the biological networks of different species or compound networks of different chemicals. In this work we introduce the problem of characterizing the differences between attributed subgraphs that belong to different classes. We define this characterization problem as one of partitioning the attributes into as many groups as the number of classes, while maximizing the total attributed quality score of all the given subgraphs. We show that our attribute-to-class assignment problem is NP-hard and an optimal $(1 - 1/e)$-approximation algorithm exists. We also propose two different faster heuristics that are linear-time in the number of attributes and subgraphs. Unlike previous work where only attributes were taken into account for characterization, here we exploit both attributes and social ties (i.e. graph structure). Through extensive experiments, we compare our proposed algorithms, show findings that agree with human intuition on datasets from Amazon co-purchases, Congressional bill sponsorships, and DBLP co-authorships. We also show that our approach of characterizing subgraphs is better suited for sense-making than discriminating classification approaches.
rate research
Read More
Understanding the correlation between two different scores for the same set of items is a common problem in information retrieval, and the most commonly used statistics that quantifies this correlation is Kendalls $tau$. However, the standard definition fails to capture that discordances between items with high rank are more important than those between items with low rank. Recently, a new measure of correlation based on average precision has been proposed to solve this problem, but like many alternative proposals in the literature it assumes that there are no ties in the scores. This is a major deficiency in a number of contexts, and in particular while comparing centrality scores on large graphs, as the obvious baseline, indegree, has a very large number of ties in web and social graphs. We propose to extend Kendalls definition in a natural way to take into account weights in the presence of ties. We prove a number of interesting mathematical properties of our generalization and describe an $O(nlog n)$ algorithm for its computation. We also validate the usefulness of our weighted measure of correlation using experimental data.
Network structure can affect when and how widely new ideas, products, and behaviors are adopted. In widely-used models of biological contagion, interventions that randomly rewire edges (generally making them longer) accelerate spread. However, there are other models relevant to social contagion, such as those motivated by myopic best-response in games with strategic complements, in which an individuals behavior is described by a threshold number of adopting neighbors above which adoption occurs (i.e., complex contagions). Recent work has argued that highly clustered, rather than random, networks facilitate spread of these complex contagions. Here we show that minor modifications to this model, which make it more realistic, reverse this result: we allow very rare below-threshold adoption, i.e., rarely adoption occurs when there is only one adopting neighbor. To model the trade-off between long and short edges we consider networks that are the union of cycle-power-$k$ graphs and random graphs on $n$ nodes. Allowing adoptions below threshold to occur with order $1/sqrt{n}$ probability along some short cycle edges is enough to ensure that random rewiring accelerates spread. Simulations illustrate the robustness of these results to other commonly-posited models for noisy best-response behavior. Hypothetical interventions that randomly rewire existing edges or add random edges (versus adding short, triad-closing edges) in hundreds of empirical social networks reduce time to spread. This revised conclusion suggests that those wanting to increase spread should induce formation of long ties, rather than triad-closing ties. More generally, this highlights the importance of noise in game-theoretic analyses of behavior.
Increasing evidence suggests that, similar to face-to-face communications, human emotions also spread in online social media. However, the mechanisms underlying this emotion contagion, for example, whether different feelings spread in unlikely ways or how the spread of emotions relates to the social network, is rarely investigated. Indeed, because of high costs and spatio-temporal limitations, explorations of this topic are challenging using conventional questionnaires or controlled experiments. Because they are collection points for natural affective responses of massive individuals, online social media sites offer an ideal proxy for tackling this issue from the perspective of computational social science. In this paper, based on the analysis of millions of tweets in Weibo, surprisingly, we find that anger travels easily along weaker ties than joy, meaning that it can infiltrate different communities and break free of local traps because strangers share such content more often. Through a simple diffusion model, we reveal that weaker ties speed up anger by applying both propagation velocity and coverage metrics. To the best of our knowledge, this is the first time that quantitative long-term evidence has been presented that reveals a difference in the mechanism by which joy and anger are disseminated. With the extensive proliferation of weak ties in booming social media, our results imply that the contagion of anger could be profoundly strengthened to globalize its negative impact.
Due to their essential role as places for socialization, third places - social places where people casually visit and communicate with friends and neighbors - have been studied by a wide range of fields including network science, sociology, geography, urban planning, and regional studies. However, the lack of a large-scale census on third places kept researchers from systematic investigations. Here we provide a systematic nationwide investigation of third places and their social networks, by using Facebook pages. Our analysis reveals a large degree of geographic heterogeneity in the distribution of the types of third places, which is highly correlated with baseline demographics and county characteristics. Certain types of pages like Places of Worship demonstrate a large degree of clustering suggesting community preference or potential complementarities to concentration. We also found that the social networks of different types of social place differ in important ways: The social networks of Restaurants and Indoor Recreation pages are more likely to be tight-knit communities of pre-existing friendships whereas Places of Worship and Community Amenities page categories are more likely to bridge new friendship ties. We believe that this study can serve as an important milestone for future studies on the systematic comparative study of social spaces and their social relationships.
Device-to-device (D2D) communications is seen as a major technology to overcome the imminent wireless capacity crunch and to enable novel application services. In this paper, we propose a novel, social-aware approach for optimizing D2D communications by exploiting two network layers: the social network and the physical, wireless network. First we formulate the physical layer D2D network according to users encounter histories. Subsequently, we propose a novel approach, based on the so-called Indian Buffet Process, so as to model the distribution of contents in users online social networks. Given the online and offline social relations collected by the Evolved Node B, we jointly optimize the traffic offload process in D2D communication. Simulation results show that the proposed approach offload the traffic of Evolved Node B successfully.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
