WIXLIB

SOCIAL NETWORK DATA ANALYTICS

SOCIAL NETWORK DATA ANALYTICSEdited byCHARU C. AGGARWALIBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USAKluwer Academic PublishersBoston/Dordrecht/London

ContentsPreface1An Introduction to Social Network Data AnalyticsCharu C. Aggarwal1.Introduction2.Online Social Networks: Research Issues3.Research Topics in Social Networks4.Conclusions and Future DirectionsReferences2Statistical Properties ofSocial NetworksMary McGlohon, Leman Akoglu and Christos Faloutsos1.Preliminaries1.1Definitions1.2Data description2.Static Properties2.1Static Unweighted Graphs2.2Static Weighted Graphs3.Dynamic Properties3.1Dynamic Unweighted Graphs3.2Dynamic Weighted Graphs4.ConclusionReferences3Random Walks in Social Networks and their Applications: A SurveyPurnamrita Sarkar and Andrew W. Moore1.Introduction2.Random Walks on Graphs: Background2.1Random Walk based Proximity Measures2.2Other Graph-based Proximity Measures2.3Graph-theoretic Measures for Semi-supervised Learning2.4Clustering with random walk based measures3.Related Work: Algorithms3.1Algorithms for Hitting and Commute Times3.2Algorithms for Computing Personalized Pagerank and 6525356575860

viSOCIAL NETWORK DATA ANALYTICS3.3Algorithms for Computing Harmonic FunctionsRelated Work: Applications4.1Application in Computer Vision4.2Text Analysis4.3Collaborative Filtering4.4Combating Webspam5.Related Work: Evaluation and datasets5.1Evaluation: Link Prediction5.2Publicly Available Data Sources6.Conclusion and Future WorkReferences4.4Community Discovery in SocialNetworks: Applications, Methodsand Emerging TrendsS. Parthasarathy, Y. Ruan and V. Satuluri1.Introduction2.Communities in Context3.Core Methods3.1Quality Functions3.2The Kernighan-Lin(KL) algorithm3.3Agglomerative/Divisive Algorithms3.4Spectral Algorithms3.5Multi-level Graph Partitioning3.6Markov Clustering3.7Other Approaches4.Emerging Fields and Problems4.1Community Discovery in Dynamic Networks4.2Community Discovery in Heterogeneous Networks4.3Community Discovery in Directed Networks4.4Coupling Content and Relationship Information for Community Discovery5.Crosscutting Issues and Concluding RemarksReferences5Node Classification in Social NetworksSmriti Bhagat, Graham Cormode and S. Muthukrishnan1.Introduction2.Problem Formulation2.1Representing data as a graph2.2The Node Classification Problem3.Methods using Local Classifiers3.1Iterative Classification Method4.Random Walk based Methods4.1Label Propagation4.2Graph Regularization4.3Adsorption5.Applying Node Classification to Large Social Networks5.1Basic Approaches5.2Second-order Methods5.3Implementation within 2134136137137138

46Related approaches6.1Inference using Graphical Models6.2Metric labeling6.3Spectral Partitioning6.4Graph Clustering7.Variations on Node Classification7.1Dissimilarity in Labels7.2Edge Labeling7.3Label Summarization8.Concluding Remarks8.1Future Directions and Challenges8.2Further ReadingReferences6Evolution in Social Networks: A SurveyMyra Spiliopoulou1.Introduction2.Framework2.1Modeling a Network across the Time Axis2.2Evolution across Four Dimensions3.Challenges of Social Network Streams4.Incremental Mining for Community Tracing5.Tracing Smoothly Evolving Communities5.1Temporal Smoothness for Clusters5.2Dynamic Probabilistic Models6.Laws of Evolution in Social Networks7.ConclusionReferences7A Survey of Models and Algorithms for Social Influence AnalysisJimeng Sun and Jie Tang1.Introduction2.Influence Related Statistics2.1Edge Measures2.2Node Measures3.Social Similarity and Influence3.1Homophily3.2Existential Test for Social Influence3.3Influence and Actions3.4Influence and Interaction4.Influence Maximization in Viral Marketing4.1Influence Maximization4.2Other Applications5.ConclusionReferences8A Survey of Algorithms and Systems for Expert Location in Social NetworksTheodoros Lappas, Kun Liu and Evimaria 209215216

viiiSOCIAL NETWORK DATA ANALYTICS2.3.Definitions and NotationExpert Location without Graph Constraints3.1Language Models for Document Information Retrieval3.2Language Models for Expert Location3.3Further Reading4.Expert Location with Score Propagation4.1The PageRank Algorithm4.2HITS Algorithm4.3Expert Score Propagation4.4Further Reading5.Expert Team Formation5.1Metrics5.2Forming Teams of Experts5.3Further Reading6.Other Related Approaches6.1Agent-based Approach6.2Influence Maximization7.Expert Location Systems8.ConclusionsReferences9A Survey of Link Predictionin Social NetworksMohammad Al Hasan and Mohammed J. Zaki1.Introduction2.Background3.Feature based Link Prediction3.1Feature Set Construction3.2Classification Models4.Bayesian Probabilistic Models4.1Link Prediction by Local Probabilistic Models4.2Network Evolution based Probabilistic Model4.3Hierarchical Probabilistic Model5.Probabilistic Relational Models5.1Relational Bayesian Network5.2Relational Markov Network6.Linear Algebraic Methods7.Recent development and Future WorksReferences10Privacy in Social Networks: A SurveyElena Zheleva and Lise Getoor1.Introduction2.Privacy breaches in social networks2.1Identity disclosure2.2Attribute disclosure2.3Social link disclosure2.4Affiliation link disclosure3.Privacy definitions for publishing data3.1k 264266266267269270277277280281282283284286288

Contents3.2l-diversity and t-closeness3.3Differential privacy4.Privacy-preserving mechanisms4.1Privacy mechanisms for social networks4.2Privacy mechanisms for affiliation networks4.3Privacy mechanisms for social and affiliation networks5.Related literature6.ConclusionReferences11Visualizing Social NetworksCarlos D. Correa and Kwan-Liu Ma1.Introduction2.A Taxonomy of Visualizations2.1Structural Visualization2.2Semantic and Temporal Visualization2.3Statistical Visualization3.The Convergence of Visualization, Interaction and Analytics3.1Structural and Semantic Filtering with Ontologies3.2Centrality-based Visual Discovery and Exploration4.SummaryReferences12Data Mining in Social MediaGeoffrey Barbier and Huan Liu1.Introduction2.Data Mining in a Nutshell3.Social Media4.Motivations for Data Mining in Social Media5.Data Mining Methods for Social Media5.1Data Representation5.2Data Mining - A Process5.3Social Networking Sites: Illustrative Examples5.4The Blogosphere: Illustrative Examples6.Related Efforts6.1Ethnography and Netnography6.2Event Maps7.ConclusionsReferences13Text Mining in Social NetworksCharu C. Aggarwal and Haixun Wang1.Introduction2.Keyword Search2.1Query Semantics and Answer Ranking2.2Keyword search over XML and relational data2.3Keyword search over graph data3.Classification 40344344345345347353354356357358360366

xSOCIAL NETWORK DATA ANALYTICS4.Clustering Algorithms5.Transfer Learning in Heterogeneous Networks6.Conclusions and SummaryReferences14Integrating Sensors and Social NetworksCharu C. Aggarwal and Tarek Abdelzaher1.Introduction2.Sensors and Social Networks: Technological Enablers3.Dynamic Modeling of Social Networks4.System Design and Architectural Challenges4.1Privacy-preserving data collection4.2Generalized Model Construction4.3Real-time Decision Services4.4Recruitment Issues4.5Other Architectural Challenges5.Database Representation: Issues and Challenges6.Privacy Issues7.Sensors and Social Networks: Applications7.1The Google Latitude Application7.2The Citysense and Macrosense Applications7.3Green GPS7.4Microsoft SensorMap7.5Animal and Object Tracking Applications7.6Participatory Sensing for Real-Time Services8.Future Challenges and Research Multimedia Information Networksin Social MediaLiangliang Cao, GuoJun Qi, Shen-Fu Tsai, Min-Hsuan Tsai, Andrey Del Pozo, ThomasS. Huang, Xuemei Zhang and Suk Hwan Lim1.Introduction4142.Links from Semantics: Ontology-based Learning4153.Links from Community Media4163.1Retrieval Systems for Community Media4173.2Recommendation Systems for Community Media4184.Network of Personal Photo Albums4204.1Actor-Centric Nature of Personal Collections4204.2Quality Issues in Personal Collections4214.3Time and Location Themes in Personal Collections4224.4Content Overlap in Personal Collections4225.Network of Geographical Information4235.1Semantic Annotation4255.2Geographical Estimation4255.3Other Applications4266.Inference Methods4276.1Discriminative vs. Generative Models4276.2Graph-based Inference: Ranking, Clustering and Semi-supervisedLearning428

Contents6.3Online LearningDiscussion of Data Sets and Industrial SystemsDiscussion of Future Directions8.1Content-based Recommendation and Advertisements8.2Multimedia Information Networks via Cloud ComputingReferences7.8.16An Overview of Social Taggingand ApplicationsManish Gupta, Rui Li, Zhijun Yin and Jiawei Han1.Introduction1.1Problems with Metadata Generation and Fixed Taxonomies1.2Folksonomies as a Solution1.3Outline2.Tags: Why and What?2.1Different User Tagging Motivations2.2Kinds of Tags2.3Categorizers Versus Describers2.4Linguistic Classification of Tags2.5Game-based Tagging3.Tag Generation Models3.1Polya Urn Generation Model3.2Language Model3.3Other Influence Factors4.Tagging System Design5.Tag analysis5.1Tagging Distributions5.2Identifying Tag Semantics5.3Tags Versus Keywords6.Visualization of Tags6.1Tag Clouds for Browsing/Search6.2Tag Selection for Tag Clouds6.3Tag Hierarchy Generation6.4Tag Clouds Display Format6.5Tag Evolution Visualization6.6Popular Tag Cloud Demos7.Tag Recommendations7.1Using Tag Quality7.2Using Tag Co-occurrences7.3Using Mutual Information between Words, Documents andTags7.4Using Object Features8.Applications of Tags8.1Indexing8.2Search8.3Taxonomy Generation8.4Public Library Cataloging8.5Clustering and Classification8.6Social Interesting Discovery8.7Enhanced 81482483484485

SOCIAL NETWORK DATA ANALYTICS. 3.3 Algorithms for Computing Harmonic Functions 63 4. Related Work: Applications 63 4.1 Application in Computer Vision 64 4.2 Text Analysis 64 4.3 Collaborative Filtering 65 4.4 Combating Webspam 66 5. Related Work: Evaluation and datasets 66 5.1 Evaluation: Link Prediction 66 5