Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 3/2021

06.06.2020

CFIN: A community-based algorithm for finding influential nodes in complex social networks

verfasst von: Mohammad Mehdi Daliri Khomami, Alireza Rezvanian, Mohammad Reza Meybodi, Alireza Bagheri

Erschienen in: The Journal of Supercomputing | Ausgabe 3/2021

Einloggen

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

search-config
loading …

Abstract

Influence maximization (IM) problem, a fundamental algorithmic problem, is the problem of selecting a set of k users (refer as seed set) from a social network to maximize the expected number of influenced users (also known as influence spread). Due to the numerous applications of IM in marketing, IM has been studied extensively in recent years. Nevertheless, many algorithms do not take into consideration the impact of communities to influence maximization and some algorithms are non-scalable and time-consuming in practice. In this paper, we proposed a fast and scalable algorithm called community finding influential node (CFIN) that selects k users based on community structure, which maximizes the influence spread in the networks. The CFIN consists of two main parts for influence maximization: (1) seed selection and (2) local community spreading. The first part of CFIN is the extraction of seed nodes from communities which obtained the running of the community detection algorithm. In this part, to decrease computational complexity effectively and scatter seed nodes into communities, the meaningful communities are selected. The second part consists of the influence spread inside communities that are independent of each other. In this part, the final seed nodes entered to distribute the local spreading by the use of a simple path inside communities. To study the performance of the CFIN, several experiments have been conducted on some real and synthetic networks. The experimental simulations on the CFIN, in comparison with other algorithms, confirm the superiority of the CFIN in terms of influence spread, coverage ratio, running time, and Dolan-Moré performance profile.
Vorheriger Artikel PCVM.ARIMA: predictive consolidation of virtual machines applying ARIMA method
Nächster Artikel An end-to-end deep learning model for human activity recognition from highly sparse body sensor data in Internet of Medical Things environment

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

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

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
Literatur
1.
2.
3.
Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 57–66
4.
Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp 1539–1554
5.
Zhang H, Mishra S, Thai MT et al (2014) Recent advances in information diffusion and influence maximization in complex social networks. Oppor Mob Soc Netw 37:37
6.
Budak C, Agrawal D, El Abbadi A (2011) Limiting the spread of misinformation in social networks. In: Proceedings of the 20th International Conference on World Wide Web. ACM, pp 665–674
7.
Wu P, Pan L (2017) Scalable influence blocking maximization in social networks under competitive independent cascade models. Comput Netw 123:38–50
8.
Feng Z, Xu X, Yuruk N, Schweiger TA (2007) A novel similarity-based modularity function for graph partitioning. In: International Conference on Data Warehousing and Knowledge Discovery. Springer, pp 385–396
9.
Teng YW TC, Yu PS, Chen MS (2018) Revenue maximization on the multi-grade product. In: Proceedings of the 2018 SIAM International Conference on Data Mining, pp 576–584
10.
Ma H, Yang H, Lyu MR, King I (2008) Mining social networks using heat diffusion processes for marketing candidates selection. In: Proceedings of the 17th ACM Conference on Information and Knowledge Management. ACM, pp 233–242
11.
Khomami MMD, Rezvanian A, Bagherpour N, Meybodi MR (2018) Minimum positive influence dominating set and its application in influence maximization: a learning automata approach. Appl Intell 48:570–593
12.
Rezvanian A, Moradabadi B, Ghavipour M et al (2019) Social Influence Maximization. In: Rezvanian A, Moradabadi B, Ghavipour M et al (eds) Learning automata approach for social networks. Springer International Publishing, Cham, pp 315–329
13.
Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, pp 137–146
14.
Leskovec J, Krause A, Guestrin C et al (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 420–429
15.
Goyal A, Lu W, Lakshmanan LV (2011) Celf ++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th International Conference Companion on World Wide Web. ACM, pp 47–48
16.
Kundu S, Pal SK (2015) Deprecation based greedy strategy for target set selection in large scale social networks. Inf Sci 316:107–122MATH
17.
Zhou C, Zhang P, Zang W, Guo L (2015) On the upper bounds of spread for greedy algorithms in social network influence maximization. IEEE Trans Knowl Data Eng 27:2770–2783
18.
Song G, Li Y, Chen X et al (2016) Influential node tracking on dynamic social network: an interchange greedy approach. IEEE Trans Knowl Data Eng 29:359–372
19.
Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 199–208
20.
Guo J, Zhang P, Zhou C et al (2013) Item-based top-k influential user discovery in social networks. In: 2013 IEEE 13th International Conference on Data Mining Workshops. IEEE, pp 780–787
21.
Zhao X-Y, Huang B, Tang M et al (2015) Identifying effective multiple spreaders by coloring complex networks. EPL Europhys Lett 108:68005
22.
Kim J, Kim S-K, Yu H (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks? In: 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, pp 266–277
23.
Kim J, Lee W, Yu H (2014) CT-IC: continuously activated and time-restricted independent cascade model for viral marketing. Knowl Based Syst 62:57–68
24.
Li D, Xu Z-M, Chakraborty N et al (2014) Polarity related influence maximization in signed social networks. PLoS ONE 9:e102199
25.
Luo Z-L, Cai W-D, Li Y-J, Peng D (2012) A pagerank-based heuristic algorithm for influence maximization in the social network. In: Recent Progress in Data Engineering and Internet Technology. Springer, pp 485–490
26.
Kimura M, Saito K, Nakano R, Motoda H (2010) Extracting influential nodes on a social network for information diffusion. Data Min Knowl Discov 20:70MathSciNet
27.
Ohsaka N, Akiba T, Yoshida Y, Kawarabayashi K (2014) Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In: Twenty-Eighth AAAI Conference on Artificial Intelligence
28.
Goyal A, Lu W, Lakshmanan LV (2011) Simpath: an efficient algorithm for influence maximization under the linear threshold model. In: 2011 IEEE 11th International Conference on Data Mining (ICDM). IEEE, pp 211–220
29.
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. IEEE, pp 88–97
30.
Lu Z, Fan L, Wu W et al (2014) Efficient influence spread estimation for influence maximization under the linear threshold model. Comput Soc Netw 1:2
31.
Heidari M, Asadpour M, Faili H (2015) SMG: fast scalable greedy algorithm for influence maximization in social networks. Phys Stat Mech Appl 420:124–133
32.
Narayanam R, Narahari Y (2011) A shapley value-based approach to discover influential nodes in social networks. IEEE Trans Autom Sci Eng 8:130–147
33.
Cantwell GT, Newman MEJ (2019) Mixing patterns and individual differences in networks. Phys Rev E 99:042306
34.
Riolo MA, Cantwell GT, Reinert G, Newman ME (2017) Efficient method for estimating the number of communities in a network. Phys Rev E 96:032310
35.
Liu W, Pellegrini M, Wang X (2014) Detecting communities based on network topology. Sci Rep 4:5739
36.
Li H, Bhowmick SS, Sun A, Cui J (2015) Conformity-aware influence maximization in online social networks. VLDB J 24:117–141
37.
Guo L, Zhang D, Cong G et al (2016) Influence maximization in trajectory databases. IEEE Trans Knowl Data Eng 29:627–641
38.
Li Y, Zhang D, Tan K-L (2015) Real-time targeted influence maximization for online advertisements
39.
Stein S, Eshghi S, Maghsudi S et al (2017) Heuristic algorithms for influence maximization in partially observable social networks. In: SocInf@ IJCAI, pp 20–32
40.
Wilder B, Immorlica N, Rice E, Tambe M (2018) Maximizing influence in an unknown social network. In: Thirty-Second AAAI Conference on Artificial Intelligence
41.
Rezvanian A, Moradabadi B, Ghavipour M et al (2019) Social Community Detection. Learning automata approach for social networks. Springer International Publishing, Cham, pp 151–168
42.
de Guzzi Bagnato G, Ronqui JRF, Travieso G (2018) Community detection in networks using self-avoiding random walks. Phys Stat Mech Appl 505:1046–1055
43.
44.
45.
Kumpula JM, Kivelä M, Kaski K, Saramäki J (2008) Sequential algorithm for fast clique percolation. Phys Rev E 78(2):026109
46.
Luo Z-G, Ding F, Jiang X-Z, Shi J-L (2011) New progress on community detection in complex networks. J Nat Univ Defense Technol 33(1):47–52
47.
Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818
48.
Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106
49.
Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phys 12:103018MATH
50.
Xie J, Szymanski BK (2012) Towards linear time overlapping community detection in social networks. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, pp 25–36
51.
Ugander J, Backstrom L (2013) Balanced label propagation for partitioning massive graphs. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp 507–516
52.
Stokes ME, Barmada MM, Kamboh MI, Visweswaran S (2014) The application of network label propagation to rank biomarkers in genome-wide Alzheimer’s data. BMC Genom 15:282
53.
Hosseini R, Rezvanian A (2020) AntLP: ant-based label propagation algorithm for community detection in social networks. CAAI Trans Intell Technol 5:34–41
54.
Kuzmin K, Shah SY, Szymanski BK (2013) Parallel overlapping community detection with SLPA. In: 2013 International Conference on Social Computing. IEEE, pp 204–212
55.
Ahn Y-Y, Bagrow JP, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature 466:761–764
56.
Ye Q, Wu B, Zhao Z, Wang B (2011) Detecting link communities in massive networks. In: 2011 International Conference on Advances in Social Networks Analysis and Mining. IEEE, pp 71–78
57.
Lee C, Reid F, McDaid A, Hurley N (2010) Detecting highly overlapping community structure by greedy clique expansion. ArXiv Prepr ArXiv10021827
58.
Zhang X, Wang C, Su Y et al (2017) A fast overlapping community detection algorithm based on weak cliques for large-scale networks. IEEE Trans Comput Soc Syst 4:218–230
59.
Badie R, Aleahmad A, Asadpour M, Rahgozar M (2013) An efficient agent-based algorithm for overlapping community detection using nodes’ closeness. Phys Stat Mech Appl 392:5231–5247
60.
Khomami MMD, Rezvanian A, Meybodi MR (2016) Distributed learning automata-based algorithm for community detection in complex networks. Int J Mod Phys B 30:1650042MathSciNet
61.
Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99:7821–7826MathSciNetMATH
62.
Lusseau D (2003) The emergent properties of a dolphin social network. Proc R Soc Lond B Biol Sci 270:S186–S188
63.
Park J, Newman ME (2005) A network-based ranking system for US college football. J Stat Mech: Theory Exp 2005:P10014MATH
64.
Adamic LA, Glance N (2005) The political blogosphere and the 2004 US election: divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery. ACM, pp 36–43
65.
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data TKDD 1:1–41
66.
Richardson M, Agrawal R, Domingos P (2003) Trust management for the semantic web. In: International Semantic Web Conference. Springer, pp 351–368
67.
Erdos P, Rényi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17–61MathSciNetMATH
68.
Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442MATH
69.
Lancichinetti A, Radicchi F, Ramasco JJ, Fortunato S (2011) Finding statistically significant communities in networks. PLoS ONE 6:e18961
70.
Goyal A, Bonchi F, Lakshmanan LVS (2011) A data-based approach to social influence maximization. Proc VLDB Endow 5:73–84
71.
Chen Y-C, Zhu W-Y, Peng W-C et al (2014) CIM: community-based influence maximization in social networks. ACM Trans Intell Syst Technol TIST 5:25
72.
Rahimkhani K, Aleahmad A, Rahgozar M, Moeini A (2015) A fast algorithm for finding most influential people based on the linear threshold model. Expert Syst Appl 42:1353–1361
73.
Ok J, Jin Y, Shin J, Yi Y (2014) On maximizing diffusion speed in social networks: impact of random seeding and clustering. In: The 2014 ACM International Conference on Measurement and Modeling of Computer Systems, pp 301–313
74.
75.
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91:201–213MathSciNetMATH
Metadaten
Titel
CFIN: A community-based algorithm for finding influential nodes in complex social networks
verfasst von
Mohammad Mehdi Daliri Khomami
Alireza Rezvanian
Mohammad Reza Meybodi
Alireza Bagheri
Publikationsdatum
06.06.2020
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 3/2021
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-020-03355-2

Weitere Artikel der Ausgabe 3/2021

The Journal of Supercomputing 3/2021 Zur Ausgabe

OriginalPaper

A convolutional autoencoder-based approach with batch normalization for energy disaggregation

OriginalPaper

Network anomaly detection based on selective ensemble algorithm

OriginalPaper

A cloud computing framework for analysis of agricultural big data based on Dempster–Shafer theory

OriginalPaper

Task scheduling, resource provisioning, and load balancing on scientific workflows using parallel SARSA reinforcement learning agents and genetic algorithm

OriginalPaper

Image enhancement using deep-learning fully connected neural network mean filter

OriginalPaper

Energy consumption model in multicore architectures with variable frequency

Premium Partner

    Bildnachweise