Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSampling Online Social Networks by Random Walk with Indirect Jumps
100
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Random walk-based sampling methods are gaining popularity and importance in characterizing large networks. While powerful, they suffer from the slow mixing problem when the graph is loosely connected, which results in poor estimation accuracy. Random walk with jumps (RWwJ) can address the slow mixing problem but it is inapplicable if the graph does not support uniform vertex sampling (UNI). In this work, we develop methods that can efficiently sample a graph without the necessity of UNI but still enjoy the similar benefits as RWwJ. We observe that many graphs under study, called target graphs, do not exist in isolation. In many situations, a target graph is related to an auxiliary graph and a bipartite graph, and they together form a better connected {em two-layered network structure}. This new viewpoint brings extra benefits to graph sampling: if directly sampling a target graph is difficult, we can sample it indirectly with the assistance of the other two graphs. We propose a series of new graph sampling techniques by exploiting such a two-layered network structure to estimate target graph characteristics. Experiments conducted on both synthetic and real-world networks demonstrate the effectiveness and usefulness of these new techniques.
rate research
Read More
In this paper, we introduce a novel, general purpose, technique for faster sampling of nodes over an online social network. Specifically, unlike traditional random walk which wait for the convergence of sampling distribution to a predetermined target distribution - a waiting process that incurs a high query cost - we develop WALK-ESTIMATE, which starts with a much shorter random walk, and then proactively estimate the sampling probability for the node taken before using acceptance-rejection sampling to adjust the sampling probability to the predetermined target distribution. We present a novel backward random walk technique which provides provably unbiased estimations for the sampling probability, and demonstrate the superiority of WALK-ESTIMATE over traditional random walks through theoretical analysis and extensive experiments over real world online social networks.
Instant quality feedback in the form of online peer ratings is a prominent feature of modern massive online social networks (MOSNs). It allows network members to indicate their appreciation of a post, comment, photograph, etc. Some MOSNs support both positive and negative (signed) ratings. In this study, we rated 11 thousand MOSN member profiles and collected user responses to the ratings. MOSN users are very sensitive to peer ratings: 33% of the subjects visited the researchers profile in response to rating, 21% also rated the researchers profile picture, and 5% left a text comment. The grades left by the subjects are highly polarized: out of the six available grades, the most negative and the most positive are also the most popular. The grades fall into three almost equally sized categories: reciprocal, generous, and stingy. We proposed quantitative measures for generosity, reciprocity, and benevolence, and analyzed them with respect to the subjects demographics.
In the past decade, blogging web sites have become more sophisticated and influential than ever. Much of this sophistication and influence follows from their network organization. Blogging social networks (BSNs) allow individual bloggers to form contact lists, subscribe to other blogs, comment on blog posts, declare interests, and participate in collective blogs. Thus, a BSN is a bimodal venue, where users can engage in publishing (post) as well as in social (make friends) activities. In this paper, we study the co-evolution of both activities. We observed a significant positive correlation between blogging and socializing. In addition, we identified a number of user archetypes that correspond to mainly bloggers, mainly socializers, etc. We analyzed a BSN at the level of individual posts and changes in contact lists and at the level of trajectories in the friendship-publishing space. Both approaches produced consistent results: the majority of BSN users are passive readers; publishing is the dominant active behavior in a BSN; and social activities complement blogging, rather than compete with it.
We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. These characterizations directly yield polynomial time algorithms that allow us to determine whether a given social network satisfies one of the above properties. We also study algorithmic questions for networks without unique outcomes. We show that the problem of determining whether a final network exists in which all nodes adopted some product is NP-complete. In turn, the problems of determining whether a given node adopts some (respectively, a given) product in some (respectively, all) network(s) are either co-NP complete or can be solved in polynomial time. Further, we show that the problem of computing the minimum possible spread of a product is NP-hard to approximate with an approximation ratio better than $Omega(n)$, in contrast to the maximum spread, which is efficiently computable. Finally, we clarify that some of the above problems can be solved in polynomial time when there are only two products.
Given a large population, it is an intensive task to gather individual preferences over a set of alternatives and arrive at an aggregate or collective preference of the population. We show that social network underlying the population can be harnessed to accomplish this task effectively, by sampling preferences of a small subset of representative nodes. We first develop a Facebook app to create a dataset consisting of preferences of nodes and the underlying social network, using which, we develop models that capture how preferences are distributed among nodes in a typical social network. We hence propose an appropriate objective function for the problem of selecting best representative nodes. We devise two algorithms, namely, Greedy-min which provides a performance guarantee for a wide class of popular voting rules, and Greedy-sum which exhibits excellent performance in practice. We compare the performance of these proposed algorithms against random-polling and popular centrality measures, and provide a detailed analysis of the obtained results. Our analysis suggests that selecting representatives using social network information is advantageous for aggregating preferences related to personal topics (e.g., lifestyle), while random polling with a reasonable sample size is good enough for aggregating preferences related to social topics (e.g., government policies).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
