面向大规模社交网络的信息传播模型及其应用研究
|
摘要
近年来,社交网络得到了极大的发展,成为人们消磨休闲时光、获取最新信息、了解朋友动态的重要工具,构成了人们网络在线生活的重要一部分。社交网络的出现带来了各种可能性,如美国总统奥巴马利用社交网络成功赢得两次竞选,韩国音乐人PSY利用社交网络传播其舞曲视频《江南style》突破了10亿次点击的吉尼斯记录。社交网络如何进行信息传播,以及如何利用社交网络推动信息的快速有效传播,成为目前学术界研究的热点。本文系统研究了社交网络上的信息传播模型,其研究成果对于改进社交网络上的信息服务具有重要的应用价值。
首先,本文提出一种信息传播的快速计算模型：线性影响力传播模型。信息传播模型是描述社交网络上信息传播过程和进行信息传播计算的基础。尽管近年来对信息传播模型的研究较多,如独立级联模型和线性阈值模型,但这些模型都存在许多缺点,如不可解析,没有闭形式解,效率太低等。这些缺点导致它们只能应用在小规模网络中,然而实际环境中的社交网络(如Facebook、 Twitter等)常常拥有数以亿计的用户规模!为此,本文提出了一种线性影响力模型。该模型能够在线性时间内完成信息传播计算,同时该模型具有可调节性,通过调节模型参数可以使得该模型的信息传播结果非常逼近传统模型。在一个规模达到千万的实际社交网络上的测试表明,线性影响力模型能够严格逼近传统模型的传播效果,而且仅需要付出比传统模型低得多的计算代价。
其次,本文基于线性影响力模型提出PageRank的改进算法。PageRank算法是用于计算网络中节点权威值的经典算法。自Larry Page和Seige Brin提出以来,已成为网络研究中最重要的算法之一,也是互联网巨擎Google的立身之本。本文从影响力传播的角度重新分析了这一算法,并得出“网络中节点权威值就是该节点对网络中所有节点的影响力之和”这一本质结论。同时还论证了PageRank算法只是对网络中节点权威值的一种快速近似计算,并给出了多种针对节点权威值计算的精确算法,如规范PageRank算法和先验Pagerank算法等。本文在科学家合作网络上对各种PageRank算法进行了对比,结果表明规范PageRank算法和先验PageRank算法均能取得比传统PageRank更好的结果。
然后,本文基于线性影响力传播模型和PageRank算法的本质联系,提出一种用于快速计算任意群体影响力(权威值)的群体PageRank算法。群体PageRank算法是对PageRank算法一种维度上的推广。众所周知,Pagerank算法是计算节点权威值的经典算法,然而如何计算一个群体的权威值呢?如美国民主党和共和党在竞选之时,如何计算两党在民众中的权威值从而预测谁将赢得最终大选?因此,群体权威值计算具有重要的应用价值。本文从影响力传播的角度分析了群体的权威值的计算方法,同时基于影响力传播模型和PageRank算法的关系提出了群体PageRank算法,用于快速计算大规模社交网络上群体权威值。在真实数据上进行的大量测试表明,群体PageRank算法能在常数时间内计算任意群体的群体权威值,同时计算结果能够一致逼近真实结果。
最后,本文将线性影响力传播模型和群体PageRank算法用于病毒营销设计,为社交网络上的信息传播提供最佳策略。病毒营销,亦称“口碑效应”,致力于寻找一组社交网络用户为某种产品代言,希望这组用户能在网络上造成多米诺骨牌效应,使得该产品的好口碑能口口相传到到最大规模的网络群体中,从而为产品销售带来最佳效果。本文基于线性影响力传播模型和群体PageRank算法提出了两种病毒营销算法,Linear算法和Bound算法。同时,在多个真实数据上进行的实验测试结果表明,Linear算法和Bound算法均能在时间和效果上胜过当前最新算法。其中,Bound算法甚至只需要常数时间代价就能为病毒营销设计出最佳策略,尤其适合应用在超大规模的社交网络上。
Recent years has witnessed the great development of social network. Social network has become a necessity for people's life. They use it to spend spare time, get information and contact with their friends. This creator has brought endless possibility for people's future life. For example, US president Obama use social network to get the votes for him and win the final campaign; Korea singer PSY use social network to maximally spread his work Gangnam style. How does the infor-mation propagate in social network and how to take advantage of social network to boost the information propagation, have become the hot problems in academia. In this paper, we will systematically research the information propagation model in social network.
First, this paper has proposed an efficient information propagation model: linear influence model. Information propagation model is the basis for describing and computing the information propagation process. Although there have been many models, such as independent cascade model and linear threshold model, these models have many shortages. They are untractable, low-efficient, and has no closed-form expression, which make them only applicable to the small scale social networks. However, the real social networks (such as Facebbook, twitter) usually have billions of nodes. To overcome these obstacles, we proposed the linear influence model which is tunable, flexible and efficient. We could use it to approach the traditional models with little effort and complete its computation in linear time. We verified its performance in several large scale social networks, even with millions of nodes.
Second, this paper studied the essential of PageRank, and proposed several enhanced PageRank algorithm. PageRank is the classical algorithm for authority computation. This paper re-analyzed this algorithm in the perspective of social influence and found the conclusion "the node authority is actually the sum of its influence on each node of social network". This paper also proved that PageRank is a fast approximation for node's influence and could be improved by many ways. This paper proposed several enhanced PageRank, such as norm-PageRank, prior-PageRank. Moreover, This paper also proposed a general PageRank:influence-PageRank, which is applicable to any social network with arbitrary information transition probability matrix, and proposed a more-general PageRank:group-PageRank, which is used to compute the authority of a group of nodes. Finally, this paper verified the correctness of the conclusion and the advantage of those enhanced PageRank algorithms through experiments.
At last, this paper worked on applying the linear influence model and group-PageRank to design viral marketing campaign. Viral marketing, also called as "word-of-mouth effect", targets at finding a small group of influential nodes-giving them free samples of a product-for triggering a cascade of product propagation that people recommend the product to their friends and friends'friends, with the hope that the product will be adopted by a maximum fraction of the social network. This paper proposed two algorithms:Linear and Bound, based on the linear influence model and group-PageRank respectively. We tested these two algorithms in many real data sets. The experimental results showed that both of Linear and Bound perform better than the state-of-the-art algorithms. Especially, Bound could make the optimal strategy in constant time, which is applicable to the social networks with billions of nodes.
首先,本文提出一种信息传播的快速计算模型：线性影响力传播模型。信息传播模型是描述社交网络上信息传播过程和进行信息传播计算的基础。尽管近年来对信息传播模型的研究较多,如独立级联模型和线性阈值模型,但这些模型都存在许多缺点,如不可解析,没有闭形式解,效率太低等。这些缺点导致它们只能应用在小规模网络中,然而实际环境中的社交网络(如Facebook、 Twitter等)常常拥有数以亿计的用户规模!为此,本文提出了一种线性影响力模型。该模型能够在线性时间内完成信息传播计算,同时该模型具有可调节性,通过调节模型参数可以使得该模型的信息传播结果非常逼近传统模型。在一个规模达到千万的实际社交网络上的测试表明,线性影响力模型能够严格逼近传统模型的传播效果,而且仅需要付出比传统模型低得多的计算代价。
其次,本文基于线性影响力模型提出PageRank的改进算法。PageRank算法是用于计算网络中节点权威值的经典算法。自Larry Page和Seige Brin提出以来,已成为网络研究中最重要的算法之一,也是互联网巨擎Google的立身之本。本文从影响力传播的角度重新分析了这一算法,并得出“网络中节点权威值就是该节点对网络中所有节点的影响力之和”这一本质结论。同时还论证了PageRank算法只是对网络中节点权威值的一种快速近似计算,并给出了多种针对节点权威值计算的精确算法,如规范PageRank算法和先验Pagerank算法等。本文在科学家合作网络上对各种PageRank算法进行了对比,结果表明规范PageRank算法和先验PageRank算法均能取得比传统PageRank更好的结果。
然后,本文基于线性影响力传播模型和PageRank算法的本质联系,提出一种用于快速计算任意群体影响力(权威值)的群体PageRank算法。群体PageRank算法是对PageRank算法一种维度上的推广。众所周知,Pagerank算法是计算节点权威值的经典算法,然而如何计算一个群体的权威值呢?如美国民主党和共和党在竞选之时,如何计算两党在民众中的权威值从而预测谁将赢得最终大选?因此,群体权威值计算具有重要的应用价值。本文从影响力传播的角度分析了群体的权威值的计算方法,同时基于影响力传播模型和PageRank算法的关系提出了群体PageRank算法,用于快速计算大规模社交网络上群体权威值。在真实数据上进行的大量测试表明,群体PageRank算法能在常数时间内计算任意群体的群体权威值,同时计算结果能够一致逼近真实结果。
最后,本文将线性影响力传播模型和群体PageRank算法用于病毒营销设计,为社交网络上的信息传播提供最佳策略。病毒营销,亦称“口碑效应”,致力于寻找一组社交网络用户为某种产品代言,希望这组用户能在网络上造成多米诺骨牌效应,使得该产品的好口碑能口口相传到到最大规模的网络群体中,从而为产品销售带来最佳效果。本文基于线性影响力传播模型和群体PageRank算法提出了两种病毒营销算法,Linear算法和Bound算法。同时,在多个真实数据上进行的实验测试结果表明,Linear算法和Bound算法均能在时间和效果上胜过当前最新算法。其中,Bound算法甚至只需要常数时间代价就能为病毒营销设计出最佳策略,尤其适合应用在超大规模的社交网络上。
Recent years has witnessed the great development of social network. Social network has become a necessity for people's life. They use it to spend spare time, get information and contact with their friends. This creator has brought endless possibility for people's future life. For example, US president Obama use social network to get the votes for him and win the final campaign; Korea singer PSY use social network to maximally spread his work Gangnam style. How does the infor-mation propagate in social network and how to take advantage of social network to boost the information propagation, have become the hot problems in academia. In this paper, we will systematically research the information propagation model in social network.
First, this paper has proposed an efficient information propagation model: linear influence model. Information propagation model is the basis for describing and computing the information propagation process. Although there have been many models, such as independent cascade model and linear threshold model, these models have many shortages. They are untractable, low-efficient, and has no closed-form expression, which make them only applicable to the small scale social networks. However, the real social networks (such as Facebbook, twitter) usually have billions of nodes. To overcome these obstacles, we proposed the linear influence model which is tunable, flexible and efficient. We could use it to approach the traditional models with little effort and complete its computation in linear time. We verified its performance in several large scale social networks, even with millions of nodes.
Second, this paper studied the essential of PageRank, and proposed several enhanced PageRank algorithm. PageRank is the classical algorithm for authority computation. This paper re-analyzed this algorithm in the perspective of social influence and found the conclusion "the node authority is actually the sum of its influence on each node of social network". This paper also proved that PageRank is a fast approximation for node's influence and could be improved by many ways. This paper proposed several enhanced PageRank, such as norm-PageRank, prior-PageRank. Moreover, This paper also proposed a general PageRank:influence-PageRank, which is applicable to any social network with arbitrary information transition probability matrix, and proposed a more-general PageRank:group-PageRank, which is used to compute the authority of a group of nodes. Finally, this paper verified the correctness of the conclusion and the advantage of those enhanced PageRank algorithms through experiments.
At last, this paper worked on applying the linear influence model and group-PageRank to design viral marketing campaign. Viral marketing, also called as "word-of-mouth effect", targets at finding a small group of influential nodes-giving them free samples of a product-for triggering a cascade of product propagation that people recommend the product to their friends and friends'friends, with the hope that the product will be adopted by a maximum fraction of the social network. This paper proposed two algorithms:Linear and Bound, based on the linear influence model and group-PageRank respectively. We tested these two algorithms in many real data sets. The experimental results showed that both of Linear and Bound perform better than the state-of-the-art algorithms. Especially, Bound could make the optimal strategy in constant time, which is applicable to the social networks with billions of nodes.
引文
[1]Goldenberg J, Libai B, Muller E. Talk of the network:A complex systems look at the underlying process of word-of-mouth. Marketing letters,2001,12(3):211-223.
[2]Granovetter M. Threshold models of collective behavior. American journal of sociology,1978. 1420-1443.
[3]Xiang B, Chen E, Liu Q, et al. A Social Influence Model Based On Circuit Theory. arXiv preprint arXiv:1205.6024,2012..
[4]A Linear Circuit Model For Social Influence. arXiv preprint arXiv:1206.1105,2012..
[5]Page L, Brin S, Motwani R, et al. The PageRank citation ranking:Bringing order to the web. Proceedings of Proceedings of WWW Conference. Stanford InfoLab,1999.
[6]Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network. Proceedings of Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2003.137-146.
[7]Borodin A, Roberts G O, Rosenthal J S, et al. Link analysis ranking:algorithms, theory, and experiments. ACM Transactions on Internet Technology (TOIT),2005,5(1):231-297.
[8]Chakrabarti S, Dom B E, Kumar S R, et al. Mining the Web's link structure. Computer,1999, 32(8):60-67.
[9]McGlohon M, Akoglu L, Faloutsos C. Weighted graphs and disconnected components:patterns and a generator. Proceedings of Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.524-532.
[10]Chakrabarti S. Dynamic personalized pagerank in entity-relation graphs. Proceedings of Proceed-ings of the 16th international conference on World Wide Web. ACM,2007.571-580.
[11]Albert R, Jeong H, Barabasi A L. Internet:Diameter of the world-wide web. Nature,1999, 401 (6749):130-131.
[12]Mackay R. Linked:How Everything is Connected to Everything Else and What It Means for Business, Science and Everyday Life. Complicity:An International Journal of Complexity and Education,2005,2(1).
[13]Watts D J, Strogatz S H. Collective dynamics of j(?)mall-worldj-networks. nature,1998, 393(6684):440-442.
[14]Mihail M, Papadimitriou C. On the eigenvalue power law. Proceedings of Randomization and approximation techniques in computer science. Springer,2002:254-262.
[15]Siganos G, Faloutsos M, Faloutsos P, et al. Power laws and the AS-level internet topology. IEEE/ACM Transactions on Networking (TON),2003, 11(4):514-524.
[16]Langville A, Meyer C. Deeper inside pagerank. Internet Mathematics,2004, 1(3):335-380.
[17]Agarwal A, Chakrabarti S, Aggarwal S. Learning to rank networked entities. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2006.14-23.
[18]Koren Y, North S C, Volinsky C. Measuring and extracting proximity in networks. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2006.245-255.
[19]Fogaras D, Racz B. Scaling link-based similarity search. Proceedings of Proceedings of the 14th international conference on World Wide Web. ACM,2005.641-650.
[20]Doyle P G, Snell J L. Random walks and electric networks. arXiv preprint math.PR/0001057, 2000,3.
[21]Lovasz L. Random walks on graphs:A survey. Combinatorics, Paul erdos is eighty,1993,2(1):1-46.
[22]Agarwal A, Chakrabarti S. Learning random walks to rank nodes in graphs. Proceedings of Proceedings of the 24th international conference on Machine learning. ACM,2007.9-16.
[23]Haveliwala T. Topic-sensitive pagerank:A context-sensitive ranking algorithm for web search. IEEE Transactions on Knowledge and Data Engineering,2003,15(4):784-796.
[24]Fogaras D, Racz B, Csalogany K, et al. Towards scaling fully personalized pagerank:Algorithms, lower bounds, and experiments. Internet Mathematics,2005,2(3):333-358.
[25]Boley D, Ranjan G, Zhang Z L. Commute times for a directed graph using an asymmetric Laplacian. Linear Algebra and its Applications,2011,435 (2):224-242.
[26]Hopcroft J, Sheldon D. Manipulation-resistant reputations using hitting time. Proceedings of Algorithms and Models for the Web-Graph. Springer,2007:68-81.
[27]Katz L. A new status index derived from sociometric analysis. Psychometrika,1953,18(1):39-43.
[28]Zhu X, Lafferty J. Harmonic mixtures:combining mixture models and graph-based method-s for inductive and scalable semi-supervised learning. Proceedings of Proceedings of the 22nd international conference on Machine learning. ACM,2005.1052-1059,
[29]Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using gaussian fields and harmon-ic functions. Proceedings of MACHINE LEARNING-INTERNATIONAL WORKSHOP THEN CONFERENCE-, volume 20,2003.912.
[30]Smola A J, Kondor R. Kernels and regularization on graphs. Proceedings of Learning theory and kernel machines. Springer,2003:144-158.
[31]Dalvi B B, Kshirsagar M, Sudarshan S. Keyword search on external memory data graphs. Pro-ceedings of the VLDB Endowment,2008, 1(1):1189-1204.
[32]Balmin A, Hristidis V, Papakonstantinou Y. Objectrank:Authority-based keyword search in databases. Proceedings of Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004.564-575.
[33]Mei Q, Zhou D, Church K. Query suggestion using hitting time. Proceedings of Proceedings of the 17th ACM conference on Information and knowledge management. ACM,2008.469-478.
[34]Qiu H, Hancock E R. Robust multi-body motion tracking using commute time clustering. Pro-ceedings of Computer Vision-ECCV 2006. Springer,2006:160-173.
[35]Shi J, Malik J. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelli-gence, IEEE Transactions on,2000,22(8):888-905.
[36]Grady L. Random walks for image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on,2006,28(11):1768-1783.
[37]Levin A, Lischinski D, Weiss Y. Colorization using optimization. Proceedings of ACM Transactions on Graphics (TOG), volume 23. ACM,2004.689-694.
[38]Lafferty J, Zhai C. Document language models, query models, and risk minimization for informa-tion retrieval. Proceedings of Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval. ACM,2001.111-119.
[39]Chakrabarti D, Faloutsos C. Graph mining:Laws, generators, and algorithms. ACM Computing Surveys (CSUR),2006,38(1):2.
[40]Leskovec J, Lang K J, Dasgupta A, et al. Statistical properties of community structure in large social and information networks. Proceedings of Proceedings of the 17th international conference on World Wide Web. ACM,2008.695-704.
[41]Buehrer G, Chellapilla K. A scalable pattern mining approach to web graph compression with communities. Proceedings of Proceedings of the 2008 International Conference on Web Search and Data Mining. ACM,2008.95-106.
[42]Brohee S, Helden J. Evaluation of clustering algorithms for protein-protein interaction networks. BMC bioinformatics,2006,7(1):488.
[43]Kaufman L, Rousseeuw P J. Finding groups in data:an introduction to cluster analysis, volume 344. Wiley-Interscience,2009.
[44]Chakrabarti D, Kumar R, Tomkins A. Evolutionary clustering. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2006.554-560.
[45]Berger-Wolf T Y, Saia J. A framework for analysis of dynamic social networks. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2006.523-528.
[46]Kernighan B, Lin S. An eflicient heuristic procedure for partitioning graphs. Bell system technical journal,1970..
[47]Brandes U, Delling D, Gaertler M, et al. On finding graph clusterings with maximum modularity. Proceedings of Graph-Theoretic Concepts in Computer Science. Springer,2007.121-132.
[48]Clauset A, Newman M E, Moore C. Finding community structure in very large networks. Physical review E,2004,70(6):066111.
[49]Girvan M, Newman M E. Community structure in social and biological networks. Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[50]Leicht E A, Newman M E. Community structure in directed networks. Physical review letters, 2008,100(11):118703.
[51]Xiang B, Chen E H, Zhou T. Finding community structure based on subgraph similarity. Pro-ceedings of Complex Networks. Springer,2009:73-81.
[52]Chung F R. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No.92). 1997..
[53]Andersen R, Chung F, Lang K. Local graph partitioning using pagerank vectors. Proceedings of Foundations of Computer Science,2006. FOCS'06.47th Annual IEEE Symposium on. IEEE, 2006.475-486.
[54]Barnard S T, Simon H D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency:Practice and Experience,1994,6(2):101-117.
[55]Azran A. The rendezvous algorithm:Multiclass semi-supervised learning with markov random walks. Proceedings of Proceedings of the 24th international conference on Machine learning. ACM, 2007.49-56.
[56]Baluja S, Seth R, Sivakumar D, et al. Video suggestion and discovery for youtube:taking random walks through the view graph. Proceedings of Proceedings of the 17th international conference on World Wide Web. ACM,2008.895-904.
[57]Chapelle O, Zien A, et al. Label Propagation and Quadratic Criterion..
[58]Bhagat S, Rozenbaum I, Cormode G. Applying link-based classification to label blogs. Proceedings of Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis. ACM,2007.92-101.
[59]Blum A, Chawla S. Learning from labeled and unlabeled data using graph mincuts.2001..
[60]Kleinberg.J, Tardos E, Approximation algorithms for classification problems with pairwise rela-tionships:Metric labeling and Markov random fields. Proceedings of Foundations of Computer Science,1999.40th Annual Symposium on. IEEE,1999.14-23.
[61]Lu Q, Getoor L. Link-based classification. Proceedings of MACHINE LEARNING-INTERNATIONAL WORKSHOP THEN CONFERENCE-, volume 20,2003,496.
[62]Jaakkola M S T. Partially labeled classification with Markov random walks. Proceedings of Advances in Neural Information Processing Systems 14:Proceedings of the 2002 Conference, volume 2. MIT Press,2002.945.
[63]Zhou D, Bousquet O, Lal T N, et al. Learning with local and global consistency. Advances in neural information processing systems,2004,16(753760):284.
[64]Zhou Y, Cheng H, Yu J X. Graph clustering based on structural/attribute similarities. Proceedings of the VLDB Endowment,2009,2(1):718-729.
[65]Chakrabarti S, Dom B, Indyk P. Enhanced hypertext categorization using hyperlinks. Proceedings of ACM SIGMOD Record, volume 27. ACM,1998.307-318.
[66]Goyal A, Bonchi F, Lakshmanan L V. Learning influence probabilities in social networks. Proceed-ings of Proceedings of the third ACM international conference on Web search and data mining. ACM,2010.241-250.
[67]Sen P, Namata G, Bilgic M, et al. Collective classification in network data. AI magazine,2008, 29(3):93.
[68]Ahmed A, Xing E P. Recovering time-varying networks of dependencies in social and biological studies. Proceedings of the National Academy of Sciences,2009,106(29):11878-11883.
[69]Asur S, Parthasarathy S, Ucar D. An event-based framework for characterizing the evolutionary behavior of interaction graphs. Proceedings of Proceedings of the 13th ACM SIGKDD interna-tional conference on Knowledge discovery and data mining. ACM,2007.913-921.
[70]Kumar R, Novak J, Tomkins A. Structure and evolution of online social networks. Proceedings of Link Mining:Models, Algorithms, and Applications. Springer,2010:337-357.
[71]Leskovec J, Backstrom L, Kumar R, et al. Microscopic evolution of social networks. Proceedings of Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.462-470.
[72]Lin Y R, Chi Y, Zhu S, et al. Analyzing communities and their evolutions in dynamic social networks. ACM Transactions on Knowledge Discovery from Data (TKDD),2009,3(2):8.
[73]Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution. Nature,2007, 446(7136):664-667.
[74]Aggarwal C C, Yu P. Online analysis of community evolution in data streams. Proceedings of Proceedings of the SIAM International Conference on Data Mining (SDM 2005),2005.56-67.
[75]Ferlez J, Faloutsos C, Leskovec J, et al. Monitoring network evolution using MDL. Proceedings of Data Engineering,2008. ICDE 2008. IEEE 24th International Conference on. IEEE,2008. 1328-1330.
[76]Tantipathananandh C, Berger-Wolf T, Kempe D. A framework for community identification in dynamic social networks. Proceedings of Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2007.717-726.
[77]Toyoda M, Kitsuregawa M. Extracting evolution of web communities from a series of web archives. Proceedings of Proceedings of the fourteenth ACM conference on Hypertext and hypermedia. ACM,2003.28-37.
[78]Adamic L A, Adar E. Friends and neighbors on the web. Social networks,2003,25(3):211-230.
[79]Bilgic M, Namata G M, Getoor L. Combining collective classification and link prediction. Pro-ceedings of Data Mining Workshops,2007. ICDM Workshops 2007. Seventh IEEE International Conference on. IEEE,2007.381-386.
[80]Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American society for information science and technology,2007,58(7):1019-1031.
[81]Sarukkai R R. Link prediction and path analysis using Markov chains. Computer Networks,2000, 33(1):377-386.
[82]Herman I, Melangon G, Marshall M S. Graph visualization and navigation in information visual-ization:A survey. Visualization and Computer Graphics, IEEE Transactions on,2000,6(1):24-43.
[83]Henry N, Fekete J D, McGuffin M J. NodeTrix:a hybrid visualization of social networks. Visu-alization and Computer Graphics, IEEE Transactions on,2007,13(6):1302-1309.
[84]Freeman L C. Visualizing social networks. Journal of social structure,2000,1(1):4.
[85]Bertini E, Lalanne D. Surveying the complementary role of automatic data analysis and visu-alization in knowledge discovery. Proceedings of Proceedings of the ACM SIGKDD Workshop on Visual Analytics and Knowledge Discovery:Integrating Automated Analysis with Interactive Exploration. ACM,2009.12-20.
[86]Brandes U, Pich C. An experimental study on distance-based graph drawing. Proceedings of Graph Drawing. Springer,2009.218-229.
[87]Brandes U, Kenis P, Raab J, et al. Explorations into the visualization of policy networks. Journal of Theoretical Politics,1999, 11(1):75-106.
[88]Dwyer T, Hong S H, Koschiitzki D, et al. Visual analysis of network centralities. Proceedings of Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation-Volume 60. Aus-tralian Computer Society, Inc.,2006.189-197.
[89]Holten D. Hierarchical edge bundles:Visualization of adjacency relations in hierarchical data. Visualization and Computer Graphics, IEEE Transactions on,2006,12(5):741-748.
[90]Jia Y, Hoberock J, Garland M, et al. On the visualization of social and other scale-free networks. Visualization and Computer Graphics, IEEE Transactions on,2008,14(6):1285-1292.
[91]Aris A, Shneiderman B. Designing semantic substrates for visual network exploration. Information Visualization,2007,6(4):281-300.
[92]Perer A, Shneiderman B. Integrating statistics and visualization:case studies of gaining clarity during exploratory data analysis. Proceedings of Proceedings of the twenty-sixth annual SIGCHI conference on Human factors in computing systems. ACM,2008.265-274.
[93]Kang H, Getoor L, Singh L. Visual analysis of dynamic group membership in temporal social networks. ACM SIGKDD Explorations Newsletter,2007,9(2):13-21.
[94]Moody J, McFarland D, Bender-deMoll S. Dynamic network visualizationl. American Journal of Sociology,2005,110(4):1206-1241.
[95]Aggarwal C. Social network data analytics. Springer-Verlag New York Inc,2011.
[96]Anagnostopoulos A, Kumar R, Mahdian M. Influence and correlation in social networks. Proceed-ings of Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.7-15.
[97]Aral S, Muchnik L, Sundararajan A. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proceedings of the National Academy of Sciences,2009, 106(51):21544-21549.
[98]Backstrom L, Kumar R, Marlow C, et al. Preferential behavior in online groups. Proceedings of Proceedings of the international conference on Web search and web data mining. ACM,2008. 117-128.
[99]Bakshy E, Karrer B, Adamic L A. Social influence and the diffusion of user-created content. Proceedings of Proceedings of the 10th ACM conference on Electronic commerce. ACM,2009. 325-334.
[100]Eastwick P W, Gardner W L. Is it a game? Evidence for social influence in the virtual world. Social Influence,2009,4(1):18-32.
[101]Bass F M. Comments on (?)A New Product Growth for Model Consumer Durables The Bass Modelj±. Management science,2004,50(12 supplement):1833-1840.
[102]Hartline J, Mirrokni V, Sundararajan M. Optimal marketing strategies over social networks. Proceedings of Proceedings of the 17th international conference on World Wide Web. ACM,2008. 189-198.
[103]Provost F, Dalessandro B, Hook R, et al. Audience selection for on-line brand advertising:privacy-friendly social network targeting. Proceedings of Proceedings of the 15th ACM SIGKDD interna-tional conference on Knowledge discovery and data mining. ACM,2009.707-716.
[104]Brown J J, Reingen P H. Social ties and word-of-mouth referral behavior. Journal of Consumer Research,1987.350-362.
[105]Chen W, Wang Y, Yang S. Efficient influence maximization in social networks. Proceedings of Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2009.199-208.
[106]Cialdini R B, Goldstein N J. Social influence:Compliance and conformity. Annu. Rev. Psychol., 2004,55:591-621.
[107]Crandall D, Cosley D, Huttenlocher D, et al. Feedback effects between similarity and social influ-ence in online communities. Proceedings of Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.160-168.
[108]La Fond T, Neville J. Randomization tests for distinguishing social influence and homophily effects. Proceedings of Proceedings of the 19th international conference on World wide web. ACM,2010. 601-610.
[109]Manavoglu E, Pavlov D, Giles C L. Probabilistic user behavior models. Proceedings of Data Mining,2003. ICDM 2003. Third IEEE International Conference on. IEEE,2003.203-210.
[110]Domingos P, Richardson M. Mining the network value of customers. Proceedings of Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2001.57-66.
[111]Java A, Kolari P, Finin T, et al. Modeling the spread of influence on the blogosphere. Proceedings of Proceedings of the 15th international world wide web conference,2006.22-26.
[112]Goyal A, Bonchi F, Lakshmanan L V. Discovering leaders from community actions. Proceedings of Proceedings of the 17th ACM conference on Information and knowledge management. ACM, 2008.499-508.
[113]Aggarwal C, Khan A, Yan X. On Flow Authority Discovery in Social Networks. Proceedings of Proceedings of the SDM Conference,2011.
[114]Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks. Proceedings of Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2010.1029-1038.
[115]Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks. Proceedings of Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2007.420-429.
[116]Yang Y, Chen E, Liu Q, et al. On Approximation of Real-World InuenceSpread. Proceedings of The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (PKDD),2012. xxx-xxx.
[117]BIANCHINI M, GORI M, SCARSELLI F. Inside PageRank. ACM Transactions on Internet Technology,2005,5(1):92-128.
[118]Ding Y, Yan E, Frazho A, et al. PageRank for ranking authors in co-citation networks. Journal of the American Society for Information Science and Technology,2009,60(11):2229-2243.
[119]Ding Y. Topic-based PageRank on author cocitation networks. Journal of the American Society for Information Science and Technology,2011,62(3):449-466.
[120]Liu Q, Xiang B, Chen E, et al. Influential seed items recommendation. Proceedings of Proceedings of the sixth ACM conference on Recommender systems. ACM,2012.245-248.
[121]Zhu H, Cao H, Xiong H, et al. Towards expert finding by leveraging relevant categories in authority ranking. Proceedings of Proceedings of the 20th ACM international conference on Information and knowledge management. ACM,2011.2221-2224.
[122]Aggarwal C, Khan A, Yan X. On flow authority discovery in social networks. Proceedings of Proceedings of SIAM Conference on Data Mining (SDM),2011.522-533.
[123]Goyal A, Bonchi F, Lakshmanan L. A data-based approach to social influence maximization. Proceedings of the VLDB Endowment,2011,5(1):73-84.
[124]Tang J, Sun J, Wang C, et al. Social influence analysis in large-scale networks. Proceedings of Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2009.807-816.
[125]Wang Y, Cong G, Song G, et al. Community-based greedy algorithm for mining top-k influ-ential nodes in mobile social networks. Proceedings of Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2010.1039-1048.
[126]Chen W, Lu W, Zhang N. Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process. Proceedings of Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AAAI Press,2012.
[127]Goyal A, Bonchi F, Lakshmanan L. Approximation analysis of influence spread in social networks. Arxiv preprint arXiv:1008.2005,2010..
[2]Granovetter M. Threshold models of collective behavior. American journal of sociology,1978. 1420-1443.
[3]Xiang B, Chen E, Liu Q, et al. A Social Influence Model Based On Circuit Theory. arXiv preprint arXiv:1205.6024,2012..
[4]A Linear Circuit Model For Social Influence. arXiv preprint arXiv:1206.1105,2012..
[5]Page L, Brin S, Motwani R, et al. The PageRank citation ranking:Bringing order to the web. Proceedings of Proceedings of WWW Conference. Stanford InfoLab,1999.
[6]Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network. Proceedings of Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2003.137-146.
[7]Borodin A, Roberts G O, Rosenthal J S, et al. Link analysis ranking:algorithms, theory, and experiments. ACM Transactions on Internet Technology (TOIT),2005,5(1):231-297.
[8]Chakrabarti S, Dom B E, Kumar S R, et al. Mining the Web's link structure. Computer,1999, 32(8):60-67.
[9]McGlohon M, Akoglu L, Faloutsos C. Weighted graphs and disconnected components:patterns and a generator. Proceedings of Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.524-532.
[10]Chakrabarti S. Dynamic personalized pagerank in entity-relation graphs. Proceedings of Proceed-ings of the 16th international conference on World Wide Web. ACM,2007.571-580.
[11]Albert R, Jeong H, Barabasi A L. Internet:Diameter of the world-wide web. Nature,1999, 401 (6749):130-131.
[12]Mackay R. Linked:How Everything is Connected to Everything Else and What It Means for Business, Science and Everyday Life. Complicity:An International Journal of Complexity and Education,2005,2(1).
[13]Watts D J, Strogatz S H. Collective dynamics of j(?)mall-worldj-networks. nature,1998, 393(6684):440-442.
[14]Mihail M, Papadimitriou C. On the eigenvalue power law. Proceedings of Randomization and approximation techniques in computer science. Springer,2002:254-262.
[15]Siganos G, Faloutsos M, Faloutsos P, et al. Power laws and the AS-level internet topology. IEEE/ACM Transactions on Networking (TON),2003, 11(4):514-524.
[16]Langville A, Meyer C. Deeper inside pagerank. Internet Mathematics,2004, 1(3):335-380.
[17]Agarwal A, Chakrabarti S, Aggarwal S. Learning to rank networked entities. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2006.14-23.
[18]Koren Y, North S C, Volinsky C. Measuring and extracting proximity in networks. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2006.245-255.
[19]Fogaras D, Racz B. Scaling link-based similarity search. Proceedings of Proceedings of the 14th international conference on World Wide Web. ACM,2005.641-650.
[20]Doyle P G, Snell J L. Random walks and electric networks. arXiv preprint math.PR/0001057, 2000,3.
[21]Lovasz L. Random walks on graphs:A survey. Combinatorics, Paul erdos is eighty,1993,2(1):1-46.
[22]Agarwal A, Chakrabarti S. Learning random walks to rank nodes in graphs. Proceedings of Proceedings of the 24th international conference on Machine learning. ACM,2007.9-16.
[23]Haveliwala T. Topic-sensitive pagerank:A context-sensitive ranking algorithm for web search. IEEE Transactions on Knowledge and Data Engineering,2003,15(4):784-796.
[24]Fogaras D, Racz B, Csalogany K, et al. Towards scaling fully personalized pagerank:Algorithms, lower bounds, and experiments. Internet Mathematics,2005,2(3):333-358.
[25]Boley D, Ranjan G, Zhang Z L. Commute times for a directed graph using an asymmetric Laplacian. Linear Algebra and its Applications,2011,435 (2):224-242.
[26]Hopcroft J, Sheldon D. Manipulation-resistant reputations using hitting time. Proceedings of Algorithms and Models for the Web-Graph. Springer,2007:68-81.
[27]Katz L. A new status index derived from sociometric analysis. Psychometrika,1953,18(1):39-43.
[28]Zhu X, Lafferty J. Harmonic mixtures:combining mixture models and graph-based method-s for inductive and scalable semi-supervised learning. Proceedings of Proceedings of the 22nd international conference on Machine learning. ACM,2005.1052-1059,
[29]Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using gaussian fields and harmon-ic functions. Proceedings of MACHINE LEARNING-INTERNATIONAL WORKSHOP THEN CONFERENCE-, volume 20,2003.912.
[30]Smola A J, Kondor R. Kernels and regularization on graphs. Proceedings of Learning theory and kernel machines. Springer,2003:144-158.
[31]Dalvi B B, Kshirsagar M, Sudarshan S. Keyword search on external memory data graphs. Pro-ceedings of the VLDB Endowment,2008, 1(1):1189-1204.
[32]Balmin A, Hristidis V, Papakonstantinou Y. Objectrank:Authority-based keyword search in databases. Proceedings of Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004.564-575.
[33]Mei Q, Zhou D, Church K. Query suggestion using hitting time. Proceedings of Proceedings of the 17th ACM conference on Information and knowledge management. ACM,2008.469-478.
[34]Qiu H, Hancock E R. Robust multi-body motion tracking using commute time clustering. Pro-ceedings of Computer Vision-ECCV 2006. Springer,2006:160-173.
[35]Shi J, Malik J. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelli-gence, IEEE Transactions on,2000,22(8):888-905.
[36]Grady L. Random walks for image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on,2006,28(11):1768-1783.
[37]Levin A, Lischinski D, Weiss Y. Colorization using optimization. Proceedings of ACM Transactions on Graphics (TOG), volume 23. ACM,2004.689-694.
[38]Lafferty J, Zhai C. Document language models, query models, and risk minimization for informa-tion retrieval. Proceedings of Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval. ACM,2001.111-119.
[39]Chakrabarti D, Faloutsos C. Graph mining:Laws, generators, and algorithms. ACM Computing Surveys (CSUR),2006,38(1):2.
[40]Leskovec J, Lang K J, Dasgupta A, et al. Statistical properties of community structure in large social and information networks. Proceedings of Proceedings of the 17th international conference on World Wide Web. ACM,2008.695-704.
[41]Buehrer G, Chellapilla K. A scalable pattern mining approach to web graph compression with communities. Proceedings of Proceedings of the 2008 International Conference on Web Search and Data Mining. ACM,2008.95-106.
[42]Brohee S, Helden J. Evaluation of clustering algorithms for protein-protein interaction networks. BMC bioinformatics,2006,7(1):488.
[43]Kaufman L, Rousseeuw P J. Finding groups in data:an introduction to cluster analysis, volume 344. Wiley-Interscience,2009.
[44]Chakrabarti D, Kumar R, Tomkins A. Evolutionary clustering. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2006.554-560.
[45]Berger-Wolf T Y, Saia J. A framework for analysis of dynamic social networks. Proceedings of Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2006.523-528.
[46]Kernighan B, Lin S. An eflicient heuristic procedure for partitioning graphs. Bell system technical journal,1970..
[47]Brandes U, Delling D, Gaertler M, et al. On finding graph clusterings with maximum modularity. Proceedings of Graph-Theoretic Concepts in Computer Science. Springer,2007.121-132.
[48]Clauset A, Newman M E, Moore C. Finding community structure in very large networks. Physical review E,2004,70(6):066111.
[49]Girvan M, Newman M E. Community structure in social and biological networks. Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[50]Leicht E A, Newman M E. Community structure in directed networks. Physical review letters, 2008,100(11):118703.
[51]Xiang B, Chen E H, Zhou T. Finding community structure based on subgraph similarity. Pro-ceedings of Complex Networks. Springer,2009:73-81.
[52]Chung F R. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No.92). 1997..
[53]Andersen R, Chung F, Lang K. Local graph partitioning using pagerank vectors. Proceedings of Foundations of Computer Science,2006. FOCS'06.47th Annual IEEE Symposium on. IEEE, 2006.475-486.
[54]Barnard S T, Simon H D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency:Practice and Experience,1994,6(2):101-117.
[55]Azran A. The rendezvous algorithm:Multiclass semi-supervised learning with markov random walks. Proceedings of Proceedings of the 24th international conference on Machine learning. ACM, 2007.49-56.
[56]Baluja S, Seth R, Sivakumar D, et al. Video suggestion and discovery for youtube:taking random walks through the view graph. Proceedings of Proceedings of the 17th international conference on World Wide Web. ACM,2008.895-904.
[57]Chapelle O, Zien A, et al. Label Propagation and Quadratic Criterion..
[58]Bhagat S, Rozenbaum I, Cormode G. Applying link-based classification to label blogs. Proceedings of Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis. ACM,2007.92-101.
[59]Blum A, Chawla S. Learning from labeled and unlabeled data using graph mincuts.2001..
[60]Kleinberg.J, Tardos E, Approximation algorithms for classification problems with pairwise rela-tionships:Metric labeling and Markov random fields. Proceedings of Foundations of Computer Science,1999.40th Annual Symposium on. IEEE,1999.14-23.
[61]Lu Q, Getoor L. Link-based classification. Proceedings of MACHINE LEARNING-INTERNATIONAL WORKSHOP THEN CONFERENCE-, volume 20,2003,496.
[62]Jaakkola M S T. Partially labeled classification with Markov random walks. Proceedings of Advances in Neural Information Processing Systems 14:Proceedings of the 2002 Conference, volume 2. MIT Press,2002.945.
[63]Zhou D, Bousquet O, Lal T N, et al. Learning with local and global consistency. Advances in neural information processing systems,2004,16(753760):284.
[64]Zhou Y, Cheng H, Yu J X. Graph clustering based on structural/attribute similarities. Proceedings of the VLDB Endowment,2009,2(1):718-729.
[65]Chakrabarti S, Dom B, Indyk P. Enhanced hypertext categorization using hyperlinks. Proceedings of ACM SIGMOD Record, volume 27. ACM,1998.307-318.
[66]Goyal A, Bonchi F, Lakshmanan L V. Learning influence probabilities in social networks. Proceed-ings of Proceedings of the third ACM international conference on Web search and data mining. ACM,2010.241-250.
[67]Sen P, Namata G, Bilgic M, et al. Collective classification in network data. AI magazine,2008, 29(3):93.
[68]Ahmed A, Xing E P. Recovering time-varying networks of dependencies in social and biological studies. Proceedings of the National Academy of Sciences,2009,106(29):11878-11883.
[69]Asur S, Parthasarathy S, Ucar D. An event-based framework for characterizing the evolutionary behavior of interaction graphs. Proceedings of Proceedings of the 13th ACM SIGKDD interna-tional conference on Knowledge discovery and data mining. ACM,2007.913-921.
[70]Kumar R, Novak J, Tomkins A. Structure and evolution of online social networks. Proceedings of Link Mining:Models, Algorithms, and Applications. Springer,2010:337-357.
[71]Leskovec J, Backstrom L, Kumar R, et al. Microscopic evolution of social networks. Proceedings of Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.462-470.
[72]Lin Y R, Chi Y, Zhu S, et al. Analyzing communities and their evolutions in dynamic social networks. ACM Transactions on Knowledge Discovery from Data (TKDD),2009,3(2):8.
[73]Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution. Nature,2007, 446(7136):664-667.
[74]Aggarwal C C, Yu P. Online analysis of community evolution in data streams. Proceedings of Proceedings of the SIAM International Conference on Data Mining (SDM 2005),2005.56-67.
[75]Ferlez J, Faloutsos C, Leskovec J, et al. Monitoring network evolution using MDL. Proceedings of Data Engineering,2008. ICDE 2008. IEEE 24th International Conference on. IEEE,2008. 1328-1330.
[76]Tantipathananandh C, Berger-Wolf T, Kempe D. A framework for community identification in dynamic social networks. Proceedings of Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2007.717-726.
[77]Toyoda M, Kitsuregawa M. Extracting evolution of web communities from a series of web archives. Proceedings of Proceedings of the fourteenth ACM conference on Hypertext and hypermedia. ACM,2003.28-37.
[78]Adamic L A, Adar E. Friends and neighbors on the web. Social networks,2003,25(3):211-230.
[79]Bilgic M, Namata G M, Getoor L. Combining collective classification and link prediction. Pro-ceedings of Data Mining Workshops,2007. ICDM Workshops 2007. Seventh IEEE International Conference on. IEEE,2007.381-386.
[80]Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American society for information science and technology,2007,58(7):1019-1031.
[81]Sarukkai R R. Link prediction and path analysis using Markov chains. Computer Networks,2000, 33(1):377-386.
[82]Herman I, Melangon G, Marshall M S. Graph visualization and navigation in information visual-ization:A survey. Visualization and Computer Graphics, IEEE Transactions on,2000,6(1):24-43.
[83]Henry N, Fekete J D, McGuffin M J. NodeTrix:a hybrid visualization of social networks. Visu-alization and Computer Graphics, IEEE Transactions on,2007,13(6):1302-1309.
[84]Freeman L C. Visualizing social networks. Journal of social structure,2000,1(1):4.
[85]Bertini E, Lalanne D. Surveying the complementary role of automatic data analysis and visu-alization in knowledge discovery. Proceedings of Proceedings of the ACM SIGKDD Workshop on Visual Analytics and Knowledge Discovery:Integrating Automated Analysis with Interactive Exploration. ACM,2009.12-20.
[86]Brandes U, Pich C. An experimental study on distance-based graph drawing. Proceedings of Graph Drawing. Springer,2009.218-229.
[87]Brandes U, Kenis P, Raab J, et al. Explorations into the visualization of policy networks. Journal of Theoretical Politics,1999, 11(1):75-106.
[88]Dwyer T, Hong S H, Koschiitzki D, et al. Visual analysis of network centralities. Proceedings of Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation-Volume 60. Aus-tralian Computer Society, Inc.,2006.189-197.
[89]Holten D. Hierarchical edge bundles:Visualization of adjacency relations in hierarchical data. Visualization and Computer Graphics, IEEE Transactions on,2006,12(5):741-748.
[90]Jia Y, Hoberock J, Garland M, et al. On the visualization of social and other scale-free networks. Visualization and Computer Graphics, IEEE Transactions on,2008,14(6):1285-1292.
[91]Aris A, Shneiderman B. Designing semantic substrates for visual network exploration. Information Visualization,2007,6(4):281-300.
[92]Perer A, Shneiderman B. Integrating statistics and visualization:case studies of gaining clarity during exploratory data analysis. Proceedings of Proceedings of the twenty-sixth annual SIGCHI conference on Human factors in computing systems. ACM,2008.265-274.
[93]Kang H, Getoor L, Singh L. Visual analysis of dynamic group membership in temporal social networks. ACM SIGKDD Explorations Newsletter,2007,9(2):13-21.
[94]Moody J, McFarland D, Bender-deMoll S. Dynamic network visualizationl. American Journal of Sociology,2005,110(4):1206-1241.
[95]Aggarwal C. Social network data analytics. Springer-Verlag New York Inc,2011.
[96]Anagnostopoulos A, Kumar R, Mahdian M. Influence and correlation in social networks. Proceed-ings of Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.7-15.
[97]Aral S, Muchnik L, Sundararajan A. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proceedings of the National Academy of Sciences,2009, 106(51):21544-21549.
[98]Backstrom L, Kumar R, Marlow C, et al. Preferential behavior in online groups. Proceedings of Proceedings of the international conference on Web search and web data mining. ACM,2008. 117-128.
[99]Bakshy E, Karrer B, Adamic L A. Social influence and the diffusion of user-created content. Proceedings of Proceedings of the 10th ACM conference on Electronic commerce. ACM,2009. 325-334.
[100]Eastwick P W, Gardner W L. Is it a game? Evidence for social influence in the virtual world. Social Influence,2009,4(1):18-32.
[101]Bass F M. Comments on (?)A New Product Growth for Model Consumer Durables The Bass Modelj±. Management science,2004,50(12 supplement):1833-1840.
[102]Hartline J, Mirrokni V, Sundararajan M. Optimal marketing strategies over social networks. Proceedings of Proceedings of the 17th international conference on World Wide Web. ACM,2008. 189-198.
[103]Provost F, Dalessandro B, Hook R, et al. Audience selection for on-line brand advertising:privacy-friendly social network targeting. Proceedings of Proceedings of the 15th ACM SIGKDD interna-tional conference on Knowledge discovery and data mining. ACM,2009.707-716.
[104]Brown J J, Reingen P H. Social ties and word-of-mouth referral behavior. Journal of Consumer Research,1987.350-362.
[105]Chen W, Wang Y, Yang S. Efficient influence maximization in social networks. Proceedings of Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2009.199-208.
[106]Cialdini R B, Goldstein N J. Social influence:Compliance and conformity. Annu. Rev. Psychol., 2004,55:591-621.
[107]Crandall D, Cosley D, Huttenlocher D, et al. Feedback effects between similarity and social influ-ence in online communities. Proceedings of Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2008.160-168.
[108]La Fond T, Neville J. Randomization tests for distinguishing social influence and homophily effects. Proceedings of Proceedings of the 19th international conference on World wide web. ACM,2010. 601-610.
[109]Manavoglu E, Pavlov D, Giles C L. Probabilistic user behavior models. Proceedings of Data Mining,2003. ICDM 2003. Third IEEE International Conference on. IEEE,2003.203-210.
[110]Domingos P, Richardson M. Mining the network value of customers. Proceedings of Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2001.57-66.
[111]Java A, Kolari P, Finin T, et al. Modeling the spread of influence on the blogosphere. Proceedings of Proceedings of the 15th international world wide web conference,2006.22-26.
[112]Goyal A, Bonchi F, Lakshmanan L V. Discovering leaders from community actions. Proceedings of Proceedings of the 17th ACM conference on Information and knowledge management. ACM, 2008.499-508.
[113]Aggarwal C, Khan A, Yan X. On Flow Authority Discovery in Social Networks. Proceedings of Proceedings of the SDM Conference,2011.
[114]Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks. Proceedings of Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2010.1029-1038.
[115]Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks. Proceedings of Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2007.420-429.
[116]Yang Y, Chen E, Liu Q, et al. On Approximation of Real-World InuenceSpread. Proceedings of The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (PKDD),2012. xxx-xxx.
[117]BIANCHINI M, GORI M, SCARSELLI F. Inside PageRank. ACM Transactions on Internet Technology,2005,5(1):92-128.
[118]Ding Y, Yan E, Frazho A, et al. PageRank for ranking authors in co-citation networks. Journal of the American Society for Information Science and Technology,2009,60(11):2229-2243.
[119]Ding Y. Topic-based PageRank on author cocitation networks. Journal of the American Society for Information Science and Technology,2011,62(3):449-466.
[120]Liu Q, Xiang B, Chen E, et al. Influential seed items recommendation. Proceedings of Proceedings of the sixth ACM conference on Recommender systems. ACM,2012.245-248.
[121]Zhu H, Cao H, Xiong H, et al. Towards expert finding by leveraging relevant categories in authority ranking. Proceedings of Proceedings of the 20th ACM international conference on Information and knowledge management. ACM,2011.2221-2224.
[122]Aggarwal C, Khan A, Yan X. On flow authority discovery in social networks. Proceedings of Proceedings of SIAM Conference on Data Mining (SDM),2011.522-533.
[123]Goyal A, Bonchi F, Lakshmanan L. A data-based approach to social influence maximization. Proceedings of the VLDB Endowment,2011,5(1):73-84.
[124]Tang J, Sun J, Wang C, et al. Social influence analysis in large-scale networks. Proceedings of Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2009.807-816.
[125]Wang Y, Cong G, Song G, et al. Community-based greedy algorithm for mining top-k influ-ential nodes in mobile social networks. Proceedings of Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2010.1039-1048.
[126]Chen W, Lu W, Zhang N. Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process. Proceedings of Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AAAI Press,2012.
[127]Goyal A, Bonchi F, Lakshmanan L. Approximation analysis of influence spread in social networks. Arxiv preprint arXiv:1008.2005,2010..