Francesco Bonchi
Carlos Castillo
Aristides Gionis
Alejandro Jaimes
Skip Abstract Section
Abstract
Social network analysis has gained significant attention in recent years, largely due to the success of online social networking and media-sharing sites, and the consequent availability of a wealth of social network data. In spite of the growing interest, however, there is little understanding of the potential business applications of mining social networks. While there is a large body of research on different problems and methods for social network mining, there is a gap between the techniques developed by the research community and their deployment in real-world applications. Therefore the potential business impact of these techniques is still largely unexplored.
In this article we use a business process classification framework to put the research topics in a business context and provide an overview of what we consider key problems and techniques in social network analysis and mining from the perspective of business applications. In particular, we discuss data acquisition and preparation, trust, expertise, community structure, network dynamics, and information propagation. In each case we present a brief overview of the problem, describe state-of-the art approaches, discuss business application examples, and map each of the topics to a business process classification framework. In addition, we provide insights on prospective business applications, challenges, and future research directions. The main contribution of this article is to provide a state-of-the-art overview of current techniques while providing a critical perspective on business applications of social network analysis and mining.
- Abrol, M., Mahadevan, U., McCracken, K., Mukherjee, R., and Raghavan, P. 2002. Social networks for enterprise webs. In Proceedings of the International World Wide Web Conference (WWW'02).Google Scholar
- Adar, E. and Adamic, L. A. 2005. Tracking information epidemics in blogspace. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence (WI'05). Google ScholarDigital Library
- Agarwal, G. and Kempe, D. 2008. Modularity-Maximizing network communities via mathematical programming. Euro. Phys. J. B 66, 3.Google Scholar
- Agarwal, N., Liu, H., Tang, L., and Yu, P. S. 2008. Identifying the influential bloggers in a community. In Proceedings of the 1<sup>st</sup>International Conference on Web Search and Web Data Mining, (WSDM'08). Google ScholarDigital Library
- Aggarwal, C. C. and Yu, P. S. 2005. Online analysis of community evolution in data streams. In Proceedings of the SIAM International Data Mining Conference (SDM'05).Google Scholar
- Aggarwal, G., Mishra, N., and Pinkas, B. 2004. Secure computation of the kth-ranked element. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT).Google Scholar
- Agrawal, R. and Srikant, R. 2000a. Privacy-Preserving data mining. In Proceedings of the ACM-SIGMOD International Conference on Management of Data (SIGMOD). 439--450. Google ScholarDigital Library
- Agrawal, R. and Srikant, R. 2000b. Privacy-Preserving data mining. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Google ScholarDigital Library
- Ahn, H.-K., Cheng, S.-W., Cheong, O., Golin, M. J., and van Oostrum, R. 2001. Competitive facility location along a highway. In Proceedings of the 7th Annual International Conference on Computing and Combinatorics, (COCOON'01). Google ScholarDigital Library
- Ahuja, R. K., Magnanti, Thomas L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ. Google ScholarDigital Library
- Amatriain, X., Jaimes, A., Oliver, N., and Pujol, J. M. 2010. Data Mining Methods for Recommender Systems. Springer, Chapter 2, 39--100.Google Scholar
- Anagnostopoulos, A., Kumar, R., and Mahdian, M. 2008. Influence and correlation in social networks. In Proceedings of the 14<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'08). Google ScholarDigital Library
- Aral, S. 2010. Identifying social influence: A comment on opinion leadership and social contagion in new product diffusion. SSRN eLibrary.Google Scholar
- Aral, S., Brynjolfsson, E., and Van Alstyne, M. W. 2006. Information, technology and information worker productivity. SSRN eLibrary.Google Scholar
- Aral, S., Brynjolfsson, E., and Van Alstyne, M. W. 2007. Productivity effects of information diffusion in networks. SSRN eLibrary.Google Scholar
- Aral, S., Muchnik, L., and Sundararajan, A. 2009. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proc. Nat. Acad. Sci. 106, 51, 21544--21549.Google ScholarCross Ref
- Aral, S. and Van Alstyne, M. W. 2010. Networks, information and brokerage: The diversity-bandwidth tradeoff. SSRN eLibrary.Google Scholar
- Aral, S. and Walker, D. 2010. Creating social contagion through viral product design: A Randomized trial of peer influence in networks. SSRN eLibrary.Google Scholar
- Arthur, D., Motwani, R., Sharma, A., and Xu, Y. 2009. Pricing strategies for viral marketing on social networks. In Proceedings of the 5<sup>th</sup>International Workshop on Internet and Network Economics (WINE'09). 101--112. Google ScholarDigital Library
- Arthur, W. B. 1989. Competing technologies, increasing returns, and lock-in by historical events. Econ. J. 99, 394.Google ScholarCross Ref
- Backstrom, L., Dwork, C., and Kleinberg, J. M. 2007. Wherefore art thou r3579x&quest;: Anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the International World Wide Web Conference (WWW'07). 181--190. Google ScholarDigital Library
- Backstrom, L., Huttenlocher, D. P., Kleinberg, J. M., and Lan, X. 2006. Group formation in large social networks: Membership, growth, and evolution. In Proceedings of the 12<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'06). Google ScholarDigital Library
- Bakshy, E., Karrer, B., and Adamic, L. A. 2009. Social influence and the diffusion of user-created content. In Proceedings 10<sup>th</sup>ACM Conference on Electronic Commerce (EC'09). Google ScholarDigital Library
- Balog, K., Azzopardi, L., and De Rijke, M. 2006. Formal models for expert finding in enterprise corpora. In Proceedings of the 29<sup>th</sup>Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM Press, New York, 43--50. Google ScholarDigital Library
- Balog, K. and De Rijke, M. 2007. Determining expert profiles (with an application to expert finding). In Proceedings of the 20<sup>th</sup>International Joint Conference on Artifical Intelligence. Morgan Kaufmann, San Francisco, CA, 2657--2662. Google ScholarDigital Library
- Barabasi, A. L. and Albert, R. 1999. Emergence of scaling in random networks. Sci. 286, 5439, 509--512.Google Scholar
- Bass, F. 1969. A new product growth model for consumer durables. Manag. Sci. 15, 215--227.Google ScholarDigital Library
- Berlingerio, M., Bonchi, F., Bringmann, B., and Gionis, A. 2009. Mining graph evolution rules. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD'09). Lecture Notes in Computer Science, vol. 5781. Springer, 115--130.Google Scholar
- Bharathi, S., Kempe, D., and Salek, M. 2007. Competitive influence maximization in social networks. In Proceedings of the 3<sup>rd</sup>International Workshop on Internet and Network Economics (WINE'07). Google ScholarDigital Library
- Blum, A., Dwork, C., McSherry, F., and Nissim, K. 2005. Practical privacy: The SuLQ framework. In Proceedings of the ACM-SIGMOD Symposium on Principles of Database Systems (PODS). 128--138. Google ScholarDigital Library
- Bollobas, B. 1998. Modern Graph Theory. Springer.Google Scholar
- Bonchi, F., Gionis, A., and Tassa, T. 2011. Identity obfuscation in graphs through the information theoretic lens. In Proceedings of the International Conference on Data Engineering (ICDE'11). Google ScholarDigital Library
- Borgwardt, K. M., Kriegel, H.-P., and Wackersreuther, P. 2006. Pattern mining in frequent dynamic subgraphs. In Proceedings of the IEEE International Conference on Data Mining. 818--822. Google ScholarDigital Library
- Boykin, O. P. and Roychowdhury, V. 2004. Personal Email networks: An effective anti-spam tool. Condensed Matter cond-mat/0402143.Google Scholar
- Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. 2008. On modularity clustering. IEEE Trans. Knowl. Data Engin. 20, 2, 172--188. Google ScholarDigital Library
- Campan, A. and Truta, T. 2008. A clustering approach for data and structural anonymity in social networks. In Proceedings of the International Workshop on Privacy, Security and Trust in KDD (PinKDD'08).Google Scholar
- Campbell, C. S., Maglio, P. P., Cozzi, A., and Dom, B. 2003. Expertise identification using email communications. In Proceedings of the 12<sup>th</sup>International Conference on Information and Knowledge Management (CIKM'03). ACM, New York, 528--531. Google ScholarDigital Library
- Carnes, T., Nagarajan, C., Wild, S. M., and van Zuylen, A. 2007. Maximizing influence in a competitive social network: A follower's perspective. In Proceedings of the 9th International Conference on Electronic Commerce (ICEC'07). Google ScholarDigital Library
- Caverlee, J., Liu, L., and Webb, S. 2008. Socialtrust: Tamper-Resilient trust establishment in online communities. In Proceedings of the Joint Conference on Digital Libraries (JCDL). 104--114. Google ScholarDigital Library
- Cha, M., Haddadi, H., Benevenuto, F., and Gummadi, K. P. 2010. Measuring user influence in twitter: The million follower fallacy. In Proceedings of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM).Google Scholar
- Cha, M., Mislove, A., and Gummadi, P. K. 2009. A measurement-driven analysis of information propagation in the flickr social network. In Proceedings of the 18th International Conference on World Wide Web (WWW'09). Google ScholarDigital Library
- Chellappa, R. and Jain, A. 1993. Markov Random Fields: Theory and Application. Academic Press, Boston, MA.Google Scholar
- Chen, W., Wang, Y., and Yang, S. 2009. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'09). Google ScholarDigital Library
- Cheong, O., Har-Peled, S., Linial, N., and Matousek, J. 2004. The one-round voronoi game. Discr. Comput. Geom. 31, 1, 125--138.Google ScholarDigital Library
- Chickering, D. M. and Heckerman, D. 2000. A decision theoretic approach to targeted advertising. In Proceedings of the 16th Conference in Uncertainty in Artificial Intelligence (UAI'00). Google ScholarDigital Library
- Chung, F. R. K. 1997. Spectral Graph Theory. American Mathematical Society.Google Scholar
- Clauset, A., Moore, C., and Newman, M. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453, 98--101.Google ScholarCross Ref
- Clauset, A., Newman, M. E. J., and Moore, C. 2004. Finding community structure in very large networks. Phys. Rev. E, 1--6.Google ScholarCross Ref
- Clifford, P. and Sudbury, A. 1973. A model for spatial conflict. Biometrika 60, 3, 581--588.Google ScholarCross Ref
- Coleman, J., Menzel, H., and Katz, E. 1966. Medical Innovations: A Diffusion Study. Bobbs Merrill.Google Scholar
- Cortes, C., Pregibon, D., and Volinsky, C. 2001. Communities of interest. In Proceedings of the 4th International Conference on Advances in Intelligent Data Analysis (IDA'01). Springer, 105--114. Google ScholarDigital Library
- Coull, S. E., Monrose, F., Reiter, M. K., and Bailey, M. D. 2009. The challenges of effectively anonymizing network data. In Proceedings of the Cybersecurity Applications and Technology Conference For Homeland Security (CATCH '09). 230--236. Google ScholarDigital Library
- Crandall, D. J., Cosley, D., Huttenlocher, D. P., Kleinberg, J. M., and Suri, S. 2008. Feedback effects between similarity and social influence in online communities. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'08). Google ScholarDigital Library
- Craswell, N., de Vries, A. P., and Soboroff, I., Eds. 2005. The 14<sup>th</sup> Text Retrieval Conference, TREC 2005. Information Technology Laboratory's NIST Special Publications, vol. 500-266. NIST.Google Scholar
- Craswell, N., Hawking, D., marie Vercoustre, A., and Wilkins, P. 2001. P&commat;noptic expert: Searching for experts not just for documents. In Proceedings of the AusWeb Conference.Google Scholar
- Dalenius, T. 1977. Towards a methodology for statistical disclosure control. Statistik Tidskrift 15, 429--444.Google Scholar
- Dasgupta, K., Singh, R., Viswanathan, B., Chakraborty, D., Mukherjea, S., Nanavati, A. A., and Joshi, A. 2008. Social ties and their relevance to churn in mobile telecom networks. In Proceedings of the 11th International Conference on Extending Database Technology. ACM, New York, 668--677. Google ScholarDigital Library
- David, P. A. 1975. Technical Choice, Innovation and Economic Growth. Cambridge University Press.Google Scholar
- Davitz, J., Yu, J., Basu, S., Gutelius, D., and Harris, A. 2007. ilink: Search and routing in social networks. In Proceedings of the 13<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 931--940. Google ScholarDigital Library
- Degenne, A. and Forse, M. 1999. Introducing Social Networks. Sage Publications.Google Scholar
- Demailly, C. and Silman, M. 2008. At&amp;t white paper: The business impacts of social networking. White paper. http://www.business.att.com/content/whitepaper/WP-soc_17172_v3_11-10-08.pdf.Google Scholar
- Deng, H., King, I., and Lyu, M. R. 2008. Formal models for expert finding on dblp bibliography data. In Proceedings of the IEEE International Conference on Data Mining. 163--172. Google ScholarDigital Library
- Desikan, P. and Srivastava, J. 2004. Mining temporally changing web usage graphs. In Proceedings of the International Workshop on Mining Web Data for Discovering Usage Patterns and Profiles (WebKDD'04). 1--17. Google ScholarDigital Library
- Detica. 2006. Detecting telecoms subscription fraud. Tech. rep., Detica Information Intelligence.Google Scholar
- Domingos, P. and Richardson, M. 2001. Mining the network value of customers. In Proceedings of the 7<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'01). Google ScholarDigital Library
- Domingos, P. and Richardson, M. 2004. Markov logic: A unifying framework for statistical relational learning. In Proceedings of the ICML'04 Workshop on Statistical Relational Learning and its Connections to Other Fields. 49--54.Google Scholar
- Duan, D., Li, Y., Jin, Y., and Lu, Z. 2009. Community mining on dynamic weighted directed graphs. In Proceedings of the 1st ACM International Workshop on Complex Networks meet Information and Knowledge Management. ACM, New York, 11--18. Google ScholarDigital Library
- Easley, D. and Kleinberg, J. 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press. Google ScholarDigital Library
- Even-Dar, E. and Shapira, A. 2007. A note on maximizing the spread of influence in social networks. In Proceedings of the 3<sup>rd</sup>International Workshop on Internet and Network Economics (WINE'07). Google ScholarDigital Library
- Evfimievski, A., Gehrke, J., and Srikant, R. 2003. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the ACM-SIGMOD Symposium on Principles of Database Systems (PODS'03). 211--222. Google ScholarDigital Library
- Evfimievski, A. V., Srikant, R., Agrawal, R., and Gehrke, J. 2002. Privacy preserving mining of association rules. In Proceedings of the 8<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Google ScholarDigital Library
- Faloutsos, M., Faloutsos, P., and Faloutsos, C. 1999. On power-law relationships of the internet topology. In Proceedings of the ACM SIGCOMM Data Communications Festival. 251--262. Google ScholarDigital Library
- Fawcett, T. and Provost, F. J. 1997. Adaptive fraud detection. Data Min. Knowl. Discov. 1, 3, 291--316. Google ScholarDigital Library
- Ferlez, J., Faloutsos, C., Leskovec, J., Mladenic, D., and Grobelnik, M. 2008. Monitoring network evolution using mdl. In Proceedings of the International Conference on Data Engineering (ICDE'08). Google ScholarDigital Library
- Flake, G. W., Lawrence, S., and Giles, C. L. 2000. Efficient identification of web communities. In Proceedings of the International SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'00). Google ScholarDigital Library
- Flake, G. W., Lawrence, S., Giles, C. L., and Coetzee, F. M. 2002. Self-Organization and identification of web communities. Comput. 35, 3, 66--71. Google ScholarDigital Library
- Fortunato, S. 2010. Community detection in graphs. Phys. Rep. 486, 3--5, 75--174.Google ScholarCross Ref
- Fortunato, S. and Barthelemy, M. 2007. Resolution limit in community detection. Proc. Nat. Acad. Sci. 104, 1.Google ScholarCross Ref
- Freeman, L. 2004. A History of Social Network Analysis. Empiric Press.Google Scholar
- Friedkin, N. E. 1998. A Structural Theory of Social Influence. Cambridge University Press.Google Scholar
- Getoor, L., Friedman, N., Koller, D., and Taskar, B. 2003. Learning probabilistic models of link structure. Mach. Learn. 3, 679--707. Google ScholarDigital Library
- Girvan, M. and Newman, M. E. J. 2002. Community structure in social and biological networks. Proc. Nat. Acad. Sci. USA 99, 12, 7821--7826.Google ScholarCross Ref
- Golbeck, J. and Hendler, J. 2006. Inferring binary trust relationships in web-based social networks. ACM Trans. Internet Technol. 6, 4, 497--529. Google ScholarDigital Library
- Goldenberg, J., Libai, B., and Muller, E. 2001. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Market. Lett. 12, 3, 211--223.Google ScholarCross Ref
- Gomes, L. H., Almeida, R. B., Bettencourt, L. M. A., Almeida, V., and Almeida, J. M. 2005. Comparative graph theoretical characterization of networks of spam and legitimate email. http://www.arxiv.org/abs/cs.CR/0504012.Google Scholar
- Goyal, A., Bonchi, F., and Lakshmanan, L. V. S. 2010. Learning influence probabilities in social networks. In Proceedings of the 3<sup>rd</sup> ACM International Conference on Web Search and Data Mining (WSDM'10). Google ScholarDigital Library
- Goyal, A., Bonchi, F., and Lakshmanan, L. V. S. 2008. Discovering leaders from community actions. In Proceedings of the ACM Conference on Information and Knowledge Management (CIKM'08). Google ScholarDigital Library
- Goyal, A., On, B.-W., Bonchi, F., and Lakshmanan, L. V. S. 2009. Gurumine: A pattern mining system for discovering leaders and tribes. In Proceedings of the 25th IEEE International Conference on Data Engineering (ICDE'09). Google ScholarDigital Library
- Gruhl, D., Guha, R. V., Liben-Nowell, D., and Tomkins, A. 2004. Information diffusion through blogspace. In Proceedings of the 13th International Conference on World Wide Web (WWW'04). Google ScholarDigital Library
- Guha, R., Kumar, R., Raghavan, P., and Tomkins, A. 2004a. Propagation of trust and distrust. In Proceedings of the 13th International Conference on World Wide Web (WWW'04). ACM Press, New York, 403--412. Google ScholarDigital Library
- Guha, R., Kumar, R., Raghavan, P., and Tomkins, A. 2004b. Propagation of trust and distrust. In Proceedings of the 13th International Conference on World Wide Web (WWW'04). Google ScholarDigital Library
- Gyongyi, Z., Garcia-Molina, H., and Pedersen, J. 2004. Combating Web spam with Trust-Rank. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 576--587. Google ScholarDigital Library
- Hanhijarvi, S., Garriga, G., and Puolamaki, K. 2009. Randomization techniques for graphs. In Proceedings of the SIAM Conference on Data Mining (SDM).Google Scholar
- Hartline, J. D., Mirrokni, V. S., and Sundararajan, M. 2008. Optimal marketing strategies over social networks. In Proceedings of the 17th International Conference on World Wide Web (WWW'08). Google ScholarDigital Library
- Haveliwala, T. H. 2002. Topic-Sensitive pagerank. In Proceedings of the 11<sup>th</sup>World Wide Web Conference. ACM Press, 517--526. Google ScholarDigital Library
- Hay, M., Miklau, G., Jensen, D., Towsley, D. F., and Weis, P. 2008. Resisting structural re-identification in anonymized social networks. Proc. VLDB, 102--114. Google ScholarDigital Library
- Hay, M., Miklau, G., Jensen, D., Weis, P., and Srivastava, S. 2007. Anonymizing social networks. Tech. rep. 07, 19, University of Massachusetts.Google Scholar
- Hel, M., Lawrence, R., Liu, Y., Perlich, C., Reddy, A., and Rosset, S. 2007. Looking for great ideas: Analyzing the innovation jam abstract. In Proceedings of the International SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'07). Google ScholarDigital Library
- Henzinger, M. R., Motwani, R., and Silverstein, C. 2002. Challenges in Web search engines. SIGIR Forum 37, 2. Google ScholarDigital Library
- Hettich, S. and Pazzani, M. J. 2006. Mining for proposal reviewers: Lessons learned at the national science foundation. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'06). ACM, New York, 862--871. Google ScholarDigital Library
- Hill, S., Provost, F., and Volinsky, C. 2006. Network-Based marketing: Identifying likely adopters via consumer networks. Statist. Sci. 21, 2, 256--276.Google ScholarCross Ref
- Holley, R. and Liggett, T. 1975. Ergodic theorems for weakly interacting infinite systems and the voter model. Ann. Probab. 3, 643--663.Google ScholarCross Ref
- Horowitz, D. and Kamvar, S. D. 2010. The anatomy of a large-scale social search engine. In Proceedings of the 19th International Conference on World Wide Web (WWW'10). ACM, New York, 431--440. Google ScholarDigital Library
- Ienco, D., Bonchi, F., and Castillo, C. 2010. The meme ranking problem: Maximizing microblogging virality. In Proceedings of the SIASP Workshop at IEEE International Conference on Data Mining (ICDM'10). Google ScholarDigital Library
- Inokuchi, A. and Washio, T. 2008. A fast method to mine frequent subsequences from graph sequence data. In Proceedings of the IEEE International Conference on Data Mining (ICDM'08). Google ScholarDigital Library
- Jurczyk, P. and Agichtein, E. 2007. Hits on question answer portals: Exploration of link analysis for author ranking. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, 845--846. Google ScholarDigital Library
- Jurvetson, S. 2000. What exactly is viral marketing&quest; Red Herr. 78, 110--112.Google Scholar
- Kaiser, F., Schwarz, H., and Jakob, M. 2007. Expose: Searching the web for expertise. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, 906. Google ScholarDigital Library
- Karypis, G. and Kumar, V. 1998. Multilevel algorithms for multi-constraint graph partitioning. In Proceedings of the ACM/IEEE Conference on Supercomputing (CDROM). Google ScholarDigital Library
- Katz, L. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 39--43.Google ScholarCross Ref
- Kempe, D., Kleinberg, J. M., and Tardos, E. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03). Google ScholarDigital Library
- Kim, Y. A. and Srivastava, J. 2007. Impact of social influence in e-commerce decision making. In Proceedings of the 9th International Conference on Electronic Commerce: The Wireless World of Electronic Commerce (ICEC'07). Google ScholarDigital Library
- Kleinberg, J., Papadimitriou, C., and Raghavan, P. 2003. Auditing boolean attributes. J. Comput. Syst. Sci. 6, 244--253. Google ScholarDigital Library
- Kleinberg, J. M. 1999. Authoritative sources in a hyperlinked environment. J. ACM 46, 5, 604--632. Google ScholarDigital Library
- Koren, Y. 2003. On spectral graph drawing. In Proceedings of the 9<sup>th</sup>International Computing and Combinatorics Conference. Springer, 496--508. Google ScholarDigital Library
- Kramer, R. M. 1999. Trust and distrust in organizations: Emerging perspectives, enduring questions. Ann. Rev. Psychol. 50, 569--598.Google ScholarCross Ref
- Krebs, V. 2002. Uncloaking terrorist networks. First Monday 7, 4.Google ScholarCross Ref
- Kumar, R., Novak, J., Raghavan, P., and Tomkins, A. 2004. Structure and evolution of blogspace. Comm. ACM 47, 12, 35--39. Google ScholarDigital Library
- Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E. 2000. Stochastic models for the web graph. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, 57--65. Google ScholarDigital Library
- Lahiri, M., Maiya, A. S., Sulo, R., Habiba, and Berger-Wolf, T. Y. 2008. The impact of structural changes on predictions of diffusion in networks. In Workshops Proceedings of the 8th IEEE International Conference on Data Mining (Workshops of ICDM'08). Google ScholarDigital Library
- Langville, A. N. and Meyer, C. D. 2003. Deeper inside pagerank. Internet Math. 1, 3, 335--380.Google ScholarCross Ref
- Lappas, T., Liu, K., and Terzi, E. 2009. Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 467--476. Google ScholarDigital Library
- Lazer, D., Pentland, A., Adamic, L., Aral, S., Barabasi, A., Brewer, D., Christakis, N., Contractor, N., Fowler, J., Guttmann, M., Jebara, T., King, G., Macy, M., Roy, D., and Alstyne, M. V. 2009. Computational social science. Sci, 323, 5915, 721--723.Google Scholar
- Lerman, K. and Jones, L. 2006. Social browsing on flickr. CoRR abs/cs/0612047.Google Scholar
- Leskovec, J., Adamic, L. A., and Huberman, B. A. 2007a. The dynamics of viral marketing. ACM Trans. Web 1, 1. Google ScholarDigital Library
- Leskovec, J., Backstrom, L., Kumar, R., and Tomkins, A. 2008. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD International Conference textiton Knowledge Discovery and Data Mining. ACM, New York, 462--470. Google ScholarDigital Library
- Leskovec, J., Kleinberg, J., and Faloutsos, C. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the 11<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (KDD). ACM, New York, 177--187. Google ScholarDigital Library
- Leskovec, J., Kleinberg, J., and Faloutsos, C. 2007b. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 1, 2. Google ScholarDigital Library
- Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., and Glance, N. S. 2007c. Cost-Effective outbreak detection in networks. In Proceedings of the 13<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'07). Google ScholarDigital Library
- Leskovec, J., Singh, A., and Kleinberg, J. M. 2006. Patterns of influence in a recommendation network. In Proceedings of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'06). Google ScholarDigital Library
- Levien, R. and Aiken, A. 1998. Attack-Resistant trust metrics for public key certification. In Proceedings of the 7th USENIX Security Symposium. 229--242. Google ScholarDigital Library
- Liben-Nowell, D. and Kleinberg, J. 2003. The link prediction problem for social networks. In Proceedings of the 12<sup>th</sup>International Conference on Information and Knowledge Management. ACM Press, New York, 556--559. Google ScholarDigital Library
- Liu, K. and Terzi, E. 2008. Towards identity anonymization on graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 93--106. Google ScholarDigital Library
- Liu, Z., Yu, J. X., Ke, Y., Lin, X., and Chen, L. 2008. Spotting significant changing subgraphs in evolving graphs. In Proceedings of the 8th International Conference on Data Mining (ICDM'08). Google ScholarDigital Library
- Lloyd, S. 1982. Least squares quantization in pcm. IEEE Trans. Inf. Theory 28, 2.Google ScholarDigital Library
- Mahajan, V., Muller, E., and Bass, F. 1990. New product diffusion models in marketing: A review and directions for research. J. Market. 54, 1, 1--26.Google ScholarCross Ref
- Marlow, C. 2003. Classifying emergent communitites through diffusion. In Proceedings of the Sunbelt International Social Networks Conference XXIII.Google Scholar
- Marti, S. and Garcia-Molina, H. 2006. Taxonomy of trust: Categorizing P2P reputation systems. Comput. Netw. 50, 4, 472--484. Google ScholarDigital Library
- Melnik, M. I. and Alm, J. 2002. Does a seller's ecommerce reputation matter&quest; Evidence from ebay auctions. J. Industr. Econ. 50, 3, 337--349.Google ScholarCross Ref
- Mui, L., Mohtashemi, M., and Halberstadt, A. 2002. A computational model of trust and reputation. In Proceedings of the 35th Hawaii International Conference on System Science (HICSS). Google ScholarDigital Library
- Narayanan, A. and Shmatikov, V. 2009. De-Anonymizing social networks. In Proceedings of the 30th IEEE Symposium on Security and Privacy. Google ScholarDigital Library
- Neville, J., Simsek, O., Jensen, D., Komoroske, J., Palmer, K., and Goldberg, H. 2005. Using relational knowledge discovery to prevent securities fraud. In Proceedings of the 11<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 449--458. Google ScholarDigital Library
- Ng, A. Y., Jordan, M. I., and Weiss, Y. 2001. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14. MIT Press, 849--856.Google Scholar
- Nguyen, H., Parikh, N., and Sundaresan, N. 2008. A software system for buzz-based recommendations. In Proceedings of the 14<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 1093--1096. Google ScholarDigital Library
- O'Madadhain, J., Hutchins, J., and Smyth, P. 2005. Prediction and ranking algorithms for event-based network data. ACM SIGKDD Explor. Newslett. 7, 2, 23--30. Google ScholarDigital Library
- Page, L., Brin, S., Motwani, R., and Winograd, T. 1998. The PageRank citation ranking: Bringing order to the Web. Tech. rep., Stanford Digital Library Technologies Project.Google Scholar
- Pandit, S., Chau, D. H., Wang, S., and Faloutsos, C. 2007. Netprobe: A fast and scalable system for fraud detection in online auction networks. In Proceedings of the 16th International Conference on World Wide Web. ACM, New York, 201--210. Google ScholarDigital Library
- Phithakkitnukoon, S. and Dantu, R. 2008. Adequacy of data for characterizing caller behavior. In Proceedings of the 2<sup>nd</sup>Workshop on Social Network Mining and Analysis (SNA-KDD'08) in Conjunction with the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Google Scholar
- Pioch, N. J. and Everett, J. O. 2006. Polestar: Collaborative knowledge management and sensemaking tools for intelligence analysts. In Proceedings of the 15th ACM Inter-National Conference on Information and Knowledge Management. ACM, New York, 513--521. Google ScholarDigital Library
- Provost, F. J., Dalessandro, B., Hook, R., Zhang, X., and Murray, A. 2009. Audience selection for on-line brand advertising: Privacy-Friendly social network targeting. In Proceedings of the 15<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Google ScholarDigital Library
- Pujol, J. M., Sanguesa, R., and Delgado, J. 2002. Extracting reputation in multi agent systems by means of social network topology. In Proceedings of the 1<sup>st</sup>International Joint Conference on Autonomous Agents and Multiagent Systems. ACM, New York, 467--474. Google ScholarDigital Library
- Rahm, E. and Do, H. H. 2000. Data cleaning: Problems and current approaches. IEEE Data Engin. Bull. 23, 4, 3--13.Google Scholar
- Resnick, P., Kuwabara, K., Zeckhauser, R., and Friedman, E. 2000. Reputation systems. Comm. ACM 43, 12, 45--48. Google ScholarDigital Library
- Richardson, M. and Domingos, P. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'02). Google ScholarDigital Library
- Rizvi, S. and Haritsa, J. R. 2002. Maintaining data privacy in association rule mining. In Proceedings of the International Conference in Very Large Databases (VLDB). Google ScholarDigital Library
- Ronen, I., Shahar, E., Ur, S., Uziel, E., Yogev, S., Zwerdling, N., Carmel, D., Guy, I., Har'el, N., and Koifman, S. O. 2009. Social networks and discovery in the enterprise (sand). In Proceedings of the 32<sup>nd</sup>International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, 836. Google ScholarDigital Library
- Saito, K., Nakano, R., and Kimura, M. 2008. Prediction of information diffusion probabili- ties for independent cascade model. In Proceedings of the 12th International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES'08). Google ScholarDigital Library
- Samper, J. J., Castillo, P. A., Araujo, L., and Guervos, J. J. M. 2006. Nectarss, An rss feed ranking system that implicitly learns user preferences. CoRR abs/cs/0610019.Google Scholar
- Schifanella, R., Barrat, A., Cattuto, C., Markines, B., and Menczer, F. 2010. Folks in folksonomies: Social link prediction from shared metadata. In Proceedings of the 3<sup>rd</sup>ACM International Conference on Web Search and Data Mining (WSDM). Google ScholarDigital Library
- Scott, J. 2000. Social Network Analysis: A Handbook. Sage Publications.Google Scholar
- Seid, D. Y. and Kobsa, A. 2002. Expert Finding Systems for Organizations: Problem and Domain Analysis and the DEMOIR Approach. MIT Press, Cambridge, MA, 327--358.Google Scholar
- Sirivianos, M., Yang, X., and Kim, K. 2009. FaceTrust: Assessing the credibility of online personas via social networks. Tech. rep., Duke University. http://www.cs.duke.edu/~msirivia/publications/facetrust-tech-report.pdf.Google Scholar
- Soghoian, C. 2008. Widespread cell phone location snooping by nsa&quest; http://voices.allthingsd.com/20080909/exclusive-widespread-cell-phone-location-snooping-by-nsa/.Google Scholar
- Song, X., Chi, Y., Hino, K., and Tseng, B. L. 2007. Information flow modeling based on diffusion rate for prediction and ranking. In Proceedings of the 16th International Conference on World Wide Web (WWW'07). Google ScholarDigital Library
- Song, X., Tseng, B. L., Lin, C.-Y., and Sun, M.-T. 2006. Personalized recommendation driven by information flow. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'06). Google ScholarDigital Library
- Sun, J., Faloutsos, C., Papadimitriou, S., and Yu, P. S. 2007. Graphscope: Parameter-Free mining of large time-evolving graphs. In Proceedings of the 13<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 687--696. Google ScholarDigital Library
- Sun, J., Tao, D., and Faloutsos, C. 2006. Beyond streams and graphs: Dynamic tensor analysis. In Proceedings of the 12<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, New York, 374--383. Google ScholarDigital Library
- Taherian, M., Amini, M., and Jalili, R. 2008. Trust inference in web-based social networks using resistive networks. In Proceedings of the 3<sup>rd</sup>International Conference on Internet and Web Applications and Services (ICIW'08). Google ScholarDigital Library
- Tang, J., Sun, J., Wang, C., and Yang, Z. 2009. Social influence analysis in large-scale networks. In Proceedings of the 15<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'09). Google ScholarDigital Library
- Tantipathananandh, C., Berger-Wolf, T., and Kempe, D. 2007. A framework for community identification in dynamic social networks. In Proceedings of the 13<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, New York, 717--726. Google ScholarDigital Library
- Taskar, B., Wong, M., Abbeel, P., and Koller, D. 2003. Link prediction in relational data. Neural Inf. Process. Syst. 15.Google Scholar
- Tomochi, M., Murata, H., and Kono, M. 2005. A consumer-based model of competitive diffusion: The multiplicative effects of global and local network externalities. J. Evolut. Econ. 15, 273--295.Google ScholarCross Ref
- Travers, J. and Milgram, S. 1969. An experimental study of the small world problem. Sociometry 32, 4, p425--443.Google ScholarCross Ref
- Vaidya, J., Zhu, Y. M., and Clifton, C. 2006. Privacy Preserving Data Mining. Springer-Verlag. Google ScholarDigital Library
- Valente, T. 1955. Network Models of the Diffusion of Innovations. Hampton Press.Google Scholar
- Virdhagriswaran, S. and Dakin, G. 2006. Camouflaged fraud detection in domains with complex relationships. In Proceedings of the 12<sup>th</sup>ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 941--947. Google ScholarDigital Library
- Wasserman and Faust, K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.Google Scholar
- Watts, D. 2007. Challenging the influentials hypothesis. In WOMMA Measuring Word of Mouth, Vol. 3. 201--211.Google Scholar
- Watts, D. and Dodds, P. 2007. Influential, networks, and public opinion formation. J. Consum. Res. 34, 4, 441--458.Google ScholarCross Ref
- Watts, D. and Peretti, J. May 2007. Viral marketing for the real world. Harvard Bus. Rev., 22--23.Google Scholar
- Watts, D. J. 2004. The &#8220;new&#8221; science of networks. Ann. Rev. Sociol. 30, 243--270.Google ScholarCross Ref
- Watts, D. J., Dodds, P. S., and Newman, M. E. J. 2002. Identity and search in social networks. Sci. 296, 1302--1305.Google ScholarCross Ref
- Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of 'small world' netwroks. Nature 393, 440--442.Google ScholarCross Ref
- West, D. 1996. Introduction to Graph Theory. Prentice Hall.Google Scholar
- White, S. and Smyth, P. 2005. A spectral clustering approach to finding communities in graph. In Proceedings of the SIAM International Conference on Data Mining (SDM'05).Google Scholar
- Winkler, W. E. 2003. Methods for evaluating and creating data quality. Inf. Syst. 29, 531--550. Google ScholarDigital Library
- Wortman, J. 2008. Viral marketing and the diffusion of trends on social networks. Tech. rep. MS-CIS-08-19, University of Pennsylvania. May.Google Scholar
- Wu, W., Xiao, Y., Wang, W., He, Z., and Wang, Z. 2010. k-Symmetry model for identity anonymization in social networks. In Proceedings of the 13th International Conference on Extending Database Technology. Google ScholarDigital Library
- Yimam-seid, D. and Kobsa, A. 2002. Expert finding systems for organizations: Problem and domain analysis and the demoir approach. J. Orgiz. Comput. Electron. Commerce 13, 2003.Google Scholar
- Ying, X., Pan, K., Wu, X., and Guo, L. 2009. Comparisons of randomization and k-degree anonymization schemes for privacy preserving social network publishing. In Proceedings of the 3rd SNA-KDD Workshop. Google ScholarDigital Library
- Ying, X. and Wu, X. 2008. Randomizing social networks: A spectrum preserving approach. In Proceedings of the SIAM Conference on Data Mining (SDM'08). 739--750.Google Scholar
- Ying, X. and Wu, X. 2009a. Graph generation with prescribed feature constraints. In Proceedings of the SIAM Conference on Data Mining (SDM'09).Google Scholar
- Ying, X. and Wu, X. 2009b. On link privacy in randomizing social networks. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'09). Google ScholarDigital Library
- Zhang, J., Ackerman, M. S., and Adamic, L. 2007. Expertise networks in online communities: Structure and algorithms. In Proceedings of the 16<sup>th</sup>International Conference on World Wide Web. ACM, New York, 221--230. Google ScholarDigital Library
- Zheleva, E. and Getoor, L. 2007. Preserving the privacy of sensitive relationship in graph data. In Proceedings of the International Workshop on Privacy, Security and Trust in KDD (PinKDD'07). 153--171. Google ScholarDigital Library
- Zhou, B. and Pei, J. 2008. Preserving privacy in social networks against neighborhood attacks. In Proceedings of the International Conference on Data Engineering (ICDE'08). 506--515. Google ScholarDigital Library
- Ziegler, C.-N. and Lausen, G. 2005a. Propagation models for trust and distrust in social networks. Inf. Syst. Front. 7, 4-5, 337--358. Google ScholarDigital Library
- Ziegler, C.-N. and Lausen, G. 2005b. Propagation models for trust and distrust in social networks. Inf. Syst. Front. 7, 4-5, 337--358. Google ScholarDigital Library
Index Terms
- Social Network Analysis and Mining for Business Applications
Recommendations
Mining expertise and interests from social media
WWW '13: Proceedings of the 22nd international conference on World Wide WebThe rising popularity of social media in the enterprise presents new opportunities for one of the organization's most important needs--expertise location. Social media data can be very useful for expertise mining due to the variety of existing ...
A measurement-driven analysis of information propagation in the flickr social network
WWW '09: Proceedings of the 18th international conference on World wide webOnline social networking sites like MySpace, Facebook, and Flickr have become a popular way to share and disseminate content. Their massive popularity has led to viral marketing techniques that attempt to spread content, products, and ideas on these ...
Potential networks, contagious communities, and understanding social network structure
WWW '13: Proceedings of the 22nd international conference on World Wide WebIn this paper we study how the network of agents adopting a particular technology relates to the structure of the underlying network over which the technology adoption spreads. We develop a model and show that the network of agents adopting a particular ...
Comments