nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2019 | Original Article

Influence maximization in graph-based OLAP (GOLAP)

verfasst von: Jenny Jin, Guigang Zhang, Phillip Sheu, Masahiro Hayakawa, Atsushi Kitazawa

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The notion of influence among people or organizations has been the core conceptual basis for making various decisions. With the increasing availability of datasets in various domains such as social networks and digital healthcare, it becomes more feasible to apply complex analytics on influence networks. In this paper, we present a comprehensive approach to managing influence networks using a set of extended graph models, called graph-based OLAP (GOLAP). The design space for GOLAP is defined by the incorporation of node types (i.e., colors), weights on relationships (i.e., edges), constraints on the number of nodes for a certain node type and constraints on the percentage of nodes for a certain node type. We begin with defining a method to find a strongest influence path (SIP) which is the strongest path from the source node to the target node. We can answer complex queries on influence networks such as “find an SIP with t nodes of color c” or “find an SIP with t% nodes of color c.” Based on the SIP model, we present a set of influence maximization methods which find a set of s seed nodes that can influence the whole graph maximally with various constraints such as having ‘t nodes of color c’. We also address methods for optimizing the time complexity of the analytics algorithms. We apply heuristic-based and graph reduction-based methods to reduce the time complexity. In addition to proving the proposed methods, we present the result of our implementation on the methods.

Vorheriger Artikel Correction to: Characterising and evaluating dynamic online communities from live microblogging user interactions

Nächster Artikel Diversified top-k search with relaxed graph simulation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Agarwal N, Liu H, Tang L, Yu PS (2008) Identifying the influential bloggers in a community. In: WSDM’08, pp 207–217

Aini A, Salehipour A (2012) Speeding up the Floyd–Warshall algorithm for the cycled shortest path problem. Appl Math Lett 25:1MathSciNetCrossRef

Alshawi IS, Yan L, Pan W, Luo B (2012) Lifetime enhancement in wireless sensor networks using fuzzy approach and A-star algorithm. In: IET Conference on wireless sensor systems

Anagnostopoulos A, Kumar R, Mahdian M (2008) Influence and correlation in social networks. In: KDD’08, pp 7–15

Arif T (2015) The mathematics of social network analysis: metrics for academic social networks. Int J Comput Appl Technol Res 4(12):889–893

Bao Y, Wang X, Wang Z, Wu C, Lau FCM (2016) Online influence maximization in non-stationary social networks. In: 2016 IEEE/ACM 24th international symposium on quality of service (IWQoS), Beijing, pp 1–6

Bruckman A (2015) Influence maximization in social networks: considering both positive and negative relationships. In: 2015 International conference on collaboration technologies and systems (CTS), Atlanta, GA, pp 479–480

Cai JLZ, Yan M, Li Y (2016) Using crowdsourced data in location-based social networks to explore influence maximization. In: IEEE INFOCOM 2016—the 35th annual IEEE international conference on computer communications, San Francisco, CA, pp 1–9

Chang CW, Yeh MY, Chuang KT (2015) On influence maximization to target users in the presence of multiple acceptances. In: 2015 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), Paris, pp 1592–1593

Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of international conference on Knowledge discovery and data mining, pp 1029–1038

Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE international conference on data mining, Sydney, NSW, pp 88–97

Cheng C, Riley R, Kumar SPR, Garcia-Luna-Aceves JJ (1989) A loop-free extended Bellman–Ford routing protocol without bouncing effect. In: Proceedings of symposium proceedings on communications architectures & protocols, pp 224–236

Chou B, Kim M (2018) Graph online analytical processing. In: Encyclopedia with semantic computing

Cohen E (2016) Greedy maximization framework for graph-based influence functions. In: 2016 Fourth IEEE workshop on hot topics in web systems and technologies (HotWeb), Washington, DC, pp 29–35

Deng X, Pan Y, Wu Y, Gui J (2015) Credit distribution and influence maximization in online social networks using node features. In: 2015 12th international conference on fuzzy systems and knowledge discovery (FSKD), Zhangjiajie, pp 2093–2100

Dong X, Qian L, Huang L (2017) Short-term load forecasting in smart grid: a combined CNN and k-means clustering approach. In: 2017 IEEE international conference on big data and smart computing (BigComp), Jeju, pp 119–125

Fan Z, Sun Y (2016) Clustering of college students based on improved k-means algorithm. In: 2016 International computer symposium (ICS), Chiayi, pp 676–679

Gong M, Song C, Duan C, Ma L, Shen B (2016) An efficient memetic algorithm for influence maximization in social networks. IEEE Comput Intell Mag 11(3):22–33CrossRef

Goyal A, Bonchi F, Lakshmanan LV (2008) Discovering leaders from community actions. In: CIKM’08, pp 499–508

Goyal A, Bonchi F, Lakshmanan LV (2010) Learning influence probabilities in social networks. In: WSDM’10, pp 207–217

Goyal A, Lu W, Lakshmanan LVS (2011) SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: 2011 IEEE 11th international conference on data mining, Vancouver, BC, pp 211–220

Gu L (2016) A novel locality sensitive k-means clustering algorithm based on subtractive clustering. In: 2016 7th IEEE international conference on software engineering and service science (ICSESS), Beijing, pp 836–839

Han M, Li J, Cai Z, Han Q (2016) Privacy reserved influence maximization in GPS-enabled cyber-physical and online social networks. In: 2016 IEEE international conferences on big data and cloud computing (BDCloud), social computing and networking (SocialCom), sustainable computing and communications (SustainCom) (BDCloud-SocialCom-SustainCom), Atlanta, GA, pp 284–292

Hangal S, Maclean D, Lam MS, Heer J (2010) All friends are not equal: using weights in social graphs to improve search. In: Proceedings of the 4th SNA-KDD workshop’10 (SNA-KDD’10). ACM, Washington

Hao F, Zhu C, Chen M, Yang LT, Pei Z (2011) Influence strength aware diffusion models for dynamic influence maximization in social networks. In: 2011 International conference on internet of things and 4th international conference on cyber, physical and social computing, Dalian, pp 317–322

Hu H, Wen Y, Feng S (2018) Budget-efficient viral video distribution over online social networks: mining topic-aware influential users. IEEE Trans Circuits Syst Video Technol 28(3):759–771CrossRef

Jiang F, Jin S, Wu Y, Xu J (2014) A uniform framework for community detection via influence maximization in social networks. In: 2014 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM 2014), Beijing, pp 27–32

Johnson DB (1973) A note on Dijkstra’s shortest path algorithm. J ACM 20:3MathSciNetCrossRef

Kang C, Mlinaro C, Kraus S, Shavit Y, Subrahmanian VS (2012) In: IEEE/ACM international conference on advances in social networks analysis and mining, Turkey

Kempe D, Kleinberg J, Tardos E (2015) Maximizing the spread of influence through a social network. Proc Theory Comput 11(4):105–147MathSciNetCrossRef

Król D (2014) On modelling social propagation phenomenon. In: Asian conference on intelligent information and database systems, pp 227–236

Kumari A, Singh SN (2017) Online influence maximization using rapid continuous time independent cascade model. In: 2017 7th international conference on cloud computing, data science & engineering—confluence, Noida, India, pp 356–361

Kwak B, Song N, Miller LE (2005) Performance analysis of exponential backoff. In: Proceedings of 2005 IEEE/ACM transactions on networking, vol 13, no 2

Lee JR, Chung CW (2015) A query approach for influence maximization on specific users in social networks. IEEE Trans Knowl Data Eng 27(2):340–353CrossRef

Leskovec J, Faloutsos C (2006) Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 631–636

Li J, Yu Y (2012) Scalable influence maximization in social networks using the community discovery algorithm. In: 2012 Sixth international conference on genetic and evolutionary computing, Kitakushu, pp 284–287

Li P, Li Z, He J, Du X, Liu H (2009) Assessing the influence probability between objects: a random walker approach. In: 2009 IEEE symposium on computational intelligence and data mining, Nashville, TN, pp 25–32

Li FH, Li CT, Shan MK (2011) Labeled influence maximization in social networks for target marketing. In: 2011 IEEE third international conference on privacy, security, risk and trust and 2011 IEEE third international conference on social computing, Boston, MA, pp 560–563

Li S, Zhu Y, Li D, Kim D, Ma H, Huang H (2014) Influence maximization in social networks with user attitude modification. In: 2014 IEEE international conference on communications (ICC), Sydney, NSW, pp 3913–3918

Liu B, Cong G, Xu D, Zeng Y (2012) Time constrained influence maximization in social networks. In: 2012 IEEE 12th international conference on data mining, Brussels, pp 439–448

Liu B, Cong G, Zeng Y, Xu D, Chee YM (2014) Influence spreading path and its application to the time constrained social influence maximization problem and beyond. IEEE Trans Knowl Data Eng 26(8):1904–1917CrossRef

Liu Y, Tang M, Zhou T, Do Y (2015) Improving the accuracy of the k-shell method by removing redundant links: from a perspective of spreading dynamics. Sci Rep 5:13172CrossRef

Lou T, Tang J, Hopcroft J, Fang Z, Ding X (2013) Learning to predict reciprocity and triadic closure in social networks. In: TKDD, vol 7, no 2

Lu Z, Zhang W, Wu W, Fu B, Du D (2011) Approximation and inapproximation for the influence maximization problem in social networks under deterministic linear threshold model. In: 2011 31st international conference on distributed computing systems workshops, Minneapolis, MN, pp 160–165

Lu J, Wei L, Yeh MY (2014) Influence maximization in a social network in the presence of multiple influences and acceptances. In: 2014 International conference on data science and advanced analytics (DSAA), Shanghai, pp 230–236

Lu Z, Long Y, Li VOK (2015) Cascade with varying activation probability model for influence maximization in social networks. In: 2015 International conference on computing, networking and communications (ICNC), Garden Grove, CA, pp 869–873

Maghami M, Sukthankar G (2013) Hierarchical influence maximization for advertising in multi-agent markets. In: 2013 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM 2013), Niagara Falls, ON, pp 21–27

Mihara S, Tsugawa S, Ohsaki H (2015) Influence maximization problem for unknown social networks. In: 2015 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), Paris, pp 1539–1546

Milgram S (1967) The small world problem. Psychol Today 2:60–67

Miller JC, Rae G, Schaefer F, Ward LA, LoFaro T, Farahat A (2001) Modifications of Kleinberg’s HITS algorithm using matrix exponentiation and web log records. In: Proceedings of the 24th annual international ACM SIGIR conference on research and development in information retrieval, systems engineering-theory & practice

Mohan A, Kunnakadan S, Neelakantan B, Jayakumar A, Salim H (2016) A scalable model for efficient information diffusion in large real world networks. In: 2016 International conference on next generation intelligent systems (ICNGIS), Kottayam, pp 1–6

Navlakha S, Rastogi R, Shrivastava N (2008) Graph summarization with bounded error. In SIGMOD

Newman MEJ (2005) A measure of betweenness centrality based on random walks. In: Social networks, vol 27, no 1, pp 39–54

Nguyen H, Zheng R (2013) On budgeted influence maximization in social networks. IEEE J Sel Areas Commun 31(6):1084–1094CrossRef

Nguyen DT, Das S, Thai MT (2013) Influence maximization in multiple online social networks. In: 2013 IEEE global communications conference (GLOBECOM), Atlanta, GA, pp 3060–3065

Ok J, Jin Y, Choi J, Shin J, Yi Y (2014) Influence maximization over strategic diffusion in social networks. In: 2014 48th annual conference on information sciences and systems (CISS), Princeton, NJ, pp 1–5

Ok J, Jin Y, Shin Y, Yi Y (2016) On maximizing diffusion speed over social networks with strategic users. IEEE/ACM Trans Netw 24(6):3798–3811CrossRef

Page L, Brin A, Motwani E, Winograd T (1999) The pagerank citation ranking: Bringing order to the web. Technical Report SIDL-WP-1999-0120, Stanford University

Pan J, Jiang F, Xu J (2016) Influence maximization in social networks based on non-backtracking random walk. In: 2016 IEEE first international conference on data science in cyberspace (DSC), Changsha, pp 260–267

Purnawansyah H (2016) K-Means clustering implementation in network traffic activities. In: 2016 International conference on computational intelligence and cybernetics, Makassar, pp 51–54

Qiang H, Yan G (2012) A method of personalized recommendation based on multi-label propagation for overlapping community detection. In: 2012 3rd international conference on system science, engineering design and manufacturing informatization, Chengdu, pp 360–364

Rahaman I, Hosein P (2016) On the multi-stage influence maximization problem. In: 2016 IEEE Latin American conference on computational intelligence (LA-CCI), Cartagena, pp 1–6

Srinivasan BV, Anandhavelu N, Dalal A, Yenugula M, Srikanthan P, Layek A (2014) Topic-based targeted influence maximization. In: 2014 Sixth international conference on communication systems and networks (COMSNETS), Bangalore, pp 1–6

Sun J, Tang J (2011) A survey of models and algorithms for social influence analysis. In: Aggarwal CC (ed) Social network data analytics. Kluwer Academic Publishers, Dordrecht, pp 177–214CrossRef

Tan C, Lee L, Tang J, Jiang L, Zhou M, Li P (2011) User-level sentiment analysis incorporating social networks. InL KDD’11, pp 1397–1405

Tang J, Sun J (2014) Models and algorithms for social influence analysis. In: WWW’2014 (Tutorial)

Tang J, Sun J, Wang C, Yang Z (2009) Social influence analysis in large-scale networks. In: KDD’09, pp 807–816

Tejaswi V, Bindu PV, Thilagam PS (2016) Diffusion models and approaches for influence maximization in social networks. In: International conference on advances in computing, communications and informatics (ICACCI), Jaipur, pp 1345–1351

Tejaswi V, Bindu PV, Thilagam PS (2017) Target specific influence maximization: an approach to maximize adoption in labeled social networks. In: 2017 9th international conference on communication systems and networks (COMSNETS), Bengaluru, India, pp 542–547

Toivonen H, Zhou F, Hartikainen A, Hinkka A (2011) Compression of weighted graphs. In: KDD

Tong G, Wu W, Tang S, Du DZ (2017) Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans Netw 25(1):112–125CrossRef

Wang F, Landau DP (2001) Determining the density of states for classical statistical models: a random walk algorithm to produce a flat histogram. Phys Rev 64:056101CrossRef

Wang J, Wu X, Yan B, Guo J (2011) Improved method of node importance evaluation based on node contraction in complex networks. Proc CEIS 15:1600–1604

Wang F, Xu K, Wang H (2012) Discovering shared interests in online social networks. In: 2012 32nd international conference on distributed computing systems workshops, Macau, China, pp 163–168

Wang X, Zhang Y, Zhang W, Lin X, Chen C (2017) Bring order into the samples: a novel scalable method for influence maximization (extended abstract). In: 2017 IEEE 33rd international conference on data engineering (ICDE), San Diego, CA, pp 55–56

Wang S, Zhang G, Sheu P (2018) A semantic approach to data reduction for weighted graphs and complex queries. Int J Semant Comput 12(2):287–312CrossRef

Watts DJ, Strogatz SH (1998) Collective dynamics of’small-world’ networks. Nature 393:440–442CrossRef

Weng X, Liu Z, Li Z (2016) An efficient influence maximization algorithm considering both positive and negative relationships. In: 2016 IEEE Trustcom/BigDataSE/ISPA, Tianjin, pp 1931–1936

Xu TS, Chiang HD, Liu GY, Tan CW (2017) Hierarchical K-means method for clustering large-scale advanced metering infrastructure data. IEEE Trans Power Deliv 32(2):609–616CrossRef

Yellakuor BE, Zhen Q, Hu X, Zhiguang Q (2015) Exploring online social networks for influence maximization. In: 2015 International conference and workshop on computing and communication (IEMCON), Vancouver, BC, pp 1–7

Yen JY (1971) Finding the K shortest loopless paths in a network. Manage Sci 17:712–716MathSciNetCrossRef

Yesilbudak M (2016) Clustering analysis of multidimensional wind speed data using k-means approach. In: 2016 IEEE international conference on renewable energy research and applications (ICRERA), Birmingham, pp 961–965

Yu M, Yang W, Wang W, Shen G, Dong G, Gong L (2016) UGGreedy: influence maximization for user group in microblogging. Chin J Electron 25(2):241–248CrossRef

Zargariasl H (2015) Finding social rules among objects in the social internet of things. Ph.D. Diss., Mediterranea University of Reggio Calabria, 2015, S.S.D. ING-INF/03 XXVII cycle

Zhang J, Liu B, Tang J, Chen T, Li J (2013) Social influence locality for modeling retweeting behaviors. In: IJCAI’13, pp 2761–2767

Zhang H, Nguyen DT, Zhang H, Thai MT (2016a) Least cost influence maximization across multiple social networks. IEEE/ACM Trans Netw 24(2):929–939CrossRef

Zhang H, Zhang H, Kuhnle A, Thai MT (2016) Profit maximization for multiple products in online social networks. In: IEEE INFOCOM 2016—the 35th annual IEEE international conference on computer communications, San Francisco, CA, pp 1–9

Zhang Y, Bai Y, Chen L, Bian K, Li X (2016) Influence maximization in messenger-based social networks. In: 2016 IEEE global communications conference (GLOBECOM), Washington, DC, pp 1–6

Zhang G, Li S, Wang J, Liu P, Chen Y, Luo Y (2017) New influence maximization algorithm research in big graph. In: 14th Web information systems and applications conference (WISA)

Zhao J, Liu Q, Wang L, Wang X (2015) Relative influence maximization in competitive dynamics on complex networks. In: 2015 54th IEEE conference on decision and control (CDC), Osaka, pp 6583–6588

Zhou S, Yue K, Fang Q, Zhu Y, Liu W (2014) An efficient algorithm for influence maximization under linear threshold model. In: The 26th Chinese control and decision conference, Changsha, pp 5352–5357

Zhuang H, Sun Y, Tang J, Zhang J, Sun X (2013) Influence maximization in dynamic social networks. In: 2013 IEEE 13th international conference on data mining, Dallas, TX, pp 1313–1318

Titel: Influence maximization in graph-based OLAP (GOLAP)
verfasst von: Jenny Jin
Guigang Zhang
Phillip Sheu
Masahiro Hayakawa
Atsushi Kitazawa
Publikationsdatum: 01.12.2019
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 1/2019
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-019-0598-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2019

Building a soft skill taxonomy from job openings

A quest for the structure of intra- and postoperative surgical team networks: does the small-world property evolve over time?

A social network theory perspective on how social ties influence perceived employability and job insecurity: evidence from school teachers

Localizing and quantifying infrastructure damage using class activation mapping approaches

Tracing temporal communities and event prediction in dynamic social networks

Telegram group quality measurement by user behavior analysis

Premium Partner