Review of Social Marketing Performance Maximization Problem and Its Extension

LIU Yezheng; LI Lingfei; JIANG Yuanchun

doi:10.11999/JEIT160517

Volume 38 Issue 9

Sep. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(9): 2130-2140

LIU Yezheng, LI Lingfei, JIANG Yuanchun. Review of Social Marketing Performance Maximization Problem and Its Extension[J]. Journal of Electronics & Information Technology, 2016, 38(9): 2130-2140. doi: 10.11999/JEIT160517

Citation:

LIU Yezheng, LI Lingfei, JIANG Yuanchun. Review of Social Marketing Performance Maximization Problem and Its Extension[J]. Journal of Electronics & Information Technology, 2016, 38(9): 2130-2140. doi: 10.11999/JEIT160517

Citation:

PDF( 280 KB)

Review of Social Marketing Performance Maximization Problem and Its Extension

doi: 10.11999/JEIT160517

Funds:

The Major Program of the National Natural Science Foundation of China (71490725), The National 973 Program of China (2013CB329603), The National Natural Science Foundation of China (71371062, 91546114, 71302064, 71501057),The National Key Technology Support Program (2015BAH26F00)

Received Date: 2016-05-23
Rev Recd Date: 2016-07-18
Publish Date: 2016-09-19

Abstract

Abstract

Many enterprises try to promote their products in online social network since information propagation in this network have several advantages such as fast transmission speed, low marketing costs, and large influence area. However, it is a challenging task for enterprises to select suitable seed nodes to publish marketing information so that marketing information can influence or cover most users under a given cost and realize performance maximization. By means of literature search and review, this paper systematically summarizes information propagation models in social marketing, introduces algorithms for social marketing performance maximization problem with respect to network topology, user historical data, compete and non-compete condition. Finally, this paper concludes an exploration of future directions of this research filed.
- Online social network,
- Social marketing,
- Performance maximization

FullText(HTML)

References(96)

References

DENRELL J. SOCIOLOGY: Indirect social influence[J]. Science, 2008, 321(5885): 47-48. doi: 10.1126/science. 1157667.

MUCHNIK L, ARAL S, and TAYLOR S J. Social influence bias: A randomized experiment[J]. Science, 2013, 341(6146): 647-651. doi: 10.1126/science.1240466.

SUN Tao, CHEN Wei, LIU Zhenming, et al. Participation maximization based on social influence in online discussion forums[C]. The 5th International AAAI Conference on Web and Social Media (ICWSM), Barcelona, 2011: 361-368.

BANERJEE A, CHANDRASEKHAR A G, DUFLO E, et al. The diffusion of microfinance[J]. Science, 2013, 341(6144): 1236498. doi: 10.1126/science.1236498.

BOND R M, FARISS C J, JONES J J, et al. A 61-million-person experiment in social influence and political mobilization[J]. Nature, 2012, 489(7415): 295-298. doi: 10.1038/nature11421.

ARAL S. Social science: poked to vote[J]. Nature, 2012, 489(7415): 212-214. doi: 10.1038/489212a.

ARAL S and WALKER D. Tie strength, embeddedness, and social influence: A large-scale networked experiment[J]. Management Science, 2014, 60(6): 1352-1370. doi: 10.1287/ mnsc.2014.1936.

LEE Youngjin, HOSANAGAR K, and TAN Y. Do I follow my friends or the crowd? information cascades in online movie ratings[J]. Management Science, 2015, 61(9): 2241-2258. doi: 10.1287/mnsc.2014.2082.

LEWIS K, GONZALEZ M, and KAUFMAN J. Social selection and peer influence in an online social network[J]. Proceedings of the National Academy of Sciences, 2012, 109(1): 68-72. doi: 10.1073/pnas.1109739109.

MORONE F and MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524(7563): 65-68. doi: 10.1038/nature14604.

MOE W W and SCHWEIDEL D A. Online product opinions: incidence, evaluation, and evolution[J]. Marketing Science, 2012, 31(3): 372-386. doi: 10.1287/mksc.1110.0662.

TUCKER C E. The reach and persuasiveness of viral video ads[J]. Marketing Science, 2014, 34(2): 281-296. doi: 10.1287/ mksc.2014.0874.

GODINHO DE MATOS M, FERREIRA P, and KRACKHARDT D. Peer influence in the diffusion of the iPhone 3G over a large social network[J]. Management Information Systems Quarterly (Forthcoming), 2014, 38(4): 1103-1133. doi: 10.2139/ssrn.2053420.

GU Bin, KONANA P, RAGHUNATHAN R, et al. Research note-the allure of homophily in social media: Evidence from investor responses on virtual communities[J]. Information Systems Research, 2014, 25(3): 604-617. doi: 10.1287/isre. 2014.0531.

KEMPE D, KLEINBERG J, and TARDOS. Maximizing the spread of influence through a social network[C]. Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2003: 137-146. doi: 10.1145/956750.956769.

DOMINGOS P and RICHARDSON M. Mining the network value of customers[C]. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2001: 57-66. doi: 10.1145/ 502512.502525.

RICHARDSON M and DOMINGOS P. Mining knowledge- sharing sites for viral marketing[C]. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2002: 61-70. doi: 10.1145/775047.775057.

CHEN Wei, WANG Yajun, and YANG Siyu. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2009: 199-208. doi: 10.1145/1557019.1557047.

WATTS D J. A simple model of global cascades on random networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(9): 5766-5771. doi: 10.1073/pnas.082090499.

MYERS S A, ZHU Chenguang, and LESKOVEC J. Information diffusion and external influence in networks[C]. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2012: 33-41. doi: 10.1145/2339530.2339540.

NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256. doi : 10.1137/S003614450342480.

YANG J and LESKOVEC J. Modeling information diffusion in implicit networks[C]. 2010 IEEE International Conference on Data Mining, Sydney, 2010: 599-608. doi: 10.1109/ ICDM.2010.22.

GOLDENBERG J, LIBAI B, and MULLER E. Talk of the network: A complex systems look at the underlying process of word-of-mouth[J]. Marketing Letters, 2001, 12(3): 211-223. doi: 10.1023/A:1011122126881.

GOLDENBERG J, LIBAI B, and MULLER E. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata[J]. Academy of Marketing Science Review, 2001, 9(3): 1-18.

KEMPE D, KLEINBERG J, and TARDOS. Influential Nodes in a Diffusion Model for Social Networks[M]. Lisbon: Springer, 2005: 1127-1138.

KIMURA M, SAITO K, NAKANO R, et al. Extracting influential nodes on a social network for information diffusion[J]. Data Mining and Knowledge Discovery, 2010, 20(1): 70-97. doi: 10.1007/s10618-009-0150-5.

KIMURA M and SAITO K. Tractable Models for Information Diffusion in Social Networks[M]. Berlin: Springer, 2006: 259-271.

EVEN-DAR E and SHAPIRA A. A Note on Maximizing the Spread of Influence in Social Networks[M]. San Diego: Springer, 2007: 281-286.

MA Hao, YANG Haixuan, LYU M R, et al. Mining social networks using heat diffusion processes for marketing candidates selection[C]. Proceedings of the 17th ACM Conference on Information and Knowledge Management, New York, 2008: 233-242. doi: 10.1145/1458082.1458115.

CENTOLA D. The spread of behavior in an online social network experiment[J]. Science, 2010, 329(5996): 1194-1197. doi: 10.1126/science.1189910.

ARAL S, MUCHNIK L, and SUNDARARAJAN A. Distinguishing influence-based contagion from homophily- driven diffusion in dynamic networks[J]. Proceedings of the National Academy of Sciences, 2009, 106(51): 21544-21549. doi: 10.1073/pnas.0908800106.

ARAL S and WALKER D. Identifying influential and susceptible members of social networks[J]. Science, 2012, 337(6092): 337-341. doi: 10.1126/science.1215842.

CHEN Wei, WANG Chi, and WANG Yajun. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2010: 1029-1038. doi: 10.1145/ 1835804.1835934.

CHEN Wei, YUAN Yifei, and ZHANG Li. Scalable influence maximization in social networks under the linear threshold model[C]. 2010 IEEE 10th International Conference on Data Mining (ICDM), Sydney, 2010: 88-97. doi: 10.1109/ICDM. 2010.118.

NEMHAUSER G L, WOLSEY L A, and FISHER M L. An analysis of approximations for maximizing submodular set functionsI[J]. Mathematical Programming, 1978, 14(1): 265-294. doi: 10.1007/BF01588971.

LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost- effective outbreak detection in networks[C]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2007: 420-429. doi: 10.1145/1281192.1281239.

GOYAL A, LU Wei, and LAKSHMANAN L V S. Celf++: Optimizing the greedy algorithm for influence maximization in social networks[C]. Proceedings of the 20th International Conference Companion on World Wide Web, New York, 2011: 47-48. doi: 10.1145/1963192.1963217.

GIRVAN M and NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826. doi: 10.1073/ pnas.122653799.

WANG Yu, CONG Gao, SONG Guojie, et al. Community- based greedy algorithm for mining top-k influential nodes in mobile social networks[C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2010: 1039-1048. doi: 10.1145/ 1835804.1835935.

SONG Guojie, ZHOU Xiabing, WANG Yu, et al. Influence maximization on large-scale mobile social network: A divide-and-conquer method[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(5): 1379-1392. doi: 10.1109/TPDS.2014.2320515.

BORGS C, BRAUTBAR M, CHAYES J, et al. Maximizing social influence in nearly optimal time[C]. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, 2014: 946-957. doi: 10.1137/ 1.9781611973402.70.

TANG Youze, XIAO Xiaokui, and SHI Yanchen. Influence maximization: Near-optimal time complexity meets practical efficiency[C]. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, New York, 2014: 75-86. doi: 10.1145/2588555.2593670.

COHEN E, DELLING D, PAJOR T, et al. Sketch-based influence maximization and computation: Scaling up with guarantees[C]. Proceedings of the 23rd ACM International Conference on Information and Knowledge Management, New York, 2014: 629-638. doi: 10.1145/2661829.2662077.

WANG Chi, CHEN Wei, and WANG Yajun. Scalable influence maximization for independent cascade model in large-scale social networks[J]. Data Mining and Knowledge Discovery, 2012, 25(3): 545-576. doi: 10.1007/s10618-012- 0262-1.

GOYAL A, LU W, and LAKSHMANAN L V S. Simpath: An efficient algorithm for influence maximization under the linear threshold model[C]. 2011 IEEE 11th International Conference on Data Mining (ICDM), Vancouver, 2011: 211-220. doi: 10.1109/ICDM.2011.132.

JUNG K, HEO W, and CHEN Wei. IRIE: Scalable and robust influence maximization in social networks[C]. 2012 IEEE 12th International Conference on Data Mining, Brussels, 2012: 918-923. doi: 10.1109/ICDM.2012.79.

KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893. doi: 10.1038/nphys1746.

NARAYANAM R and NARAHARI Y. A shapley value-based approach to discover influential nodes in social networks[J]. IEEE Transactions on Automation Science and Engineering, 2011, 8(1): 130-147. doi: 10.1109/TASE.2010.2052042.

JIANG Qingye, SONG Guojie, GAO Cong, et al. Simulated annealing based influence maximization in social networks[C]. Twenty-fifth AAAI Conference on Artificial Intelligence, San Francisco, USA, 2011, 11: 127-132.

LIU Xiaodong, LI Mo, LI Shanshan, et al. IMGPU: GPU- accelerated influence maximization in large-scale social networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 136-145. doi: 10.1109/TPDS.2013.41.

HE Xinran and KEMPE D. Stability of influence maximization[C]. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2014: 1256-1265. doi: 10.1145/2623330. 2623746.

ADIGA A, KUHLMAN C J, MORTVEIT H S, et al. Sensitivity of diffusion dynamics to network uncertainty[J]. Journal of Artificial Intelligence Research, 2014, 51: 207-226. doi: 10.1613/jair.4330.

SAITO K, NAKANO R, and KIMURA M. Prediction of information diffusion probabilities for independent cascade model[C]. Knowledge-Based Intelligent Information and Engineering Systems, Zagreb, 2008: 67-75. doi: 10.1007/978- 3-540-85567-5_9.

GOYAL A, BONCHI F, and LAKSHMANAN L V S. Learning influence probabilities in social networks[C]. Proceedings of the Third ACM International Conference on Web Search and Data Mining, New York, 2010: 241-250. doi: 10.1145/1718487.1718518.

GOYAL A, BONCHI F, and LAKSHMANAN L V S. A data-based approach to social influence maximization[J]. Proceedings of the VLDB Endowment, 2011, 5(1): 73-84. doi: 10.14778/2047485.2047492.

GRANOVETTER M S. The strength of weak ties[J]. American Journal of Sociology, 1973, 78(6): 1360-1380.

KRACKHARDT D. The strength of strong ties: The importance of philos in organizations[J]. Networks and Organizations: Structure, Form, and Action, 1992, 216-239.

LIN C X, MEI Qiaozhu, HAN Jiawei, et al. The joint inference of topic diffusion and evolution in social communities[C]. 2011 IEEE 11th International Conference on Data Mining (ICDM), Vancouver, 2011: 378-387. doi: 10. 1109/ICDM.2011.144.

LIU Lu, TANG Jie, HAN Jiawei, et al. Mining topic-level influence in heterogeneous networks[C]. Proceedings of the 19th ACM International Conference on Information and Knowledge Management, New York, 2010: 199-208. doi: 10.1145/1871437.1871467.

TANG Jie, SUN Jimeng, WANG Chi, et al. Social influence analysis in large-scale networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2009: 807-816. doi: 10.1145/1557019.1557108.

LI Yungming and SHIU Yalin. A diffusion mechanism for social advertising over microblogs[J]. Decision Support Systems, 2012, 54(1): 9-22. doi: 10.1016/j.dss.2012.02.012.

BARBIERI N, BONCHI F, and MANCO G. Topic-aware social influence propagation models[J]. Knowledge and Information Systems, 2013, 37(3): 555-584. doi: 10.1007/ s10115-013-0646-6.

ASLAY C, BARBIERI N, BONCHI F, et al. Online topic- aware influence maximization queries[C]. 17th International Conference on Extending Database Technology, Athens, 2014: 295-306.

CHEN Wei, LIN Tian, and YANG Cheng. Real-time topic-aware influence maximization using preprocessing[C]. International Conference on Computational Social Networks. Beijing, 2015: 1-13. doi: 10.1007/978-3-319-21786-4_1.

CHEN Shuo, FAN Ju, LI Guoliang, et al. Online topic-aware influence maximization[J]. Proceedings of the VLDB Endowment, 2015, 8(6): 666-677. doi: 10.14778/2735703. 2735706.

LI Yuchen, ZHANG Dongxiang, and TAN Kianlee. Real-time targeted influence maximization for online advertisements[J]. Proceedings of the VLDB Endowment, 2015, 8(10): 1070-1081. doi: 10.14778/2794367.2794376.

DUBEY P, GARG R, and DE MEYER B. Competing for Customers in a Social Network: The Quasi-linear Case[M]. Patras: Springer, 2006: 162-173.

CARNES T, NAGARAJAN C, WILD S M, et al. Maximizing influence in a competitive social network: A follower's perspective[C]. Proceedings of the Ninth International Conference on Electronic Commerce, New York, 2007: 351-360. doi: 10.1145/1282100.1282167.

BHARATHI S, KEMPE D, and SALEK M. Competitive Influence Maximization in Social Networks[M]. San Diego: Springer, 2007: 306-311.

KOSTKA J, OSWALD Y A, and WATTENHOFER R. Word of Mouth: Rumor Dissemination in Social Networks[M]. Villars-sur-Ollon, Switzerland: Springer, 2008: 185-196.

PATHAK N, BANERJEE A, and SRIVASTAVA J. A generalized linear threshold model for multiple cascades[C]. 2010 IEEE 10th International Conference on Data Mining (ICDM), Sydney, 2010: 965-970. doi: 10.1109/ICDM.2010. 153.

TRPEVSKI D, TANG W K S, and KOCAREV L. Model for rumor spreading over networks[J]. Physical Review E, 2010, 81(5): 056102. doi: 10.1103/PhysRevE.81.056102.

LI Hui, BHOWMICK S S, CUI Jiangtao, et al. GetReal: Towards realistic selection of influence maximization strategies in competitive networks[C]. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, New York, 2015: 1525-1537. doi: 10.1145/2723372.2723710.

GOYAL S, HEIDARI H, and KEARNS M. Competitive contagion in networks[J]. Games and Economic Behavior, 2014. doi: 10.1016/j.geb.2014.09.002.

CHAOJI V, RANU S, RASTOGI R, et al. Recommendations to boost content spread in social networks[C]. Proceedings of the 21st International Conference on World Wide Web, New York, 2012: 529-538. doi: 10.1145/2187836.2187908.

KATONA Z, ZUBCSEK P P, and SARVARY M. Network effects and personal influences: The diffusion of an online social network[J]. Journal of Marketing Research, 2011, 48(3): 425-443. doi: 10.1509/jmkr.48.3.425.

DRAIEF M, HEIDARI H, and KEARNS M. New models for competitive contagion[C]. Twenty-eighth AAAI Conference on Artificial Intelligence, Qubec, 2014: 637-644.

BUDAK C, AGRAWAL D, and EL ABBADI A. Limiting the spread of misinformation in social networks[C]. Proceedings of the 20th International Conference on World Wide Web, New York, 2011: 665-674. doi: 10.1145/1963405.1963499.

HE Xinran, SONG Guojie, CHEN Wei, et al. Influence blocking maximization in social networks under the competitive linear threshold model[C]. 9th VLDB Workshop on Secure Data Management, Istanbul, 2012: 463-474. doi: 10.1137/1.9781611972825.40.

TSAI J, NGUYEN T H, and TAMBE M. Security games for controlling contagion[C]. Twenty-sixth AAAI Conference on Artificial Intelligence, Toronto, 2012: 1241-1248.

CHEN Wei, COLLINS A, CUMMINGS R, et al. Influence maximization in social networks when negative opinions may emerge and propagate[C]. SIAM Conference on Data Mining, Mesa, Arizona, USA, 2011: 379-390. doi: 10.1137/1. 9781611972818.33.

LI Yanhua, CHEN Wei, WANG Yajun, et al. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships[C]. Proceedings of the Sixth ACM International Conference on Web Cearch and Data Mining, New York, 2013: 657-666. doi: 10.1145/2433396. 2433478.

GOYAL A, BONCHI F, LAKSHMANAN L V S, et al. On minimizing budget and time in influence propagation over social networks[J]. Social Network Analysis and Mining, 2013, 3(2): 179-192. doi: 10.1007/s13278-012-0062-z.

CHEN Wei, LU Wei, and ZHANG Ning. Time-critical influence maximization in social networks with time-delayed diffusion process[C]. The Twenty-sixth AAAI Conference on Artificial Intelligence, Toronto, 2012: 592-598.

LIU Bo, CONG Gao, ZENG Yifeng, et al. Influence spreading path and its application to the time constrained social influence maximization problem and beyond[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1904-1917. doi: 10.1109/TKDE.2013.106.

KIM J, LEE W, and YU H. CT-IC: Continuously activated and time-restricted independent cascade model for viral marketing[J]. Knowledge-based Systems, 2014, 62: 57-68. doi: 10.1016/j.knosys.2014.02.013.

RODRIGUEZ M G and SCH LKOPF B. Influence maximization in continuous time diffusion networks[C]. Proceeding of the Twenty-ninth International Conference on Machine Learning, Edinburgh, 2012: 313-320. doi: 10.1145/ 2824253.

DU Nan, SONG Le, GOMEZ-RODRIGUEZ Manuel, et al. Scalable influence estimation in continuous-time diffusion networks[C]. Advances in Neural Information Processing Systems, Harrahs and Harveys, 2013: 3147-3155.

LONG Cheng and WONG R C W. Minimizing seed set for viral marketing[C]. 2011 IEEE 11th International Conference on Data Mining (ICDM), Vancouver, 2011: 427-436. doi: 10.1109/ICDM.2011.99.

ZHANG Peng, CHEN Wei, SUN Xiaoming, et al. Minimizing seed set selection with probabilistic coverage guarantee in a social network[C]. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data

Mining, New York, 2014: 1306-1315. doi: 10.1145/2623330. 2623684.

IRIBARREN J L and MORO E. Impact of human activity patterns on the dynamics of information diffusion[J]. Physical Review Letters, 2009, 103(3): 038702. doi: 10.1103/PhysRev Lett.103.038702.

KARSAI M, KIVEL M, PAN R K, et al. Small but slow world: how network topology and burstiness slow down spreading[J]. Physical Review E, 2011, 83(2): 025102. doi: 10.1103/Phys RevE.83.025102.

RODRIGUEZ M G, BALDUZZI D, and SCH LKOPF B. Uncovering the temporal dynamics of diffusion networks[C]. Proceeding of the Twenty-eighth International Conference on Machine Learning, Bellevue, 2011: 561-568.

XIE Miao, YANG Qiusong, WANG Qing, et al. DynaDiffuse: A dynamic diffusion model for continuous time constrained influence maximization[C]. Twenty-ninth AAAI Conference on Artificial Intelligence, Austin, Texas, 2015: 346-352.

GOMEZ RODRIGUEZ M, LESKOVEC J, and KRAUSE A. Inferring networks of diffusion and influence[C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2010: 1019-1028. doi: 10.1145/1835804.1835933.

Relative Articles

Supplements(0)

Cited By

Proportional views