Journal of
Marketing Development and Competitiveness






Scholar Gateway


Abstracts prior to volume 5(1) have been archived!

Issue 5(1), October 2010 -- Paper Abstracts
Girard  (p. 9-22)
Cooper (p. 23-32)
Kunz-Osborne (p. 33-41)
Coulmas-Law (p.42-46)
Stasio (p. 47-56)
Albert-Valette-Florence (p.57-63)
Zhang-Rauch (p. 64-70)
Alam-Yasin (p. 71-78)
Mattare-Monahan-Shah (p. 79-94)
Nonis-Hudson-Hunt (p. 95-106) 



JOURNAL OF STRATEGIC INNOVATION AND SUSTAINABILITY


The Wedge Picking Model: A Theoretical Analysis of Graph Evolution Caused by Triadic Closure and Algorithmic Implications


Author(s): Sara Ahmadian, Shahrzad Haddadan

Citation: Sara Ahmadian, Shahrzad Haddadan, (2021) "The Wedge Picking Model: A Theoretical Analysis of Graph Evolution Caused by Triadic Closure and Algorithmic Implications," Journal of Strategic Innovation and Sustainability, Vol. 16, Iss. 3, pp.74-93

Article Type: Research paper

Publisher: North American Business Press

Abstract:

Social networks have become an inseparable part of human life and processing them in an efficient manner is a top priority in the study of networks. These networks are highly dynamic and they are growing incessantly. Inspired by the concept of triadic closure, we propose a probabilistic mechanism to model the evolution of these dynamic graphs. Although triadic closure is ubiquitous in social networks and its presence helps forming communities, probabilistic models encapsulating it have not been studied adequately. 

We theoretically analyze our model and show how to bound the growth rate of some characteristics of the graph, such as degree of vertices. Leveraging our theoretical results, we develop a scheduling subroutine to process modifications of the graph in batches. Our scheduling subroutine is then used to speed up the state-of-the-art algorithms with negligible loss in their approximation guarantees. We demonstrate the applicability of our method by applying it to the densest subgraph and tri-densest subgraph discovery problem. Our theoretical findings are accompanied by extensive experimental evaluations.