Node Classification in Social Networks
Published 1 January 2011Open access
Smriti Bhagat, Graham Cormode, S. Muthukrishnan
Citations359
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
When dealing with large graphs, such as those that arise in the context of online social networks, a subset of nodes may be labeled to indicate demographic values, interest, beliefs or other characteristics of the nodes (users).
Abstract
When dealing with large graphs, such as those that arise in the context of\nonline social networks, a subset of nodes may be labeled. These labels can\nindicate demographic values, interest, beliefs or other characteristics of the\nnodes (users). A core problem is to use this information to extend the labeling\nso that all nodes are assigned a label (or labels). In this chapter, we survey\nclassification techniques that have been proposed for this problem. We consider\ntwo broad categories: methods based on iterative application of traditional\nclassifiers using graph information as features, and methods which propagate\nthe existing labels via random walks. We adopt a common perspective on these\nmethods to highlight the similarities between different approaches within and\nacross the two categories. We also describe some extensions and related\ndirections to the central problem of node classification.\n
Keywords
Computer SciencePhysics and Astronomy
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
Semi-supervised learning using Gaussian fields and harmonic functions
3,377 Citations2003Xiaojin Zhu, Zoubin Ghahramani +1 more
AI MagazineCollective Classification in Network Data
3,287 Citations2008Prithviraj Sen, Galileo Namata +4 more
This article introduces four of the most widely used inference algorithms for classifying networked data and empirically compare them on both synthetic and real-world data.
IEEE Transactions on Information TheoryConstructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
1,627 Citations2005Jonathan S. Yedidia, William T. Freeman +1 more
This work explains how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms, and describes empirical results showing that GBP can significantly outperform BP.
Predicting positive and negative links in online social networks
1,454 Citations2010Jure Leskovec, Daniel P. Huttenlocher +1 more
These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, shedding light on theories of balance and status from social psychology and suggest social computing applications by which the attitude of one user toward another can be estimated from evidence provided by their relationships with other members of the surrounding social network.
Scaling personalized web search
1,205 Citations2003Glen Jeh, Jennifer Widom
The approach enables incremental computation, so that the construction of personalized views from partial vectors is practical at query time, and experimental results demonstrate the effectiveness and scalability of the techniques.
Learning influence probabilities in social networks
1,011 Citations2010Amit Goyal, Francesco Bonchi +1 more
This paper proposes models and algorithms for learning the model parameters and for testing the learned models to make predictions, and develops techniques for predicting the time by which a user may be expected to perform an action.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Learning from Labeled and Unlabeled Data using Graph Mincuts
947 Citations2018Avrim Blum, Shuchi Chawla
An algorithm based on finding minimum cuts in graphs, that uses pairwise relationships among the examples in order to learn from both labeled and unlabeled data is considered.
Proceedings of the VLDB EndowmentGraph clustering based on structural/attribute similarities
882 Citations2009Yang Zhou, Hong Cheng +1 more
This paper proposes a novel graph clustering algorithm, SA-Cluster, based on both structural and attribute similarities through a unified distance measure, which partitions a large graph associated with attributes into k clusters so that each cluster contains a densely connected subgraph with homogeneous attribute values.
Enhanced hypertext categorization using hyperlinks
775 Citations1998Soumen Chakrabarti, Byron Dom +1 more
This work has developed a text classifier that misclassified only 13% of the documents in the well-known Reuters benchmark; this was comparable to the best results ever obtained and its technique also adapts gracefully to the fraction of neighboring documents having known topics.
Spectral partitioning of random graphs
615 Citations2001Frank McSherry
This paper shows that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density.
Partially labeled classification with Markov random walks
563 Citations2001Martin Szummer, Tommi Jaakkola
This work combines a limited number of labeled examples with a Markov random walk representation over the unlabeled examples and develops and compares several estimation criteria/algorithms suited to this representation.
Journal of Machine Learning ResearchClassification in Networked Data: A Toolkit and a Univariate Case Study
447 Citations2007Sofus A. Macskassy, Foster Provost
The results demonstrate that very simple network-classification models perform quite well---well enough that they should be used regularly as baseline classifiers for studies of learning with networked data.
Video suggestion and discovery for youtube
444 Citations2008Shumeet Baluja, Rohan Seth +6 more
A novel method based upon the analysis of the entire user-video graph to provide personalized video suggestions for users, termed Adsorption, provides a simple method to efficiently propagate preference information through a variety of graphs.
Iterative Classification in Relational Data
306 Citations2000Jennifer Neville, David Jensen
An iterative classification approach that uses simple Bayesian classifiers in an iterative fashion, dynamically upd ating the attributes of some objects as inferences are made about related ob jects.
The MIT Press eBooksLabel Propagation and Quadratic Criterion
281 Citations2006Yoshua Bengio, Olivier Delalleau +1 more
A Simple Relational Classifier
246 Citations2003Sofus A. Macskassy, Foster Provost
It is argued that a simple relational predictive model the predicts only based on class labels of related neighbors, using no learning and no inherent attributes should be used as a baseline to assess the performance of relational learners.
Probabilistic classification and clustering in relational data
230 Citations2001Ben Taskar, Eran Segal +1 more
This work proposes a general class of models for classification and clustering in relational domains that capture probabilistic dependencies between related instances, and shows how to learn such models efficiently from data.
Theory of Computing SystemsFirst- and Second-Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing
141 Citations1998S. Muthukrishnan
This paper introduces a new direction in diffusive schedules by considering schedules that are modeled as w1=Mw0;wt+1=β Mwt + (1-β)wt-1 for some appropriate β; these are the second-order schedules.
arXiv (Cornell University)Discriminative Probabilistic Models for Relational Data
125 Citations2012Ben Taskar, Pieter Abbeel +1 more
Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields
124 Citations2003Jon Kleinberg, Éva Tardos
This work provides the first non-trivial polynomial-time approximation algorithms for a general family of classification problems of this type, the metric labeling problem, and shows that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields.
Dissimilarity in Graph-Based Semi-Supervised Classification
93 Citations2007Andrew B. Goldberg, Xiaojin Zhu +1 more
A semi-supervised classification algorithm that learns from dissimilarity and similarity information on labeled and unlabeled data that results in a convex problem, and can handle both binary and multiclass classification.
The rendezvous algorithm
90 Citations2007Arik Azran
A new approach for estimating a distribution over the missing labels where data points are viewed as nodes of a graph, and pairwise similarities are used to derive a transition probability matrix P for a Markov random walk between them.
Estimating PageRank on graph streams
76 Citations2008Atish Das Sarma, Sreenivas Gollapudi +1 more
In the streaming model, this study shows how to perform several graph computations including estimating the probability distribution after a random walk of length l, mixing time, and the conductance, and the relation between mixing time and conductance gives an estimate for the conductance of the graph.
Applying link-based classification to label blogs
45 Citations2007Smriti Bhagat, Irina Rozenbaum +1 more
This work focuses on multigraphs induced by blog data, and carefully applies general algorithms to specifically infer labels such as age, gender and location associated with the blog based only on the link-structure amongst them.
ACM SIGACT NewsTheory research at Google
11 Citations2008Gagan Aggarwal, Nir Ailon +10 more
The problems of research interest to theoretical computer scientists that arise, in particular at Google, are focused on the emergence of web search and associated technologies.
Lecture notes in computer scienceSecond-Order Methods for Distributed Approximate Single- and Multicommodity Flow
7 Citations1998S. Muthukrishnan, Torsten Suel
This work proposes a second-order method for accelerating the convergence of the "first-order" distributed algorithms recently proposed by Awerbuch and Leighton and gives valuable insights into the diffusive processes that underly these local-control algorithms.