DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
View Events Video Library
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Integrating PostgreSQL Databases with ANF: Join this workshop to learn how to create a PostgreSQL server using Instaclustr’s managed service

Mobile Database Essentials: Assess data needs, storage requirements, and more when leveraging databases for cloud and edge applications.

Monitoring and Observability for LLMs: Datadog and Google Cloud discuss how to achieve optimal AI model performance.

Automated Testing: The latest on architecture, TDD, and the benefits of AI and low-code tools.

Related

  • Towards a Knowledge Graph Economy. The Year of the Graph Newsletter, Summer 2020
  • Positive Impact of Graph Technology and Neural Networks on Cybersecurity
  • Getting Started With ReGraph — The Graph Visualization Toolkit for React
  • How to Leverage the MuleSoft Anypoint Visualizer

Trending

  • Generative AI: A New Tool in the Developer Toolbox
  • Podman Desktop Review
  • Database Monitoring: Key Metrics and Considerations
  • Spring WebFlux Retries
  1. DZone
  2. Data Engineering
  3. IoT
  4. Graph Theory and Network Science: The Basics

Graph Theory and Network Science: The Basics

Marko Rodriguez user avatar by
Marko Rodriguez
·
Aug. 13, 12 · Interview
Like (0)
Save
Tweet
Share
50.61K Views

Join the DZone community and get the full member experience.

Join For Free

graph theory and network science are two related academic fields that have found application in numerous commercial industries. the terms ‘graph’ and ‘network’ are synonymous and one or the other is favored depending on the domain of application. a rosetta stone of terminology is provided below to help ground the academic terms to familiar, real-world structures.

graph network brain knowledge society circuit web
vertices nodes neurons concepts people elements pages
edges links axons relations ties wires hrefs

graph theory is a branch of discrete mathematics concerned with proving theorems and developing algorithms for arbitrary graphs (e.g. random graphs , lattices , hierarchies ). for example, can a graph with four vertices, seven edges, and structured according to the landmasses and bridges of königsberg have its edges traversed once and only once? from such problems, the field of graph theory has developed numerous algorithms that can be applied to any graphical structure irrespective of the domain it represents (i.e. irrespective of what the graph models in the real-world). examples of such developments are provided below:

  • planar graphs : can a graph be laid onto a 2d surface such that no edges cross. this problem has application, for example, in circuit board design where no two wires can overlap.
  • shortest paths : what is the minimum number of hops required to get from vertex a to vertex b in a graph? moreover, what is the path that was taken? this problem has applications in routing , automated reasoning , and planning .
  • energy flows : if a continuous “energy field” is diffused out from a particular vertex (or set of vertices), how much energy do the other vertices in the graph receive? this problem is found in recommendation engines , knowledge discovery, artificial cognition/intelligence , ranking, and natural language processing .

in the domain of network science, researchers don’t study networks in the abstract, but instead, they study numerous real-world representations in order to understand the universal properties of networks. examples of such networks include social networks , transportation networks , gene regulatory networks , knowledge networks , scholarly networks , etc. network science is a relatively new discipline that has only been able to blossom because of computer technologies. with computers, scientists are able analyze large-scale networks such as the world wide web which has approximately 500 billion nodes. due to their size, such structures tend to be studied from a statistical perspective.

  • degree distribution : if a node is randomly selected from the network, what is the probability that it has x number of edges emanating from it? this statistic has implications for understanding how disease spreads through a social network and how communication networks can be sabotaged by directed attacks.
  • assortative mixing : do nodes with characteristic a tend to connect to nodes with characteristic b? such information is useful as a descriptive statistic as well as for inferring future connectivity patterns in the network.
  • growth models : do all real-world networks grow according to a similar rule? network growth models have implications for designing learning systems and understanding the future statistics of a fledgling network.

perhaps the crowning achievement of network science is the realization that most “real-world” networks have a similar structure. such networks are called scale-free networks and their degree distribution has an exponential decay. what this means is that real-world networks tend to have few nodes with numerous links and numerous nodes with few links. prior to recent times, most people assumed that networks were randomly connected. in the late 90s and early 00s a mass of scholarly articles were published demonstrating the prevalence of scale-free networks in nearly every possible domain imaginable.

interestingly, because most natural networks have this connectivity pattern, the processes that are evaluated on such networks are nearly the same—the only difference being the semantics as defined by the domain. for example, recommending products is analogous to determining the flow within an electrical circuit or determining how sensory data propagates through a neural network. finding friends in a social network is analogous to routing packets in a communication network or determining the shortest route on a transportation network. ranking web pages is analogous to determining the most influential people in a social network or finding the most relevant concepts in a knowledge network. finally, all these problems are variations of one general process— graph traversing . graph traversing is the simple process of moving from one vertex to another vertex over the edges in the graph and either mutating the structure or collecting bits of information along the way. the result of a traversal is either an evolution of the graph or a statistic about the graph.

the tools and techniques developed by graph theorists and networks scientists has an astounding number of practical applications. interestingly enough, once one has a general understanding of graph theory and network science, the world’s problems start to be seen as one in the same problem.

related material

rodriguez, m.a., neubauer, p., “ the graph traversal pattern ,” graph data management: techniques and applications, eds. s. sakr, e. pardede, igi global, isbn:9781613500538, august 2011.

watkins, j.h., m.a. rodriguez, “ a survey of web-based collective decision making systems ,” studies in computational intelligence: evolution of the web in artificial intelligence environments, springer-verlag, pages 245-279, 2008.

rodriguez, m.a., “ a graph-based movie recommender engine ,” marko a. rodriguez blog, 2011.

rodriguez, m.a., “ graphs, brains, and gremlin ,” marko a. rodriguez blog, 2011.

Network Graph (Unix)

Published at DZone with permission of Marko Rodriguez, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Towards a Knowledge Graph Economy. The Year of the Graph Newsletter, Summer 2020
  • Positive Impact of Graph Technology and Neural Networks on Cybersecurity
  • Getting Started With ReGraph — The Graph Visualization Toolkit for React
  • How to Leverage the MuleSoft Anypoint Visualizer

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: