{'fraction_non_alphanumeric': 0.04089886504385632, 'fraction_numerical': 0.012714542099542479, 'mean_word_length': 4.226846346941472, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Centralization Problem for Opinion Convergence in Decentralized Networks

This paper aims to provide a new perspective on the interplay between decentralization -- a prevalent character of multi-agent systems -- and centralization, i.e., the task of imposing central control to meet system-level goals. In particular, in the context of networked opinion dynamic model, the paper proposes and discusses a framework for centralization. More precisely, a decentralized network consists of autonomous agents and their social structure that is unknown and dynamic. Centralization is a process of appointing agents in the network to act as access units who provide information and exert influence over their local surroundings. We discuss centralization for the DeGroot model of opinion dynamics, aiming to enforce opinion convergence using the minimum number of access units. We show that the key to the centralization process lies in selecting access units so that they form a dominating set. We then propose algorithms under a new local algorithmic framework, namely prowling, to accomplish this task. To validate our algorithm, we perform systematic experiments over both real-world and synthetic networks and verify that our algorithm outperforms benchmarks.


INTRODUCTION
Opinion dynamics aims to illustrate how opinions of individuals evolve in a crowd [10], so as to provide insights on important challenges in multi-agent systems such as group decision making [13].
In an opinion dynamics model, every agent holds an opinion towards a certain issue. The agents interact by revealing their opinions to others, and in turn updating their opinions as a result of such interactions. Such a model is decentralized in the following sense. First, the agents' states, which capture not only their opinions but also with whom they interact, evolve in a way without the control of a higherlevel entity, i.e., the "system controller". Second, in the presence of a large number of agents, any potential system controller has only partial information about these states, meaning that agents' opinions and their social interactions are not directly accessible. In such a decentralized system, however, the agents may fail to reach a consensus, a key objective of the opinion dynamic process. Therefore a need arises to impose some coordinated control.
The interplay between decentralized systems and centralized control has been the subject of intense studies, with implications in fields like networking, political science, and information systems [14,15,27]. Going along with this theme, we formulate decentralized networks to capture the type of opinion dynamics models described above. In short, a decentralized network consists of agents whose repeated interactions form a social network, while unifying the following properties. (1) Dynamic topology: Here, the social network is not static but rather it changes with time. There has been a growing interest in dynamic networks as well as how changes to the network topology affect opinions [23,25]. (2) Unknown topology: The social networks are not provided upfront due to their scale and the locality of knowledge. The study of these types of networks requires discovering the network topology through some form of exploration [17,24,28,33]. Over a decentralized network, we define a process of centralization that imposes central control via two functionalities: monitoring, meaning that a number of agents are appointed as access units to gather information about a local region; and influencing, meaning that these access units may exert influence to the agents as directed by the system controller. This setup captures two extrema: (1) when no agent is an access unit, which means that the system is fully decentralized, and (2) when all agents are access units, which means that the system is fully centralized. Centralization refers to the process of appointing access units, starting from extrema (1), moving towards extrema (2) until an appropriate level of control is imposed. The challenge is to adopt suitable strategies to explore the unknown and dynamic social network and appoint access units along the way.
This paper focuses on the centralization problem for opinion convergence. We propose a decentralized version of the well-established DeGroot model to drive agents' opinions [11]: The opinion of an agent is a real value in r0, 1s, which is updated by the average opinion of neighboring agents. The goal is to have the opinions of all agents converged to 1. One paradigm to achieve this, as proposed in [25], is to deploy "committed agents" whose opinion is fixed at 1. We model these committed agents as the access units in our centralization processes. We now summarize our contributions: (1). We define decentralized networks and formulate the centralization problem over decentralized DeGroot model. These are presented in Sections 3 and 4. These notions can potentially be defined for other tasks such as influence maximization or norm emergence [24,30], thereby triggering fruitful new research.
(2). We seek to effectively facilitate opinion convergence using the minimum number of access units. We establish a connection between finding a dominating set, an important concept in network theory, and the centralization problem for opinion convergence. We provide theoretical results and algorithms in Sec. 4 and 5. These form the backbone of our experimental results in the last section.
(3). We explore local algorithms [7] to solve the centralization problem. For this, we propose a new algorithmic framework, prowling, that probes an unknown network while selecting access units. We design three prowling algorithms: one exterior-based, and two Bset prowling algorithms (see Section 5). These algorithms ensure opinion convergence under general conditions. Through empirical validation over dynamic real-world and synthetic datasets, we validate the effectiveness of our algorithms (See Section 6).

RELATED WORK
This paper is related to work on local algorithms which aims to identify global properties of a graph using only local information [7]. For example, [5] proposes an algorithm that explores an unknown network by repeating the following: greedily select a "known" node, and then make a random move to an unknown neighbor of the selected node. This method guarantees to cover a (static) graph using a small set of nodes that has a plogpΔqq-factor from an optimal set, where Δ is the maximum degree. If we view nodes traversed by the local algorithm as access units, then this work fits the framework studied in our paper. Wilder et al. utilize local algorithms for influence maximization [28], where they design a probing mechanism to collect information, i.e., walks in the unknown part of the network. The structural statistics collected by repeated probes direct the selection of seed nodes, which can also be considered as access units. In our paper, we adopt a different probing method. Instead of using probes as means to sample information, we implement a search procedure through the unknown part of the network to locate the next access unit. We call such types of algorithms prowling and consider this procedure as a less costly and adaptive alternative to the exploration strategy used in [28].
Opinion dynamics, with its application to group decision making, has been intensively studied [1,12,13,16]. The vast majority of work on opinion dynamics assumes that the social network is given as input, implying that the input is both static and fully-known. This allows us to directly employ algorithms from graph theory and combinatorial optimization. Singh et al. [25] study the co-evolution of network structures and individual opinion and found that committed agents can accelerate opinion convergence. He et al. [17] investigate opinion maximization by selecting seed agents under the assumption of partial information on edge weights. Their work, however, omits information collection, which is important in real-world applications.
While no work exists that investigates opinion dynamics in unknown and dynamic social networks, several papers study the related topic of influence maximization in unknown networks. Social influence is normally modeled using a cascading model, giving rise to a submodular function. When the social network is not available, it is common to assume that sampled influence pairs are available to extract information regarding the social network [2,3,32]. These work invokes submodular function optimization, which is not applicable in models of opinion dynamics. Wu et al. [29] assume that the network topology is given while the edge weight is unknown in a cascade model. Zhuang et al. [33] study networks that are initially known, but the structural changes are only observable by probing. Their method first selects a set of probing nodes that reveal their neighborhood topology and then selects a set of seed nodes accordingly. Our setting is somewhat similar to [33] except that our network is not initially known, and we consider opinion dynamics rather than information diffusion.
Another aspect of our model, which is distinctive from all work we mentioned above, lies in selecting access units as an iterative process as the system evolves, i.e., centralization is adaptive. This resembles the setting of adaptive influence maximization that iteratively selects seed nodes while observing network evolution [30].

DECENTRALIZED NETWORK 3.1 The general setup
We define our general framework of decentralized networks, then we present an instance of this framework for opinion dynamics modeling. Assume that there is a fixed (possibly infinite) universal set of agents . These agents will be nodes of our social network. Let be a set of states of the agents. For any subset Ď , use r s 2 to denote the set of all pairs t , u Ď with ‰ . Definition 3.1. A network instance is a triple " p , , q where is a finite set of undirected edges Ď r s 2 , : Ñ assigns every agent in a state, and Ď is a set of access units.
Since we assume that is the de facto node set throughout the paper, Definition 3.1 does not explicitly include a node set in the graph. In the next definition, we represent time as " 0, 1, 2, . . .

Definition 3.2. A decentralized network is a triple
"`␣ p q | P r s 2 ( PN , t p q | P u PN , t u PNw here p q is a random variable with domain t0, 1u, p q is a random variable with domain , and Ď is a set of access units. Intuitively, for " t , u P r s 2 , p q " 1 iff there is an t , u at time , and for P , p q is the state of at time . The network instance at time is " p , , q, where " t P r s 2 | p q " 1u and p q " p q. We will therefore refer to also by the sequence t u PN . We assume that the sequences t u PN and t u PN are the outcomes of Markovian stochastic processes with known distributions t u Pr s 2 and t u P where any p`1q " p¨| , , q and any p`1q " p¨| , , q. Note also that this stochastic definition subsumes deterministic state transitions, i.e., function that produces p`1q given and . Indeed, our opinion dynamic model will adopt deterministic state transitions (see Sec. 3.2). Note that the sequence t u PN is not a stochastic process but rather a deterministic sequence of subsets of agents. The algorithms that we describe will ensure that Ď`1 for all P N. The system knows the dynamics of the agents.
The access units represent the means for a system controller to monitor and influence the agents: For any P , the accessible region of is a set AC p q Ď that contains . The accessible region of set is AC p q " Ť P AC p q. The accessible region plays two roles: (1) AC p q defines 's scope of influence. In other words, for any , 1 Ď , for any node P , p¨| , , q " p¨| , , 1 q whenever t P | P AC p qu " t P 1 | P AC p qu.
(2) AC p q bounds the information accessible by the system controller. In particular, only nodes in Y AC p q, their states, as well as all edges attached to AC p q are known by the system controller; any other information about the network is not accessible, nor influenced by the system controller. Note that, with these assumptions, the system controller can also tell whether there is a node R AC p q that is connected to a node in AC p q.

Decentralized DeGroot model
In the rest of this paper, the decentralized network will be a decentralized DeGroot model, which we define in this section. Assume that at any time , the network instance consists of only one (finite) non-trivial connected component Ď such that all edges and access units are from this connected component. We restrict ourselves to incremental networks where any edge, once appeared, will not be deleted, and thus Ď`1. The opinion of any node P z is irrelevant (therefore p q can be assumed to be 0 for simplicity). So, represents the agents that exist at time and we may write the network instance as the tuple p , , , q. We assume that the edges evolve independently of access units, i.e., p¨| , , q " p¨| , , 1 q for all and 1 . Write dist p , q for the length of a shortest path in for , P . The accessible region of node is parametrized by a radius : As is fixed, we write AC p¨q for AC p q p¨q. In principle, can be set to any positive integer, we usually assume that an access unit can only influence its close proximity and thus ď 2. Following DeGroot model [11], an opinion is a value in " r0, 1s, and agents align their opinion with their neighbors. The system controller imposes control as follows: (1) Each P is a "committed agent" with a fixed opinion at value 1. (2) Every P AC p q is assigned an "accessor" P , where P AC p q. This accessor has direct influence on in the sense that 's opinion at time`1 is the average of the opinion values of its non-neighbors at time and the opinion of fixed at 1. Formally, we define 1 : Definition 3.3. The decentralized DeGroot model is a decentralized network where the state transition function of nodes is set as: otherwise. (2)

THE CENTRALIZATION PROBLEM 4.1 Problem formulation
Centralization is a computational process performed by the system controller that selects access units in a decentralized network. As the network is initially unknown, selecting an access unit requires a form of "information gathering". Starting with an initial network instance p 0 , 0 , 0 , 0 q, where 0 " ∅, the process repeatedly executes a local algorithm that selects access units. When executed at time ą 0, the algorithm uses information provided in AC p´1q (states and edges of nodes) and returns a node R´1, which is the next access unit, i.e., "´1 Y t u.
We now propose a type of local algorithms called prowling. Let the closed neighborhood of P be p q " t P | distp , q ď 1u. The 1`-neighborhood`p q of node is a data structure containing the states of all P p q and their degrees in . ‚ Start at an agent 0 from AC p´1q. ‚ For 0 ď ă , if P AC p´1q, move from to a neighbor 1 of ; if R AC p´1q, then first inquire about the 1`neighborhood`p q and then move from to a neighbor`1 of based on the obtained information. ‚ The last agent is chosen as output.
The prowling algorithm resembles a name-generation process used in social network analysis [8], where an interviewer asks a participant (an agent in the network) to reveal the names of those who came into direct contact with the participant, then those whose names are revealed are asked the same question and so on. Note that every step of the prowling algorithm can make use of the degree of the current node. The length is a fixed parameter. Figure 1 illustrates a run of a 4-step prowling algorithm.
Initially the opinion values of all agents are 0: p0q " 0 for P . The desired outcome of a centralization process studied in this paper is when the opinions of all agents in converge to 1.
Definition 4.2. We say that the opinions converge in a decentralized network if @ ą 0, D ą 0, such that @ P : p q ě 1´. ( In this case, the p1´q-centralization cost of is | | where is the first time when (3) holds. The network centralization problem asks for a prowling algorithm to explore a decentralized network and select access units that achieve opinion convergence with the smallest centralization cost.
Remark. We now elaborate on the motivation behind the adoption of prowling, rather than other forms of local algorithms, in the network centralization problem: Firstly, the local algorithms as proposed in [5] explore a network without going beyond the "known region". This means that at every step, the selected access unit will always be a member of AC p´1q. While such approaches strictly adhere to "accessing only local information", over large networks, too many access units may be chosen for our purpose. Secondly, the type of probing algorithms proposed in [28] were used to sample paths in an unknown network. In this way, the next access unit may not be part of the currently accessible region. However, such a method may incur a high cost when a lot of repeated sampling is used to select one access unit. Moreover, this algorithm was designed for static networks assuming that the network structure stays stable between repeated sampling. Prowling, on the other hand, strikes a balance between the two types of local algorithms above. It allows the selection of nodes outside of the accessible region as the network evolves, while not incurring the high cost with repeated sampling.

From stabilized to unit-growth networks
To study the network centralization problem, we first consider the case when the network stabilizes at some time ℓ ą 0, i.e., that p q " pℓq for all P r s 2 and ą ℓ. PROOF. Let " mint | ‰ ∅u. For convenience and w.l.o.g., we prove the case when " ℓ, " t u for some P and p q " 0 for all P zt u. We show that @ P @ ě , p`1q ě p q. Indeed, for any P , let " min t P N | p`1q ă p q, ě u (where min ∅ " 8). Pick from argmin t | P zt uu. Suppose ă 8. Note that ą , as clearly for any P zt u, p`1q ě p q. Since p`1q ă p q and our model is a DeGroot model, there is a neighbor P p q such that p q ă p´1q. This means that p q ă p q, contradicting the def. of .
Thus, the opinion of each P ℓ is a monotonic sequence pℓq, pℓ`1q, . . . bounded by 1. Let˚be the limit of this sequence. Let be a node in argmin˚and assume˚ă 1. Then take such a that has the closest distance from . Since our model is a DeGroot model, among the neighbors of , there is an P ℓ p q with˚ą˚, and all other neighbors of have˚ě˚. This means that the sequence pℓq, pℓ`1q, . . . will eventually surpass˚. □ COROLLARY 4.4. If a decentralized DeGroot model stabilizes, then one access unit suffices for opinion convergence. □ When the network does not stabilize, the convergence theorem no longer holds. For example, when each time involves two (or more) nodes entering , it is impossible to guarantee the convergence of opinions. Nevertheless, when we assume that the network " t u PN has unit-growth, that is,´1 expands by at most one node P z´1 at each time , it is possible to guarantee convergence of opinions. In this case, a dominating set, a key notion in graph theory, plays a crucial role. Recall now the parameter from Section 3.2. The set is called (distance-) dominating for network instance if AC p q p q " .
Definition 4.5. A prowling algorithm is domination-driven if for any unit-growth decentralized network there is a time at which the algorithm produces that is dominating for .
Algorithm 1 is a centralization process that makes use of a domination-driven prowling algorithm. Note that the network evolution (Lines 4 & 9) is beyond our control. The while-loop repeatedly executes the prowl algorithm until dominates. From then on, the algorithm will select new access units whenever expands.  The network evolves to`1 and set Ð`1

5:
Ð prowlp´1q Ź -step prowl 6: Ð´1 Y t u 7: end while 8: repeat 9: The network evolves to`1 and set Ð`1 10: if zAC p´1q ‰ ∅ then Ź A new node enters 11: Select from zAC p´1q Ź is the only new node  PROOF. Suppose ℓ is dominating to ℓ at time ℓ ą 0. At the first time ą ℓ when there is a node P zAC p´1q, the algorithm selects the only node from zAC p´1q. Thus "´1 Y t u is dominating to . Repeating this procedure, one can prove inductively that for any 1 ą ℓ, 1 forms a dominating set to 1 that contains all nodes in 1 z . Using a similar argument as in Theorem 4.3, we can show that opinions in the sub-network restricted to nodes in ℓ converge, and hence the theorem holds. □ The domination cost p q of a domination-driven prowl on a unitgrowth network " t u PN consistent with prowl is the least at which dominates. The theorem above links the centralization and the domination costs: For any 0 ă ă 1, let be the least number of steps for all agents in p q "´p q , p q , p q , p q¯t o reach an opinion value of at least 1´. The p1´q-centralization cost is then no more than p q`. We will verify in our experiments that the value is negligible (close to 0) even for very small .

THE PROWLING ALGORITHMS
In the rest of the paper, we assume that the network has unit growth, and aim to look for a domination-driven prowling algorithm with the smallest domination cost.

Exterior-based Prowling
We exhibit a simple condition where a prowling algorithm is dominationdriven. Define the exterior set at time as X " zAC p´1q.
Definition 5.1. We say that a prowling algorithm prowlp´1q is exterior-based if the algorithm returns a node P X .
We aim to prove that exterior-based prowling algorithms are domination-driven if the radius ě 2. Assume that at each time ą 0, a new node R AC p´1q enters , i.e., "´1 Y t u. We need the following. At time , the access neighborhood is " Ť P p q, and anti-neighborhood is " z . We havé 1 Ď and Ď´1 Y t u. Note also that " ∅ implies that " , i.e., is a (distance-1) dominating set.
PROOF. Let be the node returned by the prowling algorithm prowlp´1q when it is executed at time . By assumption P X . Take a shortest path from to a node P´1 and let be the node adjacent to on that path. It is clear that R AC p´1q and P AC pt uq. This means that t , u Ď while t , u X 1 " ∅. Hence | z´1| ě 2. By Lemma 5.2, |´1|´| | ě | z´1|´1 " 1 and thus | | ă |´1|. Therefore for some 1 ą 0, 1 " ∅ which means that 1 is dominating. Moreover, at any time , the number of times before the anti-neighborhood becomes ∅ is at most | |. Hence the theorem is proved. □ By Theorem 5.3, a centralization process consistent with an exterior-based prowling algorithm (with ě 2) guarantees to produce a dominating set over a unit-growth decentralized network. Furthermore, the theorem also provides a sequence of upper bounds on the domination cost, i.e., To lower domination cost, it makes sense to minimize values in this sequence. As grows at a constant rate, this is equivalent to making the access neighborhood 1 , 2 , 3 , . . . grow as fast as possible. This naturally suggests selecting access units based on their degrees. We thus design the following exterior-based algorithm: Definition 5.4. We define xdegp´1q the -step degree prowling algorithm: Start from a random node 0 in AC p´1q that has an edge going out of AC p´1q, and move to a random neighbor 1 R AC p´1q. From (1 ď ă ), the algorithm selects among neighbors outside of AC p´1q one that (1) has a higher degree than , and (2) the degree is as high as possible, i.e., set 1 " argmaxtdegp q | P X , degp q ą degp qu. This step is repeated for at most´1 steps or until it is not possible to do so within steps.
The following directly follows from Thm. 5.3 and Thm. 4.7.
COROLLARY 5.5. If a unit-growth decentralized network is consistent with xdegp´1q with ě 2, then in opinions converge. □

B-set Prowling
The major downside of the exterior-based algorithms is that prowling is confined to the induced subgraph of the exterior set X , which forbids more central nodes from being selected. This is problematic, especially after several access units have been selected, when the exterior subgraph is fragmented and contains many isolated nodes. In such a case, the algorithm may have a high domination cost. Fig. 2 shows an example where an exterior-based algorithm performs poorly. Thus it is important to enable prowling to move within the accessible region. We therefore define B-set prowling algorithms. Recall that is the radius of the accessible region and set´1 "´1 if ě 2 and´1 " 1 if " 1. For any time ą 0, define the set " t P | distp , X q ď´1u.
Definition 5.6. A B-set prowling algorithm prowlp´1q is one that returns a node P . THEOREM 5.7. If ě 2, then a B-set prowling algorithm is domination-driven. Moreover, the domination cost is no more thaǹ | | for any ą 0.
PROOF. Suppose ě 2. Write for the node returned by the B-set prowlp´1q. By (6), there is a node P X such that dist p , q ď´1.
We first discuss the case where " . In this case, P X , implying that R´1. Notice that dist p ,´1q ą , meaning that for any a node P´1, dist p , q ą . Take a shortest path between and , and let be the node on this path that is adjacent to . By triangle inequality, dist p , q ě dist p , q´1 ě . Note that is any a node in´1, thus we have dist p ,´1q ě , meaning that R´1. On the other hand, P , implying that t , u Ď . Thus | z´1| ě 2.
We then consider the case where ‰ . In this case, we take a shortest path between and and let be the node on this path that is adjacent to . Note that may be the same as . Since dist p ,´1q ą , we have dist p , q ą´1 ě 1 for any Ṕ 1 . Hence as dist p , q ď´1, R´1. Also, dist p , q ď 2 implies that R´1. On the other hand, P , implying that t , u P . Thus | z´1| ě 2.
In either case, | z´1| ě 2. By Lem. 5.2, | | ă |´1|. Thus in a similar argument as in the proof of Thm. 5.3, there is a time 1 ą 0 where 1 " ∅ and 1 is dominating. Moreover, the dominating cost can be analyzed in the same way as in Theorem 5.3. □ We now define bdegp´1q, a -step prowling algorithm. Recall that is the maximum number of steps in each call to prowling.
Definition 5.8. The -step B-degree algorithm bdegp´1q starts from a random node 0 in AC p´1q that has an edge going out of AC p´1q, and moves to a random neighbor 1 R AC p´1q.

From
(1 ď ă ), the algorithm selects among neighbors in one that (1) has a higher degree than , and (2) the degree is as high as possible, i.e., set`1 " argmaxtdegp q | P , degp q ą degp qu. This step is repeated for at most´1 steps or until it is not possible to do so within´1 steps.
Note that the upper bounds of the dominating costs, as asserted by Theorem 5.7, imply that it is preferred to make the access neighborhood 1 , 2 , 3 , . . . grow as fast as possible. Maximizing the degrees of the selected nodes does not optimally speed up the growth of ; Instead we define N-degree of a node as the number ndeg p q of its neighbors that are not in .
Definition 5.9. The -step B-Ndegree algorithm bndep´1q starts from a random node 0 in AC p´1q that has an edge going out of AC p´1q, and moves to a random neighbor 1 R AC p´1q.

From
(1 ď ă ), among neighbors of in , do: ‚ If P AC p´1q, then set`1 as the neighbor of that has a higher N-degree and ndeg p`1q is maximized. ‚ if R AC p´1q (note that in this case, the N-degree of neighbors of is not accessible), then set`1 as the neighbor of that has a higher degree and deg p`1q is maximized. This step is repeated for at most´1 steps or until it is not possible to do so within´1 steps.
The following directly follows from Thm. 5.7 and Thm. 4.7. COROLLARY 5.10. If a unit-growth decentralized network is consistent with bdegp´1q or bndep´1q with ě 2, then in opinions converge. □

EXPERIMENTS 6.1 Setup
We perform a series of experiments to validate the performance of our prowling algorithms. These experiments serve the following purposes. The first is to test the convergence of the algorithms over real-world dynamic networks. The second is to compare the domination costs of different prowling algorithms. The third is to test the effectiveness of the algorithms in facilitating opinion convergence.
Algorithms. We run Algorithm 1 using the three proposed prowling algorithms: xdeg, bdeg, and bnde. To put them in perspective, we also test the following benchmarks: ‚ Local random algorithm (lran): This is a local algorithm that picks a random node adjacent to AC p´1q as the next access unit. It does not use prowling. ‚ Local degree algorithm (ldeg): This local algorithm resembles the one proposed in [5]. When selecting the th access unit, it picks the node P AC p´1q that has the highest N-degree. This, just like lran, also does not use prowling. ‚ Exterior random algorithm (xran): This prowling algorithm starts by moving out of AC p q and performs a random walk (of length´1) in the exterior set to choose the next access unit. In this way, the algorithm can be considered exterior-based, and thus Thm 5.3 asserts it is domination-driven. ‚ B-set random algorithm (bran): This prowling algorithm is defined in the same way as xran except that the random walk takes place in rather than . In this way, the algorithm is a B-set prowling algorithm, and by Thm. 5.7 it is domination-driven.
Real-world datasets. We utilize four real-world datasets in our experiments. Facebook-WOSN (Facebook) records a social network on Facebook with time stamps [26]. An edge t , u denotes a friendship relation between two users. Wiki-talk (Wikitalk) is a timestamped communication network of Basque Wikipedia. An edge t , u denotes that user wrote a message on the talk page of user . Citation-HepPh (Citation) is a high-energy physics citation network [21], where an edge t , u denotes a citation relationship between papers and . Enron-Email (Enron) is a timestamped email network between the employees of a company [20] where an edge t , u denotes emails between employees and . Table 1 shows key statistics of these datasets. Note that these datasets involve only incremental changes of the networks. To ensure that the network has a sufficient size as well as a sufficient number of time stamps, we begin the centralization process from different initial time stamps. Moreover, to approximate unit growth, we run the prowling algorithm (thereby selecting an access unit) for every 13,1,1,2 times stamps for Facebook, Wikitalk, Citation, and Enron, respectively.
Dynamic models. We also run four models of dynamic networks. The goal is to test the performance and robustness of our algorithms over networks with different structural properties. Dynamic  Barabasi-Albert model (BA). This produces standard scale-free networks through preferential attachment [4]. The model adds a new node at each time stamp which randomly connects with {2 nodes, where is the average degree. The network instances will exhibit a power-law degree distribution. Dynamic stochastic block model (SB) is well-used for generating a community structure [18]. We utilize this model to generate networks with three equal-size communities. At each time stamp, a new node enters a random community. It then links to nodes in the same community with a high probability , and to nodes in other communities with a low probability with " 1{6 to mimic real-world networks as shown in [18]. Dynamic Jackson-Rogers model (JR). This model, proposed by [19], simulates stochastic friendship-making among individuals in a population. The network instances meet both scale-free and small-world properties. The dynamic version of the model was introduced in [31]. There are two parameters and . As in [31], we pick " 0.5. Dynamic rich-club model (RC). The model develops a typical core/periphery structure with a dense and central core with a sparse periphery [6,9]. At each timestamp, the model adds a new node with probability P r0, 1s or an edge between two existing nodes with probability 1´, where " 2{ . The dynamic version of this model was introduced in [31]. For easier comparison, we classify networks generated by these models using two parameters: the initial size and the average degree . Table 2 summarizes key statistics of the models by setting the average degree 2 " 6 and network size " 5000. For these models, there is no upper bound on the number of time stamps that we can generate.
Experiment design. We perform three experiments. Exp. 1 compares the domination (and centralization) costs of different prowling algorithms over real-world networks. For this, we vary the radius and steps of prowling. For each dataset, we start from the specified initial time stamp with no accessing units, running prowling until the access units form a dominating set. At any time step, we assume that 1 " if no successive timestamp is provided in the dataset.
Exp. 2 compares the algorithms over networks generated by dynamic network models. Here, we evaluate the domination costs with different initial network size and average degree . Exp. 3 further validates the findings from the two experiments above by evaluating the opinion values as a result of different prowling algorithms. We test the average opinion values of nodes in during a centralization process until this value becomes higher than 0.99. An algorithm that results in faster growth in opinion values can be considered more effective at centralization.

Results and discussion
Experiment 1. When running on the real-world datasets with the settings above, all prowling algorithms produce a dominating set, and hence opinions converge in the network. Our discussions above point out a correlation between domination cost and centralization cost, namely, the p1´q-centralization cost equals to the domination cost plus (see Section 4.2). In this experiment, we compute the value of when is roughly 0. It turns out that, over the realworld networks, for all cases considered, " 0 for " 0. This validates our conjecture above that domination costs directly reflects centralization costs. Table 3 shows the domination costs for P t1, 2u and P t4, 7, 10u after 10 runs of each algorithm. We make the following observations: First, when comparing the local algorithms (lran, ldeg) with the prowling algorithms, the prowling algorithms in general achieve lower domination costs. This is especially so for " 2 which is consistent with the theoretical analysis above. For " 1, the ldeg algorithm tends to outperform lran and the exterior-based algorithms. Nevertheless, the B-set prowling algorithms in general outperform the other algorithms in all cases. This indicates that prowling could result in much smaller centralization costs than local algorithms that do not use prowling. Moreover, B-set prowling in general is more suitable than exterior-based prowling. Second, the prowling algorithms that are based on degrees (xdeg, bdeg, bnde) in general perform better than their random-walk counterparts. In particular, xdeg clearly outperforms the other exterior-based algorithm xran in all cases; bdeg, bnde clearly outperform bran (with the Wikitalk " 1, " 7 as the only exception). This is also consistent with our theoretical analysis as we stipulate that degrees can be used as an effective criterion for centralization. Third, between the two degree-based B-set prowling algorithms, we observe comparable performance when " 2. Nevertheless, bnde performs significantly better when " 1 for all datasets apart from Wikitalk. This suggests that it may be more appropriate to adopt N-degree in prowling.
A slight unexpected result is that when increases, there does not seem to be a noticeable difference on the domination cost. This may be due to the fact that the degree ascending paths in the network are in general very short, or the exterior set (and B-set) are fragmented as access units are selected, resulting in a lack of long paths. In all subsequent experiments, we thus set " 4.
Also, Wikitalk demonstrates noticeable differences as compared to the other three datasets. This can be explained by the distinct topology of this network. Indeed, Wikitalk is very sparse with a much lower average degree and clustering coefficient than others, and it holds a node with a dis-proportionally high degree (29,479). Experiment 2. We perform three tests over networks generated by the dynamic models: BA, SBM, JR, and RC. (1) Setting " 2, and " 5000, we then compare domination costs with varying average degree . (2) Finally, setting " 2, " 6, we compare domination costs with varying initial size . (3) Setting " 5000, and " 6, we first compare domination costs with varying radius . The results are shown in Fig.3. In general, we can see prowl bdeg and prowl bnde outperform other algorithms.
As expected, when we increase the average degree from 4 to 14 or increase the radius from 1 to 4, all prowling algorithms achieve smaller domination costs, and moreover they tend to have similar performance. On the contrary, as we increase the initial size of the network, the domination costs also tend to increase. All algorithms exhibit rather stable performance across the cases where in general, bnde and bdeg achieve the best performance. ldeg results in far higher domination costs than the other algorithm in many cases. The results also reflect differences between the networks with different structural properties. In particular, ldeg tends to perform well in the scale-free networks (BA), where as all algorithms apart from ldeg perform comparably well in SBM.

Experiment 3.
For further analysis, we calculate the average opinion values during the centralization processes over the realworld networks. Fig. 4 displays changes to the average opinion starting from the initial time stamp, as more access units a chosen by different prowling algorithms (fixing " 2), until the average opinion reaches above 0.8. In all datasets, the B-set prowling algorithms bdeg and bnde are the ones that lift the average opinion the fastest, and are the first ones to achieve opinion value ě 0.8. It is also remarkable that this is achieved only within a small number (ď 50) of steps. In the citation network, ldeg achieves comparable performance as the prowling algorithms, which may be explained by the high density of this dataset. In general, the degree-based prowling methods perform better than their random-walk counterparts. These findings are consistent with the two experiments above and provide further confirmation of the superior effectiveness of the degree-based B-set prowling algorithms in centralization.  problem seeks a way to impose control to a decentralized network by selecting access units. (4) prowling are adaptive methods to explore the decentralized network. From a technical standpoint, we investigate prowling algorithms that facilitate opinion convergence. Firstly, we reveal the relationship between domination and centralization and show that domination-driven prowling algorithms hold the key to opinion convergence. Then, we explore prowling algorithms in unit-growth networks that guarantee to find dominating sets. Our theoretical finding inspires us to apply degree (or N-degree)-based prowling to reduce domination costs. Lastly, experimental results on real-world and synthetic dynamic networks verify that our algorithm achieves better domination costs compared to benchmarks. The framework proposed in this paper, i.e., decentralized networks and the centralization problem, has the potential to provide a new perspective on decentralized systems that are of interest in multi-agent systems, computational social sciences, and research about the Web. Further work may include investigating new local algorithms for selecting access units, as well as exploring centralization for other applications such as influence maximization (in a similar way as [28]) or norm emergence.