Högskolan i Skövde

his.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • apa-cv
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Community-based Influence Maximization framework for Social Networks
University of Skövde, School of Informatics.
2018 (English)Independent thesis Advanced level (degree of Master (One Year)), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Maximizing Influence (IM) in social networks has a considerable role to play in the phenomenon of viral marketing, targeted advertisements and in promoting any campaigns. However, the Influence Maximization Problem is a very challenging research-problem due to it being NP-Hard and scaling with the social networks with millions of nodes and edges becomes very tough due to the computational complexities concerned with it. Recently, solving this problem through the use of community detection based methodology is becoming very popular since, it reduces the search space by dividing the network into smaller and more manageable groups called "communities." As part of the larger research work, we reiterate a framework which has been inspired by collection of different work done by Alfalahi et al. (2013) that we can implement to solve the IM problem and its limitation through community detection and fuzzy logic inspired approach. Since the work is still under development, for this project, we report on understanding the IM field through literature reviews and in communicating a design of IM framework as inspired by the previous works. We also present our version ofthe blueprint (Algorithm design) of the framework as a five step approach. For the purpose of this report, we implement and evaluated the step 1 and step 2 of the framework. Step 1 is about preprocessing the input network with a similarity measure, which according to previous study by Alfalahi et al. (2013a) aids the algorithms in detecting better community structure (clear and accurate distinction of the nodes into communities in networks). We test it to see if it holds true. Step 2 is about implementing the community detection in social network. We benchmarkthree candidate algorithms, chosen based on theirperformance, from the previous studies in community detection fieldand we report onwhich algorithm should we consider to use in the proposed framework through experimentationon the simulated data. We use Normalized Mutual Information (NMI) and Modularity (Q) as evaluation metrics to measure the accuracy of the community detected by the candidate algorithms. Our results show that similarity based preprocessing does not improve the community structure and thus may not be required in the framework. We also found out that Louvain should be the algorithm that use to detect communities in social networks since it outperforms both CNM and Infomap on Q and NMI

Place, publisher, year, edition, pages
2018. , p. 58
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:his:diva-15378OAI: oai:DiVA.org:his-15378DiVA, id: diva2:1214562
Subject / course
Informationsteknologi
Educational program
Data Science - Master’s Programme
Supervisors
Examiners
Available from: 2018-06-13 Created: 2018-06-07 Last updated: 2018-09-26Bibliographically approved

Open Access in DiVA

fulltext(1320 kB)920 downloads
File information
File name FULLTEXT01.pdfFile size 1320 kBChecksum SHA-512
d3c7c00aca595f03969efbbf2e1d046aff184c84ec4b7ba326674816dd846045d09fbbe22e1792a961b40b50d0e162e2878156ce5b63b53565c6d692b740e482
Type fulltextMimetype application/pdf

By organisation
School of Informatics
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 921 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 448 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • apa-cv
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf