Loading...

Graphlet-Based Local Efficiency

Keshavarz, Shokoofe | 2025

66 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: Farsi
  3. Document No: 58704 (19)
  4. University: Sharif University of Technology
  5. Department: Computer Engineering
  6. Advisor(s): Beigi, Hamid
  7. Abstract:
  8. This thesis presents Graphlet-based Local Efficiency (GLE) as a novel framework for quantifying local efficiency in complex networks through higher-order structural patterns. Unlike classical local efficiency, which evaluate the connectivity among a node’s immediate neighbors after its removal, GLE generalizes this notion by incorporating 3 and 4-node induced subgraphs or graphlets and their orbit-specific configurations. This formulation enables GLE to capture multi-scale dependencies within local neighborhoods and to distinguish between distinct structural motifs such as triangles, chains and cliques that contribute differently to local communication efficiency. A weighted convex model is introduced to combine the contributions of all graphlet type, where weights reflect the relative functional significance of each motif. The resulting method is both interpretable and theoretically consistent with the traditional definition of local efficiency, while extending it to the domain of higher-order connectivity analysis. To ensure computational tractability, the thesis develops a rigorous theorical foundation based on VC-dimension and ()-approximation theory. These results formally prove that GLE can be estimated with bounded error using a limited number of graphlet samples, providing explicit guarantees for convergence and accuracy. This theorical framework bridges the gap between exhaustive enumeration and efficient randomized approximation, allowing GLE to scale to large networks. The methodology was validated on multiple brain networks, including the Mouse Visual Cortex and Imaginary Speech EEG networks. Experimental evaluations compared GLE with established metrics such as betweenness centrality, clustering coefficient, degree centrality and traditional local efficiency. The result confirm that GLE reveals finer-grained organizational differences and maintains high accuracy under sampling, in agreement with theorical predictions. Overall, the proposed GLE framework unifies structural interpretability, theorical rigor and computational efficiency. It provides a new tool for exploring higher-order organization in biological and cognitive networks, with promising directions for future work including the incorporation of 5-node graphlets, adaptive weighting strategies and extensions to dynamics or weighted network models
  9. Keywords:
  10. Brain Networks ; Graphlet ; Local Efficiency ; Graphlet-based Local Efficiency (GLE) ; Important Node

 Digital Object List

 Bookmark

...see more