A model of task-deletion mechanism based on the priority queueing system of Barabási

来自集智百科
跳转到: 导航搜索


目录

Highlights

1、在Barabási决策模型中添加任务删除机制

2、提出任务删除机制的决策模型

3、该模型可以产生丰富的人类行为模式的统计特性

4、结果有助于理解模式多样性的机制

5、有助于理解人类行为模式多样性的来源

摘要

在本文中,我们提出了一个基于Barabási(2005)的优先队列系统的任务删除机制模型,以深入研究人类行为的模式多样性。

任务删除参数的不同情况下,我们的模型可以产生丰富的统计行为模式,这与许多实证研究一致。

因此,该模型在理论上可以比Barabási模型解释更多的人类行为现象。 这些结果对于理解人类行为模式多样性的机制具有重要的意义。

概述

人们每天都会涉及很多不同的行为,从电子通讯(如发送电子邮件或拨打电话)到浏览互联网,进行金融交易或从事娱乐和体育活动。

个体的行为驱动着许多社会,技术和经济的发展,动力学将人类行为的量化理解转化问题是现代科学的核心。


简述Barabasi模型原理

1、假设每个任务的执行都是独立于其他任务的,并且以恒定的速度(constant rate)执行。 因此,执行任务的过程可以通过泊松过程很好地建模,例如发送电子邮件或拨打电话。由同一个人连续执行两个任务之间的时间间隔(称为等待时间)遵循指数分布。

2、后来随着对人类行为的深入研究,越来越多的证据表明,大量人类行为的时间遵循非泊松统计,其特点是长时间不活动的快速发生的事件爆发。

3、执行任务的等待时间表现出重尾现象,遵循幂律分布。 Barabási提出了一个优先级排队系统来模拟人类行为中的过程,人类扮演着服务器的角色

Barabási的人类过程模型很好地展示了重尾分布。

在极值动力学极限(extremal dynamic limit)中,当个体首先选择最高优先级的任务时,数值模拟和启发式论证显示大多数任务是在一个时间步中执行的,而等待多于一个时间步的任务的等待时间分配则表现为重尾和遵循的过程幂律分布。

获得了具有两个任务的Barabási模型的等待时间分布的确切结果。 Barabási的模型对我们理解人类行为中幂律分布的起源,例如网络社区中的幂律分布。 这些发现对通信和零售业都有重要的影响,例如资源管理、服务分配。

除了现实世界中普遍存在的指数分布和幂律分布之外,还有大量的实验研究表明,人类的行为模式既不完全是泊松分布也不是幂律分布,而是幂函数和指数函数的混合分布。人类行为模式可能是幂律分布,被清晰地截断(例如指数截断)

Barabási模型不能完全解释这种不同的统计模式。 如何解释人类行为的模式多样性,是否存在导致人类行为模式多样性的来源。 所有这些问题都需要深入研究。


任务删除模型

我们试图探索导致人类行为模式多样性的来源。

1、在Barabási模型中,一个人跟踪一个需要执行许多活动任务的列表,并为每个任务分配一个优先级。

2、优先级最高的任务决定被执行的等待时间呈现幂律分布。

3、在大多数由人类发起的行为中,个体确实首先执行具有最高优先级的任务。但时间有限,人们可能不会执行所有的任务。

4、当一个任务的优先级低于一定的阈值时,人们将决定删除它。

例子:比如在现代社会,大多数人都有这样的经历,他们经常收到电子邮件或手机短信。如果他们认为电子邮件或短信很重要,他们会回复。如果没有,他们将不会回复它,并从邮箱或手机中删除它。不同人之间的门槛(threshold)也可能不同。我们猜想任务删除机制可能是导致人类行为模式多样性的源头。

本文在Barabási模型的优先级排队系统中增加了任务删除机制,以深入研究人类行为的模式多样性。

首先,详细描述了任务删除机制的模型。 我们在执行任务的过程中计算两个任务的优先级和等待时间分布。 针对任务删除机制的模型得到了确切的结果。

其次,对模型进行了仿真,并对仿真结果进行了深入的讨论。

第三,总结我们的工作,探讨我们工作的意义。

最后,(向Barabasi)我们表示感谢。


模型和分析结果

模型

(i)个体有一个列表,其中有L个活动任务,他或她需要执行。 根据概率密度函数ρ(x)为每个活动任务分配优先级x(0≤x≤1)

(ii)在每个时间步骤,个体以概率p从列表中选择具有最高优先级的任务,并以概率1 - p随机选择任务,与其优先级无关。

(iii)删除任务有一定的删除阈值μ,称为μ(0≤μ≤1)。 如果所选任务的优先级低于某一阈值μ,则不执行所选任务并从列表中删除,也不记录所选任务的等待时间。 如果不是,则执行所选任务,从列表中移除,并记录所选任务的等待时间。 无论选择的任务是否被执行,此时新的任务被添加到列表中,优先级为ρ(x)。

数值模拟表明,L = 2的情况已经显示了Barabási模型的相关特征。

因此,我们接下来考虑两个任务的模型,并获得模型的确切结果,计算优先级和等待时间分布。

(iv)在每个时间步骤,从ρ(x)重新分配优先级x的所选任务将被称为新任务,另一个任务将被称为旧任务。

(v)在静止状态下,新任务和旧任务的优先级概率函数与时间无关。

新任务的优先级概率密度函数和概率分布函数分别为:ρ(x)和 R(x)= \int_{0}^{x} \rho (x')dx'

旧任务的优先级概率密度函数和概率分布函数分别为:ρ(x)和 R_{1}(x)= \int_{0}^{x} \rho_{1} (x')dx'

如果旧任务的优先级为x,则选择新任务的概率为 q(x)=p[1-R(x)]+\frac{1}{2}(1-p) (1)

如果新任务的优先级为x,则选择旧任务的概率为 q_{1}(x)=p[1-R_{1}(x)]+\frac{1}{2}(1-p) (2)

一个任务被选中后,旧任务将具有分布函数: R_{1}(x)=\int_{0}^{x}\rho _{1}(x')q(x')dx'+ \int_{0}^{x}\rho (x')q_{1}(x')dx' (3)

使用方程(1)-(2)和积分方程(3)我们得到 R_{1}(x)=\frac{(1+p)R(x)}{1-p+2pR(x))} (4)

(vi)在静止状态下,我们计算执行任务的优先级和等待时间分布。 在某个时间步骤,具有优先级x(x≥μ)的任务被添加到队列中。

(vii)等待τ个时间步骤执行的概率由第一个τ-1个时间步中未被选择的概率与第τ个时间步中选择的概率的乘积给出。

  • 和掷骰子原理相同,前(n-1)次未掷中概率*第n次掷中的概率

(vii)在第一个时间步中未被选择的概率是q1(x),在随后的τ-2个时间步中没有被选择的概率是q(x),并且在在第τ个时间步骤被选中的概率则是1-q(x)

(ix)如果所选任务的优先级低于某个阈值μ(0≤μ≤1),则不执行所选任务,从列表中删除,所选任务的等待时间也不记录。

(x)同时将新任务添加到列表中,其优先级从ρ(x)重新分配。 因此,在任务等待τ个时间步骤执行的过程中,个体选择了n(n≥τ)个任务。 在n个选择的任务中,只有τ任务的优先级高于或等于阈值μ,其他n-τ任务的优先级低于阈值μ。

基于以上分析,具有优先级x(x≥μ)的执行任务的等待时间分布可以如下获得: WX20171106-114101@2x.png

其中f(x),f 1(x),g(x)和g 1(x)是: WX20171106-114426@2x.png

我们假设每个任务的优先级从一个均匀分布ρ(x)= 1分配。可以得到这个结果: WX20171106-114524@2x.png

使用方程 (1) - (2),方程 (6) - (9),并将方程(5)积分得到: WX20171106-114728@2x.png

其中α,β和γ如下: WX20171106-114831@2x.png

——》 具有两个任务的等待时间分布是幂函数和指数函数的混合分布。

在一个μ= 0的情况下,模型是到Barabási模式,并从方程 (10)得出: WX20171106-114957@2x.png

分析结果与Vázquez的结果一致。 当p → 0 从方程 (12)我们得出: WX20171106-115112@2x.png

在随机选择任务协议条件(condition of random selection protocol)下,活动任务的等待时间分布呈指数分布。 当p → 1从方程 (12)我们得出: WX20171106-115306@2x.png

当τ → ∞,方程(14): WX20171106-115359@2x.png

在优先级最高的第一选择协议(condition of highest priority first selection protocol)的条件下,等待时间分布遵循τ→∞的幂律分布。

在另一个μ≠0的情况下,当p → 0等式 (10)得出: WX20171106-115646@2x.png

随机选择协议的限制在于,在每个步骤时间以概率1/2选择任务,并且等待时间分布遵循指数分布并且与删除参数μ有关。 当p →1从方程 (10)得出: WX20171106-115804@2x.png

当τ→∞时,得到: WX20171106-115851@2x.png

最高优先级首选协议的局限在于,优先级最高的任务就会被选中(失去概率随机性),并且在τ→∞,概率分布P(τ)遵循幂指数截止的幂律分布。

分析结果

在任务删除参数的不同情况下,上述分析结果表明,该模型能够产生丰富的统计特性,如指数函数与幂函数的混合分布,指数分布,幂律分布和带有指数截断的幂律分布等,这是符合大量的实证研究。 这些表明将任务删除机制添加到Barabási模型的方法是合理的。 任务删除模型在理论上可以解释人类行为的模式多样性。

它证实了我们的猜想:

任务删除机制可能是导致人类行为模式多样性的源头。

Figture

WX20171106-120008@2x.png

图1. 根据公式(10),在对数图中P和τ之间任务删除机制模型的模拟结果。 参数L = 2,p = 0.99999。 在μ= 0.00,0.01,0.10,0.50和0.90 分别对应 浅蓝色的点,红色的方块,绿色的菱形,蓝色的三角形和黑色的三角形。

WX20171106-120207@2x.png

图2.对数图中根据公式(10)的分析结果。 参数p = 0.99999; μ从0到1,τ被从2到1000。

WX20171106-120348@2x.png

图3.分析结果与对数图中的模拟结果之间的比较。 参数p = 0.99999和μ= 0.01。 黑色实线是根据方程(18)的分析结果,红点线是仿真结果; τ为2到1000的值。

WX20171106-120712@2x.png

图4.在μ= 0和μ= 0.5下,方程(2)的两个分析结果之间的比较方程(10)(log–log plots,两边都取了对数)。 (a)和(b)分别对应μ= 0和μ= 0.5。


仿真结果

概率P(τ)对参数μ有高度敏感度

在参数μ的不同情况下,图1示出了在选择具有最高优先级的任务的决定下P和τ之间任务删除机制的模型的仿真结果。

当μ= 0时,第一步中未被选择的任务的等待时间分布具有幂律尾,并遵循幂律概率分布,并且这些结果可以通过分析解方程(14)来验证;

当μ= 0.01时,概率P(τ)遵循幂函数和指数函数的混合分布,这个结果可以通过分析解方程(17)来验证。

因此,概率P(τ)对参数μ有高度敏感度(高关联性)。

μ、τ、P之间的关联性

图2显示了方程(10)在log–log plot中的分析结果。

删除阈值μ在0到1之间变化。

随着μ的增加,P与τ之间的关系从线性幂律分布变为指数截断的曲线幂律分布。

由参数p = 0.99999,这些变化可以通过方程(15)和(18)的极限分析解来验证。

在μ= 1的条件下,随着τ的增加,P迅速下降,当τ≥200时,P低于10的-300次方,这表明P对τ高度敏感,而长等待时间τ几乎不出现。

图3显示了方程(10)的分析结果的仿真结果之间的比较。分析结果与模拟结果一致。也就是说极限分析解方程(18)是可靠的。

μ与模式多样性

图4显示了方程(10)在μ= 0和μ= 0.5的两个条件下两个分析结果之间的比较,其中(a)图和(b)图分别对应μ= 0和μ= 0.5。

当p = 0时,任务删除机制的模型对应Barabási模型。

因此,图4(a)显示了Barabási模型的优先级排队系统的结果,随着p的增加,P与τ之间的关系从指数分布变为幂律分布,这些变化可以由方程(13)和(15)极限分析解方程验证 。然而,在图4(b)中,随着p从0到1,等待时间分布P(τ)从指数分布变化到具有指数截止的幂律分布,并且可以验证这些变化由方程(16)和(18)极限分析验证。

因此,删除阈值μ在P和τ之间的等待时间分布的模式多样性中起着非常重要的作用。

结论

综上所述,在Barabási模型的优先级排队系统中增加了任务删除机制,以便深入研究人类行为的模式多样性。

我们给出了两个任务模型的分析过程, The analytical solution of the model with two tasks is provided.

通过分析推导出紧凑的近似值(compact approximations),并通过仿真结果进行验证。

随着任务删除参数的变化,执行任务的等待时间分布发生变化,例如指数函数和幂函数的混合分布、指数分布、幂律分布、带有指数截断的幂律分布等。

我们的模型中丰富的统计模式与大量的实证研究一致。 The rich statistical patterns of our model are consistent with lots of empirical studies.

因此,与以前Barabasi的模型相比,我们的模型和解析结果可以用来从理论上解释人类行为的多样性。 揭示各种人类活动时间的机制具有重大的科学和商业潜力。

人类行为模式对于社会组织行为的大规模模拟是非常必要的,从模拟城市细节到模拟金融市场行为。 因此,目前的模型可以扩展和应用到更一般的情况。 我们的工作有助于理解人类行为模式多样性的来源。

参考文献

[1] J.H. Greene, Production and Inventory Control Handbook, Vol. 2002, McGraw-Hill, New York, 1987.

[2] P. Reynolds, Call Center Staffing, The Call Center School Press, Lebanon, Tennessee.

[3] H.R. Anderson, Fixed Broadband Wireless System Design, John Wiley & Sons, 2003.

[4] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 2, John Wiley & Sons, 2008. B. Zhou et al. / Physica A 466 (2017) 415–421

[5] V. Paxson, S. Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Trans. Netw. 3 (3) (1995) 226–244.

[6] S.D. Kleban, S.H. Clearwater, Hierarchical dynamics, interarrival times, and performance, ACM/IEEE Supercomput. (2003) 28–28.

[7] J. Masoliver, M. Montero, G.H. Weiss, Continuous-time random-walk model for financial distributions, Phys. Rev. E 67 (2) (2003) 021112.

[8] A. Vázquez, J.G. Oliveira, Z. Dezsö, K.-I. Goh, I. Kondor, A.-L. Barabási, Modeling bursts and heavy tails in human dynamics, Phys. Rev. E 73 (3) (2006) 036127.

[9] A.-L. Barabasi, The origin of bursts and heavy tails in human dynamics, Nature 435 (7039) (2005) 207–211.

[10] A. Vazquez, Exact results for the barabási model of human dynamics, Phys. Rev. Lett. 95 (24) (2005) 248701.

[11] S.L. Johnson, S. Faraj, S. Kudaravalli, Emergence of power laws in online communities: The role of social mechanisms and preferential attachment, Mis

[12] E. Scalas, T. Kaizoji, M. Kirchler, J. Huber, A. Tedeschi, Waiting times between orders and trades in double-auction markets, Physica A 366 (2006) 463–471.

[13] S.-C. Wang, J.-J. Tseng, C.-C. Tai, K.-H. Lai, W.-S. Wu, S.-H. Chen, S.-P. Li, Network topology of an experimental futures exchange, Eur. Phys. J. B 62 (1) (2008) 105–111.

[14] H.-B. Hu, D.-Y. Han, Empirical analysis of individual popularity and activity on an online music service system, Physica A 387 (23) (2008) 5916–5921.

[15] J. Oliveira, A. Vazquez, Impact of interactions on human dynamics, Physica A 388 (2) (2009) 187–192.

[16] Y. Wu, C. Zhou, J. Xiao, J. Kurths, H.J. Schellnhuber, Evidence for a bimodal distribution in human communication, Proc. Natl. Acad. Sci. 107 (44) (2010) 18803–18808.

[17] A. Scherrer, P. Borgnat, E. Fleury, J.-L. Guillaume, C. Robardet, Description and simulation of dynamic mobility networks, Comput. Netw. 52 (15) (2008) 2842–2858.

[18] H. Li, Workload dynamics on clusters and grids, J. Supercomput. 47 (1) (2009) 1–20.

[19] J.C. Bohorquez, S. Gourley, A.R. Dixon, M. Spagat, N.F. Johnson, Common ecology quantifies human insurgency, Nature 462 (7275) (2009) 911–914.

[20] R. Xue-Zao, Y. Zi-Mo, W. Bing-Hong, Z. Tao, Mandelbrot law of evolving networks, Chin. Phys. Lett. 29 (3) (2012) 038904.

[21] T. Zhou, Z.-D. Zhao, Z. Yang, C. Zhou, Relative clock verifies endogenous bursts of human dynamics, Europhys. Lett. 97 (1) (2012) 18006.

[22] M.E. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. 98 (2) (2001) 404–409.

[23] O. Mryglod, Y. Holovatch, Towards journalometrical analysis of a scientific periodical: a case study, arXiv preprint arXiv:0707.3696.

[24] M. Vojnović, On mobile user behaviour patterns, in: 2008 IEEE International Zurich Seminar on Communications, IEEE, 2008, pp. 26–29.

[25] J. Candia, M.C. González, P. Wang, T. Schoenharl, G. Madey, A.-L. Barabási, Uncovering individual and collective human dynamics from mobile phone records, J. Phys. A 41 (22) (2008) 224015.

[26] H. Chun, H. Kwak, Y.-H. Eom, Y.-Y. Ahn, S. Moon, H. Jeong, Comparison of online social relations in volume vs interaction: a case study of cyworld, in: Proceedings of the 8th ACM SIGCOMM Conference on Internet Measurement, ACM, 2008, pp. 57–70.

[27] A. Grabowski, Human behavior in online social systems, Eur. Phys. J. B 69 (4) (2009) 605–611.

[28] P. Wang, X.-Y. Xie, C.H. Yeung, B.-H. Wang, Heterogenous scaling in the inter-event time of on-line bookmarking, Physica A 390 (12) (2011) 2395–2400.

[29] O. Mryglod, Y. Holovatch, I. Mryglod, Editorial process in scientific journals: analysis and modeling, Scientometrics 91 (1) (2011) 101–112.

[30] Z.-Q. Jiang, W.-J. Xie, M.-X. Li, B. Podobnik, W.-X. Zhou, H.E. Stanley, Calling patterns in human communication dynamics, Proc. Natl. Acad. Sci. 110 (5) (2013) 1600–1605.

个人工具
名字空间
操作
导航
工具箱