Boolean Gossip Networks

doi:10.1109/TNET.2017.2763964

CSpace > 系统科学研究所

	Boolean Gossip Networks
	Li, Bo1 ; Wu, Junfeng 2; Qi, Hongsheng3,4 ; Proutiere, Alexandre 5; Shi, Guodong 6
	2018-02-01
发表期刊	IEEE-ACM TRANSACTIONS ON NETWORKING
ISSN	1063-6692
卷号	26 期号:1 页码:118-130
摘要	This paper proposes and investigates a Boolean gossip model as a simplified but non-trivial probabilistic Boolean network. With positive node interactions, in view of standard theories from Markov chains, we prove that the node states asymptotically converge to an agreement at a binary random variable, whose distribution is characterized for large-scale networks by mean-field approximation. Using combinatorial analysis, we also successfully count the number of communication classes of the positive Boolean network explicitly in terms of the topology of the underlying interaction graph, where remarkably minor variation in local structures can drastically change the number of network communication classes. With general Boolean interaction rules, emergence of absorbing network Boolean dynamics is shown to be determined by the network structure with necessary and sufficient conditions established regarding when the Boolean gossip process defines absorbing Markov chains. Particularly, it is shown that for the majority of the Boolean interaction rules, except for nine out of the total 2(16) - 1 possible nonempty sets of binary Boolean functions, whether the induced chain is absorbing has nothing to do with the topology of the underlying interaction graph, as long as connectivity is assumed. These results illustrate the possibilities of relating dynamical properties of Boolean networks to graphical properties of the underlying interactions.
关键词	Boolean networks gossiping process Markov chains communication classes
DOI	10.1109/TNET.2017.2763964
语种	英语
资助项目	National Natural Science Foundation of China[11301518] ; National Natural Science Foundation of China[61333001] ; National Natural Science Foundation of China[61733018] ; National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences ; Australian Department of Education and Training through an Endeavour Fellowship
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000425324000009
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/29705
专题	系统科学研究所
通讯作者	Wu, Junfeng
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Key Lab Math Mechanizat, Beijing 100190, Peoples R China 2.Zhejiang Univ, Coll Control Sci & Engn, Hangzhou 310027, Zhejiang, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Key Lab Syst & Control, Beijing 100190, Peoples R China 4.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 5.KTH Royal Inst Technol, Signals & Syst Linnaeus Ctr, Auton Complex Commun nEtworks, S-10044 Stockholm, Sweden 6.Australian Natl Univ, Res Sch Engn, Canberra, ACT 0200, Australia
推荐引用方式 GB/T 7714	Li, Bo,Wu, Junfeng,Qi, Hongsheng,et al. Boolean Gossip Networks[J]. IEEE-ACM TRANSACTIONS ON NETWORKING,2018,26(1):118-130.
APA	Li, Bo,Wu, Junfeng,Qi, Hongsheng,Proutiere, Alexandre,&Shi, Guodong.(2018).Boolean Gossip Networks.IEEE-ACM TRANSACTIONS ON NETWORKING,26(1),118-130.
MLA	Li, Bo,et al."Boolean Gossip Networks".IEEE-ACM TRANSACTIONS ON NETWORKING 26.1(2018):118-130.