Skip to main content

Main menu

  • Home
  • Articles
    • Current
    • Special Feature Articles - Most Recent
    • Special Features
    • Colloquia
    • Collected Articles
    • PNAS Classics
    • List of Issues
  • Front Matter
    • Front Matter Portal
    • Journal Club
  • News
    • For the Press
    • This Week In PNAS
    • PNAS in the News
  • Podcasts
  • Authors
    • Information for Authors
    • Editorial and Journal Policies
    • Submission Procedures
    • Fees and Licenses
  • Submit
  • Submit
  • About
    • Editorial Board
    • PNAS Staff
    • FAQ
    • Accessibility Statement
    • Rights and Permissions
    • Site Map
  • Contact
  • Journal Club
  • Subscribe
    • Subscription Rates
    • Subscriptions FAQ
    • Open Access
    • Recommend PNAS to Your Librarian

User menu

  • Log in
  • My Cart

Search

  • Advanced search
Home
Home
  • Log in
  • My Cart

Advanced Search

  • Home
  • Articles
    • Current
    • Special Feature Articles - Most Recent
    • Special Features
    • Colloquia
    • Collected Articles
    • PNAS Classics
    • List of Issues
  • Front Matter
    • Front Matter Portal
    • Journal Club
  • News
    • For the Press
    • This Week In PNAS
    • PNAS in the News
  • Podcasts
  • Authors
    • Information for Authors
    • Editorial and Journal Policies
    • Submission Procedures
    • Fees and Licenses
  • Submit
Research Article

Local structure can identify and quantify influential global spreaders in large scale social networks

Yanqing Hu, Shenggong Ji, Yuliang Jin, Ling Feng, View ORCID ProfileH. Eugene Stanley, and Shlomo Havlin
  1. aSchool of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China;
  2. bSchool of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China;
  3. cKey Laboratory for Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China;
  4. dComputing Science, Institute of High Performance Computing, Agency for Science, Technology, and Research, Singapore 138632;
  5. eDepartment of Physics, National University of Singapore, Singapore 117551;
  6. fCenter for Polymer Studies and Department of Physics, Boston University, Boston, MA 02215;
  7. gDepartment of Physics, Bar-Ilan University, Ramat-Gan 52900, Israel

See allHide authors and affiliations

PNAS July 17, 2018 115 (29) 7468-7472; first published July 3, 2018; https://doi.org/10.1073/pnas.1710547115
Yanqing Hu
aSchool of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China;
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
  • For correspondence: huyanq@mail.sysu.edu.cn hes@bu.edu
Shenggong Ji
bSchool of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China;
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Yuliang Jin
cKey Laboratory for Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China;
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Ling Feng
dComputing Science, Institute of High Performance Computing, Agency for Science, Technology, and Research, Singapore 138632;
eDepartment of Physics, National University of Singapore, Singapore 117551;
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
H. Eugene Stanley
fCenter for Polymer Studies and Department of Physics, Boston University, Boston, MA 02215;
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
  • ORCID record for H. Eugene Stanley
  • For correspondence: huyanq@mail.sysu.edu.cn hes@bu.edu
Shlomo Havlin
gDepartment of Physics, Bar-Ilan University, Ramat-Gan 52900, Israel
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
  1. Contributed by H. Eugene Stanley, December 31, 2017 (sent for review August 31, 2017; reviewed by Marc Barthelemy and Zoltán Toroczkai)

  • Article
  • Figures & SI
  • Info & Metrics
  • PDF
Loading

Significance

Identification and quantification of influential spreaders in social networks are challenging due to the gigantic network sizes and limited availability of the entire structure. Here we show that such difficulty can be overcome by reducing the problem scale to a local one, which is essentially independent of the entire network. This is because in viral spreading the characteristic spreading size does not depend on network structure outside the local environment of the seed spreaders. Our approach may open the door to solve various big data problems such as false information surveillance and control, viral marketing, epidemic control, and network protection.

Abstract

Measuring and optimizing the influence of nodes in big-data online social networks are important for many practical applications, such as the viral marketing and the adoption of new products. As the viral spreading on a social network is a global process, it is commonly believed that measuring the influence of nodes inevitably requires the knowledge of the entire network. Using percolation theory, we show that the spreading process displays a nucleation behavior: Once a piece of information spreads from the seeds to more than a small characteristic number of nodes, it reaches a point of no return and will quickly reach the percolation cluster, regardless of the entire network structure; otherwise the spreading will be contained locally. Thus, we find that, without the knowledge of the entire network, any node’s global influence can be accurately measured using this characteristic number, which is independent of the network size. This motivates an efficient algorithm with constant time complexity on the long-standing problem of best seed spreaders selection, with performance remarkably close to the true optimum.

  • social media
  • complex network
  • percolation
  • influence
  • viral marketing

Footnotes

  • ↵1Y.H., S.J., Y.J., L.F., H.E.S., and S.H. contributed equally to this work.

  • ↵2To whom correspondence may be addressed. Email: huyanq{at}mail.sysu.edu.cn or hes{at}bu.edu.
  • Author contributions: Y.H., L.F., and S.H. designed research; Y.H., S.J., and Y.J. performed research; Y.H., S.J., H.E.S., and S.H. analyzed data; and Y.H., L.F., H.E.S., and S.H. wrote the paper.

  • Reviewers: M.B., Centre Commissariat à l’Energie Atomique; and Z.T., University of Notre Dame.

  • The authors declare no conflict of interest.

  • This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1710547115/-/DCSupplemental.

Published under the PNAS license.

View Full Text
PreviousNext
Back to top
Article Alerts
Email Article

Thank you for your interest in spreading the word on PNAS.

NOTE: We only request your email address so that the person you are recommending the page to knows that you wanted them to see it, and that it is not junk mail. We do not capture any email address.

Enter multiple addresses on separate lines or separate them with commas.
Local structure can identify and quantify influential global spreaders in large scale social networks
(Your Name) has sent you a message from PNAS
(Your Name) thought you would like to see the PNAS web site.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Citation Tools
Local structure can identify and quantify influential global spreaders in large scale social networks
Yanqing Hu, Shenggong Ji, Yuliang Jin, Ling Feng, H. Eugene Stanley, Shlomo Havlin
Proceedings of the National Academy of Sciences Jul 2018, 115 (29) 7468-7472; DOI: 10.1073/pnas.1710547115

Citation Manager Formats

  • BibTeX
  • Bookends
  • EasyBib
  • EndNote (tagged)
  • EndNote 8 (xml)
  • Medlars
  • Mendeley
  • Papers
  • RefWorks Tagged
  • Ref Manager
  • RIS
  • Zotero
Request Permissions
Share
Local structure can identify and quantify influential global spreaders in large scale social networks
Yanqing Hu, Shenggong Ji, Yuliang Jin, Ling Feng, H. Eugene Stanley, Shlomo Havlin
Proceedings of the National Academy of Sciences Jul 2018, 115 (29) 7468-7472; DOI: 10.1073/pnas.1710547115
del.icio.us logo Digg logo Reddit logo Twitter logo CiteULike logo Facebook logo Google logo Mendeley logo
  • Tweet Widget
  • Facebook Like
  • Mendeley logo Mendeley

Article Classifications

  • Physical Sciences
  • Applied Physical Sciences
  • Social Sciences
  • Social Sciences
Proceedings of the National Academy of Sciences: 115 (29)
Table of Contents

Submit

Sign up for Article Alerts

Jump to section

  • Article
    • Abstract
    • Results
    • Methods
    • Summary
    • Acknowledgments
    • Footnotes
    • References
  • Figures & SI
  • Info & Metrics
  • PDF

You May Also be Interested in

Setting sun over a sun-baked dirt landscape
Core Concept: Popular integrated assessment climate policy models have key caveats
Better explicating the strengths and shortcomings of these models will help refine projections and improve transparency in the years ahead.
Image credit: Witsawat.S.
Model of the Amazon forest
News Feature: A sea in the Amazon
Did the Caribbean sweep into the western Amazon millions of years ago, shaping the region’s rich biodiversity?
Image credit: Tacio Cordeiro Bicudo (University of São Paulo, São Paulo, Brazil), Victor Sacek (University of São Paulo, São Paulo, Brazil), and Lucy Reading-Ikkanda (artist).
Syrian archaeological site
Journal Club: In Mesopotamia, early cities may have faltered before climate-driven collapse
Settlements 4,200 years ago may have suffered from overpopulation before drought and lower temperatures ultimately made them unsustainable.
Image credit: Andrea Ricci.
Click beetle on a leaf
How click beetles jump
Marianne Alleyna, Aimy Wissa, and Ophelia Bolmin explain how the click beetle amplifies power to pull off its signature jump.
Listen
Past PodcastsSubscribe
Birds nestling on tree branches
Parent–offspring conflict in songbird fledging
Some songbird parents might improve their own fitness by manipulating their offspring into leaving the nest early, at the cost of fledgling survival, a study finds.
Image credit: Gil Eckrich (photographer).

Similar Articles

Site Logo
Powered by HighWire
  • Submit Manuscript
  • Twitter
  • Facebook
  • RSS Feeds
  • Email Alerts

Articles

  • Current Issue
  • Special Feature Articles – Most Recent
  • List of Issues

PNAS Portals

  • Anthropology
  • Chemistry
  • Classics
  • Front Matter
  • Physics
  • Sustainability Science
  • Teaching Resources

Information

  • Authors
  • Editorial Board
  • Reviewers
  • Subscribers
  • Librarians
  • Press
  • Site Map
  • PNAS Updates
  • FAQs
  • Accessibility Statement
  • Rights & Permissions
  • About
  • Contact

Feedback    Privacy/Legal

Copyright © 2021 National Academy of Sciences. Online ISSN 1091-6490