On dynamic monopolies of graphs with probabilistic thresholds

Authors

  • H. Soltani
  • M. Zaker

Keywords:

graph theory

Abstract

Let \(G\) be a graph and \({\mathcal{\tau}}\) be an assignment of nonnegative thresholds to the vertices of \(G\). A subset of vertices, \(D\), is an irreversible dynamic monopoly of \((G, \tau)\) if the vertices of \(G\) can be partitioned into subsets \(D_0, D_1, \ldots, D_k\) such that \(D_0=D\) and for all \(i\in \{0, \ldots, k-1\}\), each vertex \(v\) in \(D_{i+1}\) has at least \(\tau(v)\) neighbours in the union of \(D_0\cup \ldots \cup D_i\). Dynamic monopolies model the spread of influence or propagation of opinion in social networks, where the graph \(G\) represents the underlying network. The smallest cardinality of any dynamic monopoly of \((G,\tau)\) is denoted by \(dyn_{\tau}(G)\). In this paper we assume that the threshold of each vertex \(v\) of the network is a random variable \(X_v\) such that \(0\leq X_v \leq deg_G(v)+1\). We obtain sharp bounds on the expectation and the concentration of \(dyn_{\tau}(G)\) around its mean value. We also obtain some lower bounds for the size of dynamic monopolies in terms of the order of graph and expectation of the thresholds. DOI:- 10.1017/S0004972714000604

Published

2014-09-20

Issue

Vol. 90 No. 3 (2014)

Section

Articles
In these notes, the Australian Mathematical Publishing Association Incorporated, Cambridge Journals Online, Cambridge University Press, and the Bulletin are abbreviated to AMPAI, CJO, CUP, and the Bulletin.

Copyright is held by AMPAI. Under the standard arrangement, the article will be made freely accessible to the public five (5) years after publication. Alternatively, for an initial fee of $USD600, immediate open access under a creative commons license will be provided on the CUP online platform.

  1. The Bulletin's policy is to acquire copyright for as many articles as possible, for two reasons:
    1. ownership of copyright by one central organisation tends to ensure maximum international protection against unauthorised use;
    2. it also ensures that requests by third parties to reprint or reproduce a contribution, or part of it, are handled efficiently and in accordance with a general policy that is sensitive both to any relevant changes in international copyright legislation and to the general desirability of encouraging the dissemination of knowledge.
  2. Copyright acts in various countries confer 'moral rights' on authors. In some cases, an author's 'right of paternity', that is the right to be properly credited whenever the work is published (or performed or broadcast), must be asserted in writing.
  3. Notwithstanding the assignment of copyright in their contribution, all authors retain the following non-transferable rights:
    1. The right to post the abstract and a link to the online edition of the Bulletin at CJO or at the Bulletin website.
    2. The right to post the definitive version of the contribution as published at CJO (in PDF or HTML) in the Institutional Repository of the institution in which they worked at the time the paper was first submitted, no sooner than two years after first publication of the paper in the journal, subject to file availability and provided the posting includes a prominent statement of the full bibliographical details, a copyright notice in the name of the copyright holder (AMPAI or another body, as appropriate), and a link to the online edition of the Bulletin at CJO. Inclusion of this definitive version after two years in Institutional Repositories outside of the institution in which the author worked at the time the paper was first submitted will be subject to the additional permission of CUP on behalf of AMPAI (not to be unreasonably withheld).
    3. The right to make hard copies of the article or an adapted version for their own purposes, including the right to make multiple copies for course use by their students, provided no sale is involved.
    4. The right to reproduce the paper or an adapted version of it in any volume of which they are an editor or an author, but otherwise permission must be sought from CUP. Permission will automatically be given to the publisher of such a volume, subject to normal acknowledgement.
  4. CUP (on behalf of AMPAI) will use its best endeavours to ensure that any direct request received to reproduce a contribution, or a substantial part of it, in another publication (which may be an electronic publication) is approved by the contributor before permission is given. Multiple authors should nominate one author only to respond to such requests.
  5. CUP co-operates in various licensing schemes that allow material to be photocopied within agreed restraints (e.g., the CCC in the USA and the CLA in the UK). Any proceeds received from such licenses, together with any proceeds from sales of subsidiary rights in the Bulletin, directly support its continuing publication.
  6. It is understood that in some cases copyright will be held by the contributor's employer. If so, CUP (on behalf of AMPAI) requires exclusive permission to deal with requests from third parties, on the understanding that any requests received from third parties will be handled in accordance with paragraphs 4 and 5 above (note that approval will be sought for the proposed use from the contributor, not the employer).
  7. If a contribution includes textual or illustrative material not in your copyright and not covered by fair use/fair dealing, permission must be obtained from the relevant copyright owner (usually the publisher or via the publisher) for the nonexclusive right to reproduce the material worldwide in all forms and media, including electronic publication. The relevant permission correspondence must be attached to this form. If in doubt about whether or not permission is required, please consult: the Permissions Controller, Cambridge University Press, The Edinburgh Building, Shaftesbury Road, Cambridge CB2 2RU, UK. Fax: +44 (0)1223 315052. Email: lnicol@cambridge.org.
  8. The information provided on this form will be held in perpetuity by AMPAI for record purposes. The name(s) and address(es) of the author(s) of the contribution may be reproduced in the Bulletin and provided to print and online indexing and abstracting services and bibliographic databases