A dynamic sampling algorithm based on learning automata for stochastic trust networks

• Published in: Knowledge-based systems 2021-01, Vol.212, p.106620, Article 106620
• Main Authors: Ghavipour, Mina, Meybodi, Mohammad Reza
• Format: Article
• Language: English
• Subjects: Algorithms; Graph measures; Graph theory; Learning automata; Literature reviews; Machine learning; Network sampling; Random variables; Sampling methods; Social networks; Stochastic graphs; Stochastic models; Trust; Trust networks
• ISSN: 0950-7051; 1872-7409
• DOI: 10.1016/j.knosys.2020.106620

Trust is known as an important social concept and an effective factor in all human interactions in social networks. Users tend to interact with trusted people with whom they have had positive experiences. Trust is updated over time as a result of these repeated interactions. Even though dynamicity is a universally accepted property of the social trust, trust networks are often modeled as static digraphs. In this paper, we first propose that a stochastic graph model, where the weights associated with edges are random variables with unknown distributions, may be a better candidate for representing trust networks. Then, we review the literature on analyzing complex networks and determine graph measures which are most appropriate with respect to the special properties of the concept of trust. Considering trust-specific measures, we finally propose a dynamic algorithm for sampling from stochastic trust networks, which is an extension of Frontier sampling. Even though there exist a few sampling methods which address edge weights and their variations over time through the sampling process, these methods are unable to accurately preserve the properties of trust networks. The proposed algorithm in this paper uses learning automata to tackle the disconnectivity problem of sampled subgraphs by Frontier sampling and, at the same time, capture the changes of edge weights through the sampling process. Our experimental results on the well-known trust network datasets indicate that the proposed sampling algorithm preserves more accurately the trust-specific measures of trust networks compared to existing sampling methods. •A stochastic graph model for representing trust networks is recommended.•We present a comprehensive review of the literature on analyzing complex networks.•New extensions of some graph measures are proposed, considering properties of trust.•We develop a dynamic sampling algorithm for stochastic trust networks.•The experimental results show the benefits of our proposed sampling algorithm.