Hirsch M.J., Pardalos P.M., Murphey R. Dynamics of Information Systems: Theory and Applications

Подождите немного. Документ загружается.

76 K.D. Pham

=−



(ε)



−1

(ε)



r=1

i,r

(3.80)

=−



(ε)



−1

(ε)



r=1

i,r

(3.81)

=−



(ε)



−1

(ε)



r=1

i,r

(3.82)

Replacing these results (3.79)–(3.82) into the right member of the HJB equation

(3.72) yields the value of the minimum. It is now necessary to exhibit {E

(·)}

r=1

{

(·)}

r=1

, and {T

(·)}

r=1

which render the left side of the HJB equation (3.72)

equal to zero for ε ∈[t

], when {Y

i,r

}

r=1

, {

i,r

}

r=1

, and {Z

i,r

}

r=1

are evaluated

along the solution trajectories of the dynamical equations (3.58) through (3.70). Due

to the space limitation, the closed forms for {E

(·)}

r=1

, {

(·)}

r=1

, and {T

(·)}

r=1

are however, omitted here. Furthermore, the boundary condition (3.73) requires that







r=1



i,r

) +E

)









r=1



i,r

) +

)





r=1



i,r

) +T

)









r=1







r=1

i,r

) +



r=1

i,r

)

Thus, matching the boundary condition yields the initial value conditions E

) =

) =0 and T

) =0.

Applying the 4-tuple decision strategy speciﬁed in (3.79)–(3.82) along the so-

lution trajectories of the time-backward differential equations (3.58)–(3.70), these

equations become the time-backward Riccati-type differential equations. Enforc-

ing the initial value conditions of E

) = 0,

) = 0 and T

) = 0 uniquely

implies that E

(ε) = Y

i,r

) − Y

i,r

(ε),

(ε) =

i,r

) −

i,r

(ε), and T

(ε) =

i,r

) −Z

i,r

(ε) for all ε ∈[t

] and yields a value function



ε, Y









r=1

i,r







r=1

i,r

) +



r=1

i,r

)

for which the sufﬁcient condition (3.74) of the veriﬁcation theorem is satisﬁed.

Therefore, the extremal risk-averse control laws (3.79)–(3.82) minimizing (3.71)

3 Performance-Information Analysis and Distributed Feedback Stabilization 77

become optimal

∗

(ε) =−



(ε)



−1

(ε)



r=1

i,r∗

(ε) (3.83)

∗

(ε) =−



(ε)



−1

(ε)



r=1

i,r∗

(ε) (3.84)

∗

(ε) =−



(ε)



−1

(ε)



r=1

i,r∗

(ε) (3.85)

∗

(ε) =−



(ε)



−1

(ε)



r=1

i,r∗

(ε) (3.86)

In closing the chapter, it is beneﬁcial to summarize the methodological character-

istics of the performance robustness analysis and distributed feedback stabilization

and reﬂect on them from a larger perspective, e.g., management control of a large-

scale interconnected system.

Theorem 6 (Decentralized and risk-averse control decisions) Let the pairs (A

)

and (A

) be uniformly stabilizable and the pair (A

) be uniformly detectable

on [t

]. The corresponding interconnected system controlled by agent i is then

considered with the initial condition x

∗

)

∗

(t) =



(t)x

∗

(t) +B

(t)u

∗

(t) +C

(t)z

∗

(t) +E

(t)d

(t)



dt +G

(t) dw

(t)

∗

(t) =H

(t)x

∗

(t) dt +dv

(t),

i ∈

whose local interactions with the nearest neighbors are given by

∗

(t) =



j=1,j =i

(t)x

∗

(t), i ∈N

which is then approximated by an explicit model-following of the type

(t) =



(t)z

(t) +E

(t)d

(t)



dt +G

(t) dw

(t), z

) =0.

Then, the local state estimate ˆx

∗

(t) for each agent i is generated by

d ˆx

∗

(t) =



(t)x

∗

(t) +B

(t)u

∗

(t) +C

(t)z

∗

(t) +E

(t)d

(t)



(t)



∗

(t) −H

(t) ˆx

∗

(t) dt



, ˆx

∗

) =x

78 K.D. Pham

and the Kalman-type gain is given by

(t) =Σ

(t)H

(t)V

−1

The covariance for estimation error, Σ

(t) is the solution of the time-forward matrix

differential equation

(t) = A

(t)Σ

(t) +Σ

(t)A

(t) +G

(t)W

(t)

−Σ

(t)H

(t)V

−1

(t)Σ

(t), Σ

) =0

Further, let k

∈Z

and the sequence μ

={μ

≥0}

r=1

with μ

> 0. The optimal

decentralized and risk-averse control decision for agent i is given by

∗

(t) =K

∗

(t) ˆx

∗

(t) +p

∗

(t); z

∗

(t) =K

∗

(t) ˆx

∗

(t) +p

∗

(t)

provided that

∗

(s) =−R

−1

(s)B

(s)



r=1

ˆμ

i,r∗

(s) (3.87)

∗

(s) =−R

−1

(s)C

(s)



r=1

ˆμ

i,r∗

(s) (3.88)

∗

(s) =−R

−1

(s)B

(s)



r=1

ˆμ

i,r∗

(s) (3.89)

∗

(s) =−R

−1

(s)C

(s)



r=1

ˆμ

i,r∗

(s) (3.90)

where normalized weighting preferences ˆμ

 μ

/μ

’s are chosen by agent i

toward strategic design of its performance robustness. The supporting solutions

i,r∗

(s)}

r=1

, {

i,r∗

(s)}

r=1

, {Z

i,r∗

(s)}

r=1

optimally satisfy the time-backward

matrix-valued and vector-valued differential equations

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s);K

∗

(s), K

∗

(s)



i∗

) (3.91)

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s);K

∗

(s), K

∗

(s)



i∗

)

(3.92)

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s);K

∗

(s), K

∗

(s)



i∗

) (3.93)

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s);K

∗

(s), K

∗

(s)



i∗

) (3.94)

3 Performance-Information Analysis and Distributed Feedback Stabilization 79

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s), Y

i∗

(s)



i∗

) (3.95)

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s)



i∗

) (3.96)

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s);K

∗

(s), K

∗

(s)



i∗

) (3.97)

i∗

(s) =F

i∗



s,Y

(s), Y

(s)



i∗

) (3.98)

i∗

(s) =F

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s)



i∗

) (3.99)

i∗

(s) =

i∗



s,Y

i∗

(s), Y

i∗

(s),

i∗

(s);K

∗

(s), K

∗

(s);...p

∗

(s), p

∗

(s)



i∗

) (3.100)

i∗

(s) =

i∗



s,Y

i∗

(s), Y

i∗

(s),

i∗

(s),

i∗

(s);p

∗

(s), p

∗

(s)



i∗

) (3.101)

i∗

(s) =

i∗



s,Y

i∗

(s),

i∗

(s);p

∗

(s), p

∗

(s)



i∗

) (3.102)

i∗

(s) =G

i∗



s,Y

i∗

(s), Y

i∗

(s), Y

i∗

(s), Y

i∗

(s), Y

i∗

(s), Y

i∗

(s), Y

i∗

(s),

i∗

(s), Y

i∗

(s),

i∗

(s),

i∗

(s);p

∗

(s), p

∗

(s)



i∗

) (3.103)

where the terminal-value conditions are deﬁned by

i∗

)  Q

×0 ×···×0 Y

i∗

)  Q

×0 ×···×0

i∗

)  0 ×0 ×···×0 Y

i∗

)  Q

×0 ×···×0

i∗

)  Q

×0 ×···×0 Y

i∗

)  0 ×0 ×···×0

i∗

)  0 ×0 ×···×0 Y

i∗

)  0 ×0 ×···×0

i∗

)  0 ×0 ×···×0

i∗

)  0 ×0 ×···×0

i∗

)  0 ×0 ×···×0

i∗

)  0 ×0 ×···×0

i∗

)  0 ×0 ×···×0

As pictorial illustrations, Fig. 3.8 shows how local interaction predictions be-

tween agent i and its neighbor agents as well as local perceptions of performance

risk associated with the Chi-squared performance random variable are integrated

80 K.D. Pham

Fig. 3.8 Local control and

interaction coordination for

interconnected autonomous

systems

Fig. 3.9 Multi-level control

and coordination for

large-scale interconnected

systems

to yield a class of distributed feedback decision strategies. Such decentralized and

risk-averse decision laws shown in Fig. 3.8, are therefore robust and adaptable to

uncertain environments without reliance on intensive communication exchanges.

Consequently, these interconnected systems controlled by autonomous agent i for

i = 1,...N take active roles to mitigate performance variations caused by the un-

derlying stochastic disturbances via means of mixed random realizations and thus

the large-scale interconnected system is capable of shaping the performance distri-

bution and robustness whose multi-level control and coordination among intercon-

nected autonomous systems is illustrated in Fig. 3.9.

3.6 Conclusions

The chapter presents a new innovative solution concept to analytically address per-

formance robustness which is widely recognized as a pressing need in stochas-

tic control of large-scale interconnected systems. In the most basic framework of

performance-information analysis, a local performance-information system trans-

mits messages about higher-order characteristics of performance uncertainty to the

local decision maker for his use in future adaptive risk-averse decisions. The mes-

sages of performance-measure statistics transmitted are then inﬂuenced by the at-

tributes of decentralized decision settings and local decision makers. The risk of

a performance measure expressed as a linear combination of higher-order aspects

(beyond statistical averaging) of performance distribution in distributed control, not

only works as feedback information for future risk-averse decisions via local infor-

mation about the states of nature but also serves as an inﬂuence mechanism for the

3 Performance-Information Analysis and Distributed Feedback Stabilization 81

local decision maker’s current control behavior. This work contributes toward the

construction of a theory of performance robustness for stochastic control of a class

of large-scale systems in terms of both substantial results and research methodology.

References

1. Brockett, R.W.: Finite Dimensional Linear Systems. Wiley, New York (1970)

2. Dieudonne, J.: Foundations of Modern Analysis. Academic Press, New York (1960)

3. Field, R.V., Bergman, L.A.: Reliability based approach to linear covariance control design.

J. Eng. Mech. 124, 193–199 (1998)

4. Fleming, W.H., Rishel, R.W.: Deterministic and Stochastic Optimal Control. Springer, New

York (1975)

5. Hansen, L.P., Sargent, T.J., Tallarini, T.D. Jr.: Robust permanent income and pricing. Rev.

Econ. Stud. 66, 873–907 (1999)

6. Liberty, S.R.: Performance analysis of stochastic linear control systems: a new viewpoint. In:

Proceedings International Forum on Alternatives for Linear Multivariable Control, pp. 79–86

(1977)

7. Pham, K.D.: Statistical control paradigms for structural vibration suppression. In: PhD Disser-

tation (2004). Available via http://etd.nd.edu/ETD-db/theses/available/etd-04152004-121926/

unrestricted/PhamKD052004.pdf. Cited 13 August 2009

8. Pham, K.D.: Cooperative solutions in multi-person quadratic decision problems: performance-

measure statistics and cost-cumulant control paradigm. In: The 46th Conference on Decisions

and Control, pp. 2484–2490 (2007)

9. Pham, K.D.: Non-cooperative outcomes for stochastic Nash games: decision strategies to-

wards multi-attribute performance robustness. In: The 17th World Congress International Fed-

eration on Automatic Control, pp. 11750–11756 (2008)

10. Pham, K.D.: New results in stochastic cooperative games: strategic coordination for multi-

resolution performance robustness. In: Hirsch, M.J., Pardalos, P.M., Murphey, R., Grundel, D.

(eds.) Optimization and Cooperative Control Strategies. Lecture Notes in Control and Infor-

mation Sciences, vol. 381, pp. 257–285. Springer, Berlin (2008)

11. Sain, M.K.: Control of linear systems according to the minimal variance criterion-a new ap-

proach to the disturbance problem. IEEE Trans. Autom. Control 11, 118–122 (1966)

12. Whittle, P.: Risk Sensitive Optimal Control. Wiley, New York (1990)

Chapter 4

A General Approach for Modules Identiﬁcation

in Evolving Networks

Thang N. Dinh, Incheol Shin, Nhi K. Thai,

My T. Thai, and Taieb Znati

Summary Most complex networks exhibit a network modular property that is

nodes within a network module are more densely connected among each other

than with the rest of the network. Identifying network modules can help deeply

understand the structures and functions of a network as well as design a ro-

bust system with minimum costs. Although there are several algorithms identi-

fying the modules in literature, none can adaptively update modules in evolv-

ing networks without recomputing the modules from scratch. In this chapter,

we introduce a general approach to efﬁciently detect and trace the evolution

of modules in an evolving network. Our solution can identify the modules of

each network snapshot based on the modules of previous snapshots, thus dy-

namically updating these modules. Moreover, we also provide a network com-

pact representation which signiﬁcantly reduces the size of the network, thereby

minimizing the running time of any existing algorithm on the modules identiﬁca-

tion.

The work of My T. Thai is supported by DTRA, Young Investigator Award, grant number

HDTRA1-09-1-0061.

T.N. Dinh (



) · I. Shin · M.T. Thai

University of Florida, Gainesville, FL 32611, USA

e-mail: tdinh@cise.uﬂ.edu

I. Shin

e-mail: ishin@cise.uﬂ.edu

M.T. Thai

e-mail: mythai@cise.uﬂ.edu

N.K. Thai

University of Minnesota, Minneapolis, MN 55455, USA

e-mail: thai0028@umn.edu

T. Znati

University of Pittsburgh, Pittsburgh, PA 15215, USA

e-mail: znati@cs.pitt.edu

M.J. Hirsch et al. (eds.), Dynamics of Information Systems,

Springer Optimization and Its Applications 40, DOI 10.1007/978-1-4419-5689-7_4,

84 T.N. Dinh et al.

4.1 Introduction

Network modules, also known as community structures in social networks, are

usually deﬁned as groups of nodes densely connected inside and sparser between

groups. Modules in networks usually correspond to groups of nodes with the same

function in networks. In the case of World Wide Web, for example, modules are

groups of pages with a same topic. In biological networks, modules may be groups

of proteins, genes with same functions. Studying network modules becomes very

active and crucial in different scientiﬁc communities with an emerging of very large

and complex networks such as phone call networks in sociology, metabolic, protein-

protein-interaction, and gene-regulatory networks in biology, citation networks and

the power grid networks in physics, and communication networks and World Wide

Web in the technology ﬁeld. Studying network modules is well-motivated as it is an

essential tool to study and understand the complexity of many natural and artiﬁcial

systems. It reveals the relationship between nodes in a same module as well as the

relationship between modules in networks. It also helps understand the interplay be-

tween network topology and functionality. Knowing the behavior of modules with

respect to the movements of nodes and links in evolving networks can directly help

predict the interdependent responses of network components and help to improve

the robustness of networks. Knowing the evolutionary of the structure provides the

basics construction/design topology we need to achieve so that it will be less sensi-

tive to the changes of structures.

Although the study of identifying network modules has been investigated exten-

sively [1–14], including the dynamics and evolution of a network in the analysis of

inherent modules is a new task that has not yet been well investigated. The study

of such evolution requires computing modules of the network at different time in-

stances. In previous approaches, [15–17] network modules are ﬁrst identiﬁed sepa-

rately at each time point and then modular structures at two consecutive time points

are compared to each other in order to highlight evolution changes. However, iden-

tifying network modules in each state of the network from scratch may result in

prohibitive computational costs, particularly in the case of highly dynamic and ex-

tremely large networks, such as the online social networks MySpace and Facebook

with more than hundred millions of nodes. In addition, it may be infeasible in the

case of limited topological data. Moreover, identifying network modules of each

snapshot independently may lead to substantial and unexpected variation, thus in-

troducing incorrect evolution phenomena.

To overcome the above limitations, we propose a graph-based approach using

modular structure found in previous steps as a guide to incrementally identify mod-

ules in the next step. Adaptively updating modules in evolving networks not only

avoids recomputing them from scratch for each time point but also produces consis-

tent modular structures over time. For further reducing the running time and com-

putational cost, we provide a compact network representation with much smaller

size such that the modular structure of compact networks is as same as that of the

original networks. The modular information is embedded in this compact represen-

tation to allow detection of modules at next time point and modules’ evolving at the

4 A General Approach for Modules Identiﬁcation in Evolving Networks 85

same time. Several experiments with real data sets show that our approach performs

extremely well, especially in term of the running time. In some cases, it can be 1000

times faster than that of computing the modules on each network snapshot.

The rest of the chapter is organized as follows. Section 4.2 presents the prelimi-

naries and the problem deﬁnition. In Sect. 4.3, we discuss the construction of com-

pact network representation together with detailed analytical results. Section 4.4

analyzes how network structure affected when elemental changes such as adding,

removing new nodes, links happen and presents an adaptively updating algorithm.

Section 4.5 shows the experimental evaluation. Finally, the Conclusion and future

work are discussed in Sect. 4.6.

4.2 Preliminaries and Problem Deﬁnition

4.2.1 Preliminaries

We study weighted undirected graph G = (V , E) i.e., each link (u, v) ∈ E is asso-

ciated with a nonnegative number w(u,v). The weights on links take greater values

for node pairs that are closely related or similar in some way [18].

The weighted degree of a node v is deﬁned as:

d(v)=



w(u,v)

The volume of a subset S ⊆V of nodes is deﬁned as:

vol(S) =



v∈S

d(v)

We recall that vol(V ) =2m where m is the total weights of links in G. We denote

the total weight of links crossing two sets of nodes X, Y ∈V by

Φ(X,Y) =



u∈X,v∈Y

w(u,v)

We note that vol(S) = Φ(S,V ). For simplicity, we also write Φ(X) instead of

Φ(X,X).

Recall that a modular structure, sometimes referred as partition, C ={C

...,C

} is a division of network into disjoint sets of nodes C

. To quantify the

strength of a partition, the most widely accepted quantitative measurement [19]is

called modularity Q which is deﬁned as follows:

Q(C ) =



i=1



Φ(C

)

−



vol(C

)





(4.1)

If a node u belongs to the module C

, we say it has the membership in C

and

deﬁne the membership function mb(u) =i.