KG_Lecture_IV_2024-26

Knowledge Graphs in Graph Theory

Types of Graphs

• Graphs can be classified into:

  • Undirected: edges do not have a direction.

  • Directed: edges have a direction.

  • Cyclic: contain cycles.

  • Acyclic: do not contain cycles.

  • Digraph: directed graph.

  • Weighted: edges have weights.

  • Unweighted: edges do not have weights.

  • Sparse: few edges compared to vertices.

  • Dense: many edges compared to vertices.

Large Graphs

• Definition: Large graphs contain thousands of vertices and tens of thousands of edges, making visualization and analysis challenging.

• Applications:

  • Represent biological, technical, and social networks.

  • Analysis provides insights into structure and behavior.

• Example: Protein interaction networks offer insights into health and disease states of organisms.

Properties of Large Graphs

• Not randomly connected; exhibit specific patterns.

• Scale-Free Networks: Few vertices have many connections; most have few connections.

• Small-World Networks: Small average distances between vertices despite a large number of nodes.

Network Models

Classifications

• Basic models for analyzing large networks:

  • Random Networks

  • Small-World Networks

  • Scale-Free Networks

Random Networks

• Introduced by Erdős and Rényi, these graphs are formed by adding edges randomly based on a probability.

• Complete graphs emerge when p = 1. The Python library NetworkX includes functions for creating these graphs.

Small-World Networks

• Characterized by short distances between nodes and high clustering coefficients.

• The property holds for networks like protein interactions and the internet.

• Mean distance reportedly approximates O(log(n)) as nodes increase.

Characteristics of Small-World Networks

• Graphs exhibit a balance between randomness and order. High clustering allows many connections with few hops.

• Examples in various domains: Social networks, road maps, and networks in biology.

• Models analyzed by Watts and Strogatz highlight parameters conducive to small-world formation with varying values for p.

Scale-Free Networks

• Defined by a degree distribution following a power law, assisting in identifying nodes of greater connectivity.

• Proposed by Barabási and Albert focusing on growth and preferential attachment:

  • Growth: Network nodes increase over time.

  • Preferential attachment: Newer nodes preferentially link to high-degree nodes, underlying the principle that “the rich get richer.”

Kronecker Graphs

• Utilized to create synthetic complex networks replicating real-world characteristics like scale-free and small-world properties through the Kronecker product.

• Python's NumPy library aids in constructing Kronecker graphs, which mimic various complex networks.

Communities in Networks

Community Structure

• Defined by internal and external degrees, emphasizing the cohesion of nodes within communities.

Metrics for Communities

• Internal degree: Connections within the community.

• Community degree: Sum of node degrees in a community.

• Density reflects potential links to gauge community strength.

Network Community Classification

• Strong communities: Nodes have more connections internally than externally.

• Weak communities: Total internal node degrees exceed those to the rest of the network.

Partitions and Overlapping Communities

• A partition uniquely groups nodes into a community, with a Bell number indicating possible configurations.

• Overlapping communities: Reflect social networks where nodes belong to multiple groups simultaneously.

Network Partitioning Techniques

Graph Bisection

• Defined by identifying a cut separating subnetworks, fundamental in community detection frameworks.

Algorithms

• Kernighan-Lin Algorithm: An iterative method that seeks to minimize cut size while maintaining cluster sizes.

Additional Techniques

• Bridge-Removal: Identifies links whose removal disconnects communities, simplifying community detection through analyzes of connected components.

Modularity Score

• It assesses the quality of a community partition relative to a randomly constructed baseline, highlighting links significant to clusters versus expected random outcomes.

• The algorithm can efficiently compute partitions maximizing modularity using the NetworkX library.