COSNET
Published 7 August 2015
Yutao Zhang, Jie Tang, Zhilin Yang, Jian Pei, Philip S. Yu
Citations288
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
An efficient subgradient algorithm is developed to train the model by converting the original energy-based objective function into its dual form, and it is demonstrated that applying the integration results produced by the method can improve the accuracy of expert finding, an important task in social networks.
Abstract
More often than not, people are active in more than one social network. Identifying users from multiple heterogeneous social networks and integrating the different networks is a fundamental issue in many applications. The existing methods tackle this problem by estimating pairwise similarity between users in two networks. However, those methods suffer from potential inconsistency of matchings between multiple networks.
Keywords
Computer SciencePhysics and Astronomy
Journal of the Operational Research SocietyNetwork Flows: Theory, Algorithms, and Applications.
8,138 Citations1994David K. Smith, Ravindra K. Ahuja +2 more
In-depth, self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including descriptions of polynomial-time algorithms for these core models are presented.
What is Twitter, a social network or a news media?
6,692 Citations2010Haewoon Kwak, Changhyun Lee +2 more
This work is the first quantitative study on the entire Twittersphere and information diffusion on it and finds a non-power-law follower distribution, a short effective diameter, and low reciprocity, which all mark a deviation from known characteristics of human social networks.
ArnetMiner
2,084 Citations2008Jie Tang, Jing Zhang +4 more
The architecture and main features of the ArnetMiner system, which aims at extracting and mining academic social networks, are described and a unified modeling approach to simultaneously model topical aspects of papers, authors, and publication venues is proposed.
Proceedings of the VLDB EndowmentDistributed GraphLab
1,673 Citations2012Yucheng Low, Danny Bickson +4 more
This paper develops graph based extensions to pipelined locking and data versioning to reduce network congestion and mitigate the effect of network latency, and introduces fault tolerance to the GraphLab abstraction using the classic Chandy-Lamport snapshot algorithm.
SoRec
1,427 Citations2008Hao Ma, Haixuan Yang +2 more
A factor analysis approach based on probabilistic matrix factorization to solve the data sparsity and poor prediction accuracy problems by employing both users' social network information and rating records is proposed.
De-anonymizing Social Networks
1,321 Citations2009Arvind Narayanan, Vitaly Shmatikov
A framework for analyzing privacy and anonymity in social networks is presented and a new re-identification algorithm targeting anonymized social-network graphs is developed, showing that a third of the users who can be verified to have accounts on both Twitter and Flickr can be re-identified in the anonymous Twitter graph.
Max-Margin Markov Networks
1,251 Citations2003Ben Taskar, Carlos Guestrin +1 more
Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data, and a new theoretical bound for generalization in structured domains is provided.
Large-Scale Named Entity Disambiguation Based on Wikipedia Data
1,072 Citations2007Silviu Cucerzan
Through a process of maximizing the agreement between the contextual information extracted from Wikipedia and the context of a document, as well as the agreement among the category tags associated with the candidate entities, the implemented system shows high disambiguation accuracy on both news stories and Wikipedia articles.
Who says what to whom on twitter
952 Citations2011Shaomei Wu, Jake M. Hofman +2 more
A striking concentration of attention is found on Twitter, in that roughly 50% of URLs consumed are generated by just 20K elite users, where the media produces the most information, but celebrities are the most followed.
Wherefore art thou r3579x?
846 Citations2007Lars Bäckström, Cynthia Dwork +1 more
A family of attacks is described such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes.
Birkhäuser Boston eBooksCongruent Graphs and the Connectivity of Graphs
806 Citations1992Hassler Whitney
A Tutorial on Energy-Based Learning
793 Citations2006Yann LeCun, Sumit Chopra +3 more
The EBM approach provides a common theoretical framework for many learning models, including traditional discr iminative and generative approaches, as well as graph-transformer networks, co nditional random fields, maximum margin Markov networks, and several manifold learning methods.
Retrieval evaluation with incomplete information
733 Citations2004Chris Buckley, Ellen M. Voorhees
It is shown that current evaluation measures are not robust to substantially incomplete relevance judgments, and a new measure is introduced that is both highly correlated with existing measures when complete judgments are available and more robust to incomplete judgment sets.
A Comparison of String Metrics for Matching Names and Records
481 Citations2003W. W. Cohen and P. Ravikumar and S. Fienberg
An open-source Java toolkit of methods for matching names and records is described and results obtained from using various string distance metrics on the task of matching entity names are summarized.
IEEE Transactions on Knowledge and Data EngineeringRiMOM: A Dynamic Multistrategy Ontology Alignment Framework
425 Citations2008Juanzi Li, Jie Tang +2 more
This paper presents a dynamic multistrategy ontology alignment framework, named RiMOM, and proposes a systematic approach to quantitatively estimate the similarity characteristics for each alignment task and a strategy selection method to automatically combine the matching strategies based on two estimated factors.
Connecting users across social media sites
416 Citations2013Reza Zafarani, Huan Liu
This study formally defines the cross-media user identification problem, introduces a methodology (MOBIUS) for finding a mapping among identities of individuals across social media sites, and shows that MOBIUS is effective in identifying users across socialMedia sites.
Inferring anchor links across multiple heterogeneous social networks
370 Citations2013Xiangnan Kong, Jiawei Zhang +1 more
This paper proposes to extract heterogeneous features from multiple heterogeneous networks for anchor link prediction, including user's social, spatial, temporal and text information, and derives an effective solution, MNA (Multi-Network Anchoring), to infer anchor links w.r.t. the one-to-one constraint.
IEEE Transactions on Pattern Analysis and Machine IntelligenceMRF Energy Minimization and Beyond via Dual Decomposition
276 Citations2010N. Komodakis, Nikos Paragios +1 more
It is shown that by appropriately choosing what subproblems to use, one can design novel and very powerful MRF optimization algorithms, which are able to derive algorithms that generalize and extend state-of-the-art message-passing methods, and take full advantage of the special structure that may exist in particular MRFs.
IEEE Transactions on Knowledge and Data EngineeringA Unified Probabilistic Framework for Name Disambiguation in Digital Library
267 Citations2011Jie Tang, A.C.M. Fong +2 more
A disambiguation objective function for the name ambiguity problem is defined and a two-step parameter estimation algorithm is proposed, which significantly outperforms four baseline methods of using clustering algorithms and two other previous methods.
What's in a name?
230 Citations2013Jing Liu, Fan Zhang +4 more
The analysis shows that the alias-disambiguation solution can address a major part of the user linking problem in terms of the coverage of true pairwise decisions and that the rareness and commonness of usernames can help user linking.
Proceedings of the International AAAI Conference on Web and Social MediaConnecting Corresponding Identities across Communities
225 Citations2009Reza Zafarani, Huan Liu
The aim is to provide evidence on the existence of a mapping among identities across multiple communities, providing a method for connecting these websites.
Data Mining and Knowledge DiscoveryA game-theoretic framework to identify overlapping communities in social networks
220 Citations2010Wei Chen, Zhenming Liu +2 more
The first time the community detection problem is addressed by a game-theoretic framework that considers community formation as the result of individual agents’ rational behaviors, and the algorithm is effective in identifying overlapping communities.
eTrust
215 Citations2012Jiliang Tang, Huiji Gao +2 more
This paper proposes a framework of evolution trust, eTrust, which exploits the dynamics of user preferences in the context of online product review and performs experiments to show how the exploitation of trust evolution can help improve the performance of online applications such as rating and trust prediction.
Lecture notes in computer scienceExpert Finding in a Social Network
208 Citations2007Jing Zhang, Jie Tang +1 more
Experimental results show that the proposed propagation-based approach can outperform the baseline approach and take into consideration both person local information and network information (e.g. relationships between persons).
Lecture notes in computer scienceHow Unique and Traceable Are Usernames?
194 Citations2011Daniele Perito, Claude Castelluccia +2 more
This paper investigates the feasibility of using usernames to trace or link multiple profiles across services that belong to the same individual, and is the first time that username are considered as a source of information when profiling users on the Internet.
Proceedings of the AAAI Conference on Artificial IntelligenceMapping Users across Networks by Manifold Alignment on Hypergraph
176 Citations2014Shulong Tan, Ziyu Guan +4 more
A novel subspace learning algorithm, Manifold Alignment on Hypergraph (MAH), is proposed, which uses hypergraph to model high-order relations here and ranks all users in the other network by their possibilities of being the corresponding user.
Mining structural hole spanners through information diffusion in social networks
166 Citations2013Tiancheng Lou, Jie Tang
This work precisely defines the problem of mining top-k structural hole spanners in large-scale social networks and provides an objective (quality) function to formalize the problem and proposes an efficient algorithm with provable approximation guarantees to solve the problem.
On the performance of percolation graph matching
161 Citations2013Lyudmila Yartseva, Matthias Grossglauser
A very simple percolation - based graph matching algorithm that incrementally maps every pair of nodes (i,j) with at least r neighboring mapped pairs is proposed and analyzed, which makes possible a rigorous analysis that relies on recent advances in bootstrappercolation theory for the G(n,p) random graph.
Linking named entities in Tweets with knowledge base via user interest modeling
152 Citations2013Wei Shen, Jianyong Wang +2 more
KAURI is proposed, a graph-based framework to collectively link all the named entity mentions in all tweets posted by a user via modeling the user's topics of interest, and the experimental results show that KAURI significantly outperforms the baseline methods in terms of accuracy, and KA URI is efficient and scales well to tweet stream.
SIGMa
149 Citations2013Simon Lacoste-Julien, Konstantina Palla +4 more
Simple Greedy Matching (SiGMa), a simple algorithm for aligning knowledge bases with millions of entities and facts, which is an iterative propagation algorithm that leverages both the structural information from the relationship graph and flexible similarity measures between entity properties in a greedy local search, which makes it scalable.
Entity disambiguation with hierarchical topic models
98 Citations2011Saurabh Kataria, K. Sambath Kumar +3 more
This paper proposes a semi-supervised hierarchical model called Wikipedia-based Pachinko Allocation Model} (WPAM) that outperforms state-of-the-art baselines by as much as 16% in terms of disambiguation accuracy.
Mining evidences for named entity disambiguation
93 Citations2013Yang Li, Chi Wang +4 more
This work proposes a generative model and an incremental algorithm to automatically mine useful evidences across documents with a specific modeling of "background topic" and "unknown entities", which outperforms the state-of-the-art approaches significantly.
Active sampling for entity matching
91 Citations2012Kedar Bellare, Suresh Iyengar +2 more
The main result is an active learning algorithm that approximately maximizes recall of the classifier while respecting a precision constraint with provably sub-linear label complexity (under certain distributional assumptions).
Mathematical ProgrammingTwo “well-known” properties of subgradient optimization
81 Citations2007Kurt M. Anstreicher, Laurence A. Wolsey
Two topics are related in that convergence of the iterates is required to prove correctness of the primal construction scheme, and the construction of primal estimates when subgradient optimization is applied to maximize the Lagrangian dual of a linear program.
NeurocomputingOn optimization of expertise matching with various constraints
47 Citations2011Wenbin Tang, Jie Tang +4 more
In the proposed framework, the problem of expertise matching is linked to a convex cost flow problem, which guarantees an optimal solution under various constraints, and an online matching algorithm to support incorporating user feedbacks in real time is presented.
Efficient training for pairwise or higher order CRFs via dual decomposition
39 Citations2011Nikos Komodakis
A very general algorithmic framework for structured prediction learning that is able to efficiently handle both pairwise and higher-order discrete MRFs/CRFs1 and can be easily adapted to take advantage of any special structure of a given class of MRFs.
World Wide WebFinding email correspondents in online social networks
37 Citations2012Yi Cui, Jian Pei +4 more
This paper systematically investigates the problem of finding email correspondents in social networks accurately and develops a practical data mining approach that utilizes the similarity between email accounts and social network user profiles, and at the same time explores the similarities between the email communication network and the social network under investigation.
Two “Well-Known” Properties of Subgradient Optimization
12 Citations2006Laurence A. Wolsey, Kurt M. Anstreicher
Exploiting user clicks for automatic seed set generation for entity matching
2 Citations2013Xiao Bai, Flavio Junqueira +1 more
This paper presents an approach that leverages user clicks during Web search to automatically generate training data for entity matching, and finds that Web pages clicked for a given query are likely to be about the same entity.