text: 14 [3] J. Maldacena, Adv. Theor. Math. Phys. 2, 231 (1998) [Int. J. Theor. Phys. 38, 1113 (1999)]. [4] E. Witten, Adv. Theor. Math. Phys. 2, 253 (1998). [5] S.S. Gubser, I.R. Klebanov, and A.M. Polyakov, Phys. Lett. B 428, 105 (1998). [6] S.A. Hartnoll, Class. Quant. Grav. 26, 224002 (2009). [7] C.P. Herzog, J. Phys. A 42, 343001 (2009). [8] G.T. Horowitz, Lect. Notes Phys. 828 313, (2011); arXiv:1002.1722 [hep-th]. [9] R.G. Cai, L. Li, L.F. Li, and R.Q. Yang, Sci. China Phys. Mech. Astron. 58, 060401 (2015); arXiv:1502.00437 [hep-th]. [10] S.S. Gubser, Phys. Rev. D 78, 065034 (2008). [11] S.A. Hartnoll, C.P. Herzog, and G.T. Horowitz, Phys. Rev. Lett. 101, 031601 (2008). [12] T. Nishioka, S. Ryu, and T. Takayanagi, J. High Energy Phys. 03, 131 (2010). [13] P. Basu, A. Mukherjee, and H.H. Shieh, Phys. Rev. D 79, 045010 (2009). [14] C.P. Herzog, P.K. Kovtun, and D.T. Son, Phys. Rev. D 79, 066002 (2009). [15] J. Sonner and B. Withers, Phys. Rev. D 82, 026001 (2010). [16] D. Arean, M. Bertolini, J. Evslin, and T. Prochazka, J. High Energy Phys. 07, 060 (2010). [17] H.B. Zeng, W.M. Sun, and H.S. Zong, Phys. Rev. D 83, 046010 (2011). [18] H.B. Zeng, Phys. Rev. D 87, 046009 (2013). [19] D. Arean, P. Basu, and C. Krishnan, J. High Energy Phys. 10, 006 (2010). [20] Y.B. Wu, J.W. Lu, W.X. Zhang, C.Y. Zhang, J.B. Lu, and F. Yu, Phys. Rev. D 90, 126006 (2014); arXiv:1410.5243 [hep-th]. [21] Y.B. Wu, J.W. Lu, C.Y. Zhang, N. Zhang, X. Zhang, Z.Q. Yang, and S.Y. Wu, Phys. Lett. B 741, 138 (2015); arXiv:1412.3689 [hep-th]. [22] I. Amado, D. Arean, A. Jimenez-Alba, K. Landsteiner, L. Melgar, and I.S. Landea, J. High Energy Phys. 07, 108 (2013). [23] I. Amado, D. Arean, A. Jimenez-Alba, K. Landsteiner, L. Melgar, and I.S. Landea, J. High Energy Phys. 02, 063 (2014). [24] Yan Peng, X.M. Kuang, Y.Q. Liu, and B. Wang, arXiv:1204.2853 [hep-th]. [25] X.M. Kuang, Y.Q. Liu, and B. Wang, Phys. Rev. D 86, 046008 (2012). [26] G. Siopsis and J. Therrien, J. High Energy Phys. 05, 013 (2010). [27] G. Siopsis, J. Therrien, and S. Musiri, Class. Quant. Grav. 29, 085007 (2012). [28] R.G. Cai, H.F. Li, and H.Q. Zhang, Phys. Rev. D 83, 126007 (2011); arXiv:1103.5568 [hep-th]. [29] R.G. Cai, S. He, L. Li, and L.F. Li, J. High Energy Phys. 12, 036 (2013); arXiv:1309.2098 [hep-th]. [30] R.G. Cai, L. Li, and L.F. Li, J. High Energy Phys. 01, 032 (2014); arXiv:1309.4877 [hep-th]. [31] L.F. Li, R.G. Cai, L. Li, and C. Shen, Nucl. Phys. B 894, 15 (2015); arXiv:1310.6239 [hep-th]. [32] R.G. Cai, L. Li, L.F. Li, and Y. Wu, J. High Energy Phys. 01, 045 (2014); arXiv:1311.7578 [hep-th]. [33] Y.B. Wu, J.W. Lu, M.L. Liu, J.B. Lu, C.Y. Zhang, and Z.Q. Yang, Phys. Rev. D 89, 106006 (2014); arXiv:1403.5649 [hep-th]. [34] R.G. Cai, L. Li, L.F. Li, and R.Q. Yang, J. High Energy Phys. 04, 016 (2014); arXiv:1401.3974 [gr-qc]. [35] Y.B. Wu, J.W. Lu, Y.Y. Jin, J.B. Lu, X. Zhang, S.Y. Wu, and C. Wang, Int. J. Mod. Phys. A 29, 1450094 (2014); arXiv:1405.2499 [hep-th]. [36] R.G. Cai and R.Q. Yang, Phys. Rev. D 91, 026001 (2015); arXiv:1410.5080 [hep-th]. [37] L. Zhang, Q.Y. Pan, and J.L. Jing, Phys. Lett. B 743, 104 (2015). [38] P. Chaturvedi and G. Sengupta, J. High Energy Phys. 04, 001 (2015). [39] Z.Y. Nie, R.G. Cai, X. Gao, L. Li, and H. Zeng, Eur. Phys. J. C 75, 559 (2015); arXiv:1501.00004 [hep-th]. [40] M. Rogatko and K.I. Wysokinski, arXiv:1508.02869 [hep-th]. [41] S.A. Hartnoll, C.P. Herzog, and G.T. Horowitz, J. High Energy Phys. 12, 015 (2008). [42] G.T. Horowitz and B. Way, J. High Energy Phys. 11, 011 (2010). [43] Q.Y. Pan, B. Wang, E. Papantonopoulos, J. Oliveria, and A.B. Pavan, Phys. Rev. D 81, 106007 (2010). [44] S.S. Gubser, C.P. Herzog, S.S. Pufu, and T. Tesileanu, Phys. Rev. Lett. 103, 141601 (2009). [45] I.M. Gelfand and S.V. Fomin, Calculus of Variations, Revised English Edition, Translated and Edited by R.A. Silverman, Prentice-Hall, Inc. Englewood Cliﬀ, New Jersey (1963).

label: reference

text: J.

text: Maldacena,

text: Adv.

text: Theor.

text: Math.

text: Phys.

text: [Int.

text: J.

text: Theor.

text: Phys.

text: E.

text: Witten,

text: Adv.

text: Theor.

text: Math.

text: Phys.

text: S.S.

text: Gubser,

text: I.R.

text: Klebanov,

text: and

text: A.M.

text: Polyakov,

text: Phys.

text: Lett.

text: B

text: S.A.

text: Hartnoll,

text: Class.

text: Quant.

text: Grav.

text: C.P.

text: Herzog,

text: J.

text: Phys.

text: A

text: G.T.

text: Horowitz,

text: Lect.

text: Notes

text: Phys.

text: [hep-th].

text: R.G.

text: Cai,

text: L.

text: Li,

text: L.F.

text: Li,

text: and

text: R.Q.

text: Yang,

text: Sci.

text: China

text: Phys.

text: Mech.

text: Astron.

text: [hep-th].

text: S.S.

text: Gubser,

text: Phys.

text: Rev.

text: D

text: S.A.

text: Hartnoll,

text: C.P.

text: Herzog,

text: and

text: G.T.

text: Horowitz,

text: Phys.

text: Rev.

text: Lett.

text: T.

text: Nishioka,

text: S.

text: Ryu,

text: and

text: T.

text: Takayanagi,

text: J.

text: High

text: Energy

text: Phys.

text: P.

text: Basu,

text: A.

text: Mukherjee,

text: and

text: H.H.

text: Shieh,

text: Phys.

text: Rev.

text: D

text: C.P.

text: Herzog,

text: P.K.

text: Kovtun,

text: and

text: D.T.

text: Son,

text: Phys.

text: Rev.

text: D

text: J.

text: Sonner

text: and

text: B.

text: Withers,

text: Phys.

text: Rev.

text: D

text: D.

text: Arean,

text: M.

text: Bertolini,

text: J.

text: Evslin,

text: and

text: T.

text: Prochazka,

text: J.

text: High

text: Energy

text: Phys.

text: H.B.

text: Zeng,

text: W.M.

text: Sun,

text: and

text: H.S.

text: Zong,

text: Phys.

text: Rev.

text: D

text: H.B.

text: Zeng,

text: Phys.

text: Rev.

text: D

text: D.

text: Arean,

text: P.

text: Basu,

text: and

text: C.

text: Krishnan,

text: J.

text: High

text: Energy

text: Phys.

text: Y.B.

text: Wu,

text: J.W.

text: Lu,

text: W.X.

text: Zhang,

text: C.Y.

text: Zhang,

text: J.B.

text: Lu,

text: and

text: F.

text: Yu,

text: Phys.

text: Rev.

text: D

text: [hep-th].

text: Y.B.

text: Wu,

text: J.W.

text: Lu,

text: C.Y.

text: Zhang,

text: N.

text: Zhang,

text: X.

text: Zhang,

text: Z.Q.

text: Yang,

text: and

text: S.Y.

text: Wu,

text: Phys.

text: Lett.

text: B

text: [hep-th].

text: I.

text: Amado,

text: D.

text: Arean,

text: A.

text: Jimenez-Alba,

text: K.

text: Landsteiner,

text: L.

text: Melgar,

text: and

text: I.S.

text: Landea,

text: J.

text: High

text: Energy

text: Phys.

text: I.

text: Amado,

text: D.

text: Arean,

text: A.

text: Jimenez-Alba,

text: K.

text: Landsteiner,

text: L.

text: Melgar,

text: and

text: I.S.

text: Landea,

text: J.

text: High

text: Energy

text: Phys.

text: Yan

text: Peng,

text: X.M.

text: Kuang,

text: Y.Q.

text: Liu,

text: and

text: B.

text: Wang,

text: [hep-th].

text: X.M.

text: Kuang,

text: Y.Q.

text: Liu,

text: and

text: B.

text: Wang,

text: Phys.

text: Rev.

text: D

text: G.

text: Siopsis

text: and

text: J.

text: Therrien,

text: J.

text: High

text: Energy

text: Phys.

text: G.

text: Siopsis,

text: J.

text: Therrien,

text: and

text: S.

text: Musiri,

text: Class.

text: Quant.

text: Grav.

text: R.G.

text: Cai,

text: H.F.

text: Li,

text: and

text: H.Q.

text: Zhang,

text: Phys.

text: Rev.

text: D

text: [hep-th].

text: R.G.

text: Cai,

text: S.

text: He,

text: L.

text: Li,

text: and

text: L.F.

text: Li,

text: J.

text: High

text: Energy

text: Phys.

text: [hep-th].

text: R.G.

text: Cai,

text: L.

text: Li,

text: and

text: L.F.

text: Li,

text: J.

text: High

text: Energy

text: Phys.

text: [hep-th].

text: L.F.

text: Li,

text: R.G.

text: Cai,

text: L.

text: Li,

text: and

text: C.

text: Shen,

text: Nucl.

text: Phys.

text: B

text: [hep-th].

text: R.G.

text: Cai,

text: L.

text: Li,

text: L.F.

text: Li,

text: and

text: Y.

text: Wu,

text: J.

text: High

text: Energy

text: Phys.

text: [hep-th].

text: Y.B.

text: Wu,

text: J.W.

text: Lu,

text: M.L.

text: Liu,

text: J.B.

text: Lu,

text: C.Y.

text: Zhang,

text: and

text: Z.Q.

text: Yang,

text: Phys.

text: Rev.

text: D

text: [hep-th].

text: R.G.

text: Cai,

text: L.

text: Li,

text: L.F.

text: Li,

text: and

text: R.Q.

text: Yang,

text: J.

text: High

text: Energy

text: Phys.

text: [gr-qc].

text: Y.B.

text: Wu,

text: J.W.

text: Lu,

text: Y.Y.

text: Jin,

text: J.B.

text: Lu,

text: X.

text: Zhang,

text: S.Y.

text: Wu,

text: and

text: C.

text: Wang,

text: Int.

text: J.

text: Mod.

text: Phys.

text: A

text: [hep-th].

text: R.G.

text: Cai

text: and

text: R.Q.

text: Yang,

text: Phys.

text: Rev.

text: D

text: [hep-th].

text: L.

text: Zhang,

text: Q.Y.

text: Pan,

text: and

text: J.L.

text: Jing,

text: Phys.

text: Lett.

text: B

text: P.

text: Chaturvedi

text: and

text: G.

text: Sengupta,

text: J.

text: High

text: Energy

text: Phys.

text: Z.Y.

text: Nie,

text: R.G.

text: Cai,

text: X.

text: Gao,

text: L.

text: Li,

text: and

text: H.

text: Zeng,

text: Eur.

text: Phys.

text: J.

text: C

text: [hep-th].

text: M.

text: Rogatko

text: and

text: K.I.

text: Wysokinski,

text: [hep-th].

text: S.A.

text: Hartnoll,

text: C.P.

text: Herzog,

text: and

text: G.T.

text: Horowitz,

text: J.

text: High

text: Energy

text: Phys.

text: G.T.

text: Horowitz

text: and

text: B.

text: Way,

text: J.

text: High

text: Energy

text: Phys.

text: Q.Y.

text: Pan,

text: B.

text: Wang,

text: E.

text: Papantonopoulos,

text: J.

text: Oliveria,

text: and

text: A.B.

text: Pavan,

text: Phys.

text: Rev.

text: D

text: S.S.

text: Gubser,

text: C.P.

text: Herzog,

text: S.S.

text: Pufu,

text: and

text: T.

text: Tesileanu,

text: Phys.

text: Rev.

text: Lett.

text: I.M.

text: Gelfand

text: and

text: S.V.

text: Fomin,

text: Calculus

text: of

text: Variations,

text: Revised

text: English

text: Edition,

text: Translated

text: and

text: Edited

text: by

text: R.A.

text: Silverman,

text: Prentice-Hall,

text: Inc.

text: Englewood

text: Cliﬀ,

text: New

text: Jersey


text: 10 and the transformation of the relevant quantities → → → (µ, S ) λ(µ, S ) , (ρ, J ) λ3(ρ, J ) , ρ λ1+∆ρ , (40) ϕ ϕ ϕ ϕ x+ x+ which can be used to set q = 1 and r = 1 when performing numerical calculations and check the analytical s expressions in this section. For convenience in the following discussion, we will change the coordinate z = r /r and convert Eq. (36) s to be (cid:18) (cid:19) (cid:34) (cid:18) (cid:19) (cid:18) (cid:19) (cid:35) (cid:48) (cid:48)(cid:48) 1 f (cid:48) 1 qA 2 − 1 qA 2 − m2 ρ + + ρ + t ϕ ρ = 0, (41) x z f x z2f r z4f2 r z4f x s s (cid:18) (cid:19) (cid:18) (cid:19) (cid:48) (cid:48)(cid:48) 1 f (cid:48) − 2 qρ 2 A + + A x A = 0, (42) t z f t z2f r t s (cid:18) (cid:19) (cid:48)(cid:48) − 1 (cid:48) − 2 qρ 2 A A x A = 0. (43) ϕ z ϕ z2f r ϕ s Here and hereafter in this section the prime denotes the derivative with respect to z. A. Critical chemical potential ≤ Similar to the analysis for the holographic s-wave model of superﬂuidity, if µ µ , the vector ﬁeld ρ is nearly (cid:39) c x − zero, i.e., ρ 0. Thus, we can obtain the physical solutions A (z) = µ to Eq. (42) and A = S (1 z2) x t ϕ ϕ to Eq. (43) when µ < µ , which are the same forms just as in the holographic s-wave superﬂuid model. c This analytical result is consistent with the numerical ﬁndings in Fig. 3 which plots the condensate of the (cid:104) (cid:105) operator O = ρ and charge density ρ with respect to the chemical potential µ for diﬀerent values of the x x+ dimensionless parameter k = S /µ. ϕ 4 1.2 Sj(cid:144)Μ=0.00 Sj(cid:144)Μ=0.00 Sj(cid:144)Μ=0.25 1.0 Sj(cid:144)Μ=0.25 3 Sj(cid:144)Μ=0.50 Sj(cid:144)Μ=0.50 Sj(cid:144)Μ=0.75 0.8 Sj(cid:144)Μ=0.75 Sj(cid:144)Μ=1.00 Sj(cid:144)Μ=1.00 <Ox> 2 Ρ 0.6 0.4 1 0.2 0 0.0 2.8 3.0 3.2 3.4 3.6 3.8 2.0 2.5 3.0 3.5 4.0 Μ Μ (cid:104) (cid:105) FIG. 3: (Color online) The condensate of the operator O and charge density ρ with respect to the chemical potential x µ for diﬀerent values of k = S /µ in the holographic p-wave model of superﬂuidity by using the numerical shooting ϕ method. In each panel, the ﬁve lines from left to right correspond to increasing S /µ, i.e., S /µ = 0.00 (orange), 0.25 ϕ ϕ (blue), 0.50 (red), 0.75 (green) and 1.00 (black) respectively. We choose m2 = 5/4 and scale q = 1 and r = 1 in the s numerical computation. → As µ µ , the vecto(cid:18)r ﬁeld eq(cid:19)uation(cid:34)(41) (cid:18)will b(cid:19)ecome (cid:18) (cid:19) (cid:35) c (cid:48) − (cid:48)(cid:48) 1 f (cid:48) 1 qµ 2 − (1 z2)2 qS 2 − m2 ρ + + ρ + ϕ ρ = 0. (44) x z f x z2f r z4f2 r z4f x s s ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: and

text: the

text: transformation

text: of

text: the

text: relevant

text: quantities

label: equation

text: (µ,

text: S

text: λ(µ,

text: S

text: (ρ,

text: J

text: J

text: ρ

text: λ1+∆ρ

text: ϕ

text: ϕ

text: ϕ

text: ϕ

text: x+

text: x+

text: which

text: can

text: be

text: used

text: to

text: set

text: q

text: and

text: r

text: when

text: performing

text: numerical

text: calculations

text: and

text: check

text: the

text: analytical

text: s

text: expressions

text: in

text: this

text: section.

text: For

text: convenience

text: in

text: the

text: following

text: discussion,

text: we

text: will

text: change

text: the

text: coordinate

text: z

text: r

text: /r

text: and

text: convert

text: Eq.

text: s

text: to

text: be

text: f

text: qA

text: qA

text: ρ

text: ρ

text: t

text: ϕ

text: ρ

text: x

text: z

text: f

text: x

text: r

text: r

text: x

text: s

text: s

text: f

text: qρ

text: A

text: A

text: x

text: A

text: t

text: z

text: f

text: t

text: r

text: t

text: s

text: qρ

text: A

text: A

text: x

text: A

text: ϕ

text: z

text: ϕ

text: r

text: ϕ

text: s

text: Here

text: and

text: hereafter

text: in

text: this

text: section

text: the

text: prime

text: denotes

text: the

text: derivative

text: with

text: respect

text: to

text: z.

text: A.

text: Critical

text: chemical

text: potential

text: Similar

text: to

text: the

text: analysis

text: for

text: the

text: holographic

text: s-wave

text: model

text: of

text: superﬂuidity,

text: if

text: µ

text: µ

text: the

text: vector

text: ﬁeld

text: ρ

text: is

text: nearly

text: c

text: x

text: zero,

text: i.e.,

text: ρ

text: Thus,

text: we

text: can

text: obtain

text: the

text: physical

text: solutions

text: A

text: (z)

text: µ

text: to

text: Eq.

text: and

text: A

text: S

text: x

text: t

text: ϕ

text: ϕ

text: to

text: Eq.

text: when

text: µ

text: µ

text: which

text: are

text: the

text: same

text: forms

text: just

text: as

text: in

text: the

text: holographic

text: s-wave

text: superﬂuid

text: model.

text: c

text: This

text: analytical

text: result

text: is

text: consistent

text: with

text: the

text: numerical

text: ﬁndings

text: in

text: Fig.

text: which

text: plots

text: the

text: condensate

text: of

text: the

text: operator

text: O

text: ρ

text: and

text: charge

text: density

text: ρ

text: with

text: respect

text: to

text: the

text: chemical

text: potential

text: µ

text: for

text: diﬀerent

text: values

text: of

text: the

text: x

text: x+

text: dimensionless

text: parameter

text: k

text: S

text: /µ.

text: ϕ

text: <Ox>

text: Ρ

text: Μ

text: Μ

text: FIG.

text: (Color

text: online)

text: The

text: condensate

text: of

text: the

text: operator

text: O

text: and

text: charge

text: density

text: ρ

text: with

text: respect

text: to

text: the

text: chemical

text: potential

text: x

text: µ

text: for

text: diﬀerent

text: values

text: of

text: k

text: S

text: /µ

text: in

text: the

text: holographic

text: p-wave

text: model

text: of

text: superﬂuidity

text: by

text: using

text: the

text: numerical

text: shooting

text: ϕ

text: method.

text: In

text: each

text: panel,

text: the

text: ﬁve

text: lines

text: from

text: left

text: to

text: right

text: correspond

text: to

text: increasing

text: S

text: /µ,

text: i.e.,

text: S

text: /µ

text: (orange),

text: ϕ

text: ϕ

text: (blue),

text: (red),

text: (green)

text: and

text: (black)

text: respectively.

text: We

text: choose

text: and

text: scale

text: q

text: and

text: r

text: in

text: the

text: s

text: numerical

text: computation.

text: As

text: µ

text: µ

text: the

text: ﬁeld

text: c

text: f

text: qµ

text: qS

text: ρ

text: ρ

text: ϕ

text: ρ

text: x

text: z

text: f

text: x

text: r

text: r

text: x

text: s

text: s

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: n degree closeness betweenness random-walk { } { } { } { } 1 11 11 11 11 { } { } { } { } { } 2 4, 11 2, 13 , 4, 11 4, 11 4, 11 { } { { } { { } { } 3 4, 11,}13 , 0, 11, 0, 11,}13 , 4, 11, 4, 11, 13 0, 11, 13 13 , ... (9) 13 , ... (4) { } { } { } { } 4 2, 4, 11, 13 , ... (23) 2, 4, 11, 13 , ... (5)] 2, 4, 11, 13 2, 4, 11, 13 Table 11: Solutions for group centrality on Proximity Semantic Network 1. Fig. 4: Proximity Semantic Network 2. Proximity Semantic Network 2 Labels: – 0.- animal – 5.- chicken – 1.- antlers – 6.- color – 2.- bat – 7.- cottonwood – 3.- bird – 8.- daisy – 4.- blood – 9.- deer ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: Proximity

text: Semantic

text: Network

text: Fig.

text: Proximity

text: Semantic

text: Network

text: Proximity

text: Semantic

text: Network

text: Labels:

text: animal

text: chicken

text: antlers

text: color

text: bat

text: cottonwood

text: bird

text: daisy

text: blood

text: deer

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: – 10.- dog – 18.- livingthing – 11.- feathers – 19.- mammal – 12.- ﬂower – 20.- plant – 13.- frog – 21.- red – 14.- green – 22.- robin – 15.- hair – 16.- hooves – 23.- rose – 17.- leaves – 24.- tree n degree closeness betweenness random-walk { } { } { } { } 1 11 11 11 11 { } { } { } { } 2 0, 11 2, 11 , ... (2) 2, 11 2, 11 { } { } { } { } 3 2, 13, 21 , ... (8) 2, 13, 21 2, 11, 13 2, 13, 21 { } { } { } { } 4 2, 4, 13, 21 , ... (16) 2, 4, 13, 21 2, 11, 13, 21 2, 4, 13, 21 Table 12: Solutions for group centrality on Proximity Semantic Network 2. Fig. 5: Proximity network built by non-specialists. ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: list

text: dog

text: livingthing

text: feathers

text: mammal

text: ﬂower

text: plant

text: frog

text: red

text: green

text: robin

text: hair

text: hooves

text: rose

text: leaves

text: tree

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: Proximity

text: Semantic

text: Network

text: Fig.

text: Proximity

text: network

text: built

text: by

text: non-specialists.

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: indicate “livingthing”. As for the biologists’ network they indicate “mammal”.2 Also, the four of them behaved remarkable similar when searching for central groups of diﬀerent sizes, as shown in Fig. 1. What do these examples tell? First of all, they give insights on the possi- ble relevance and use that group centrality could have for semantic networks. The contribution of this paper is a study of the assumptions that lie under this optimistically/naive hypothesis, that is, an analysis of the strengths and oppor- tunities and weaknesses and obstacles (known as SWOT analysis) of applying this idea to semantic networks. (In the related work section we will go over the work that has been done on ranking semantic networks, that touches some facets of this problem). The concrete contributions of this paper are: 1. Complexity analysis. We show that for the four previously mentioned cen- trality measures, the problem of ﬁnding a set with optimal centrality score is NP-hard (and its associated decision problem is NP-complete). 2. We present a small-scale study of samples of semantic networks –because of the hardness of the computations and the diﬃculties to get a human evaluation of what is “central” in a huge network, a challenge by itself– to show tendencies and illustrate the potential and robustness of the idea of group centrality. 3. We develop the notion of random-walk centrality, and prove several theoret- ical properties for it. In particular, we show that testing random-walk group centrality can be done in polynomial time. The paper is organized as follows. In Section 2 we present the main arguments of the SWOT analysis and related work on the subject. In Section 3 we show the study of samples of some real semantic networks. In section 4 we include the proofs and support for the theoretical arguments and in section 5 we present the conclusions. 2 Group Centrality in Social Networks Let us begin by stating formally the notions to be studied. Basic graph notions. An undirected and simple graph is a pair G = (V, E) where ⊆ E [V ]2, and [V ]2 is the set of all 2-elements subsets from V . The elements of V are the vertices of G, and the ones from E are its edges. When necessary, we will use the notation V (G) and E(G) for those sets. From now on, an element { } ∈ u, v E will be denoted simply by uv. ∈ A vertex u is said to be a neighbor of another vertex v, when uv E. Note (cid:0) (cid:1) that the deﬁnition of E implies that v is also a neighbor of u. The set of neighbors of v will be denoted by N (v). The degree of v, d (v) is the size of N (v). { G } { G } ≥ G A graph P = v , v , ..., v , v v , v v , ..., v − v with n 0, where all n 0 1 n 0 1 1 2 n 1 n v are distinct is called a path, and the number of edges in it is its length. A cycle i 2 In the experiments, the biologists were asked separately to tell the most represen- tative concept in the list, and they chose “mammal”. ##LTLine##

text: indicate

text: “livingthing”.

text: As

text: for

text: the

text: biologists’

text: network

text: they

text: indicate

text: Also,

text: the

text: four

text: of

text: them

text: behaved

text: remarkable

text: similar

text: when

text: searching

text: for

text: central

text: groups

text: of

text: diﬀerent

text: sizes,

text: as

text: shown

text: in

text: Fig.

text: What

text: do

text: these

text: examples

text: tell?

text: First

text: of

text: all,

text: they

text: give

text: insights

text: on

text: the

text: possi-

text: ble

text: relevance

text: and

text: use

text: that

text: group

text: centrality

text: could

text: have

text: for

text: semantic

text: networks.

text: The

text: contribution

text: of

text: this

text: paper

text: is

text: a

text: study

text: of

text: the

text: assumptions

text: that

text: lie

text: under

text: this

text: optimistically/naive

text: hypothesis,

text: that

text: is,

text: an

text: analysis

text: of

text: the

text: strengths

text: and

text: oppor-

text: tunities

text: and

text: weaknesses

text: and

text: obstacles

text: (known

text: as

text: SWOT

text: analysis)

text: of

text: applying

text: this

text: idea

text: to

text: semantic

text: networks.

text: (In

text: the

text: related

text: work

text: section

text: we

text: will

text: go

text: over

text: the

text: work

text: that

text: has

text: been

text: done

text: on

text: ranking

text: semantic

text: networks,

text: that

text: touches

text: some

text: facets

text: of

text: this

text: problem).

text: The

text: concrete

text: contributions

text: of

text: this

text: paper

text: are:

text: Complexity

text: analysis.

text: We

text: show

text: that

text: for

text: the

text: four

text: previously

text: mentioned

text: cen-

text: trality

text: measures,

text: the

text: problem

text: of

text: ﬁnding

text: a

text: set

text: with

text: optimal

text: centrality

text: score

text: is

text: NP-hard

text: (and

text: its

text: associated

text: decision

text: problem

text: is

text: NP-complete).

text: We

text: present

text: a

text: small-scale

text: study

text: of

text: samples

text: of

text: semantic

text: networks

text: –because

text: of

text: the

text: hardness

text: of

text: the

text: computations

text: and

text: the

text: diﬃculties

text: to

text: get

text: a

text: human

text: evaluation

text: of

text: what

text: is

text: “central”

text: in

text: a

text: huge

text: network,

text: a

text: challenge

text: by

text: itself–

text: to

text: show

text: tendencies

text: and

text: illustrate

text: the

text: potential

text: and

text: robustness

text: of

text: the

text: idea

text: of

text: group

text: centrality.

text: We

text: develop

text: the

text: notion

text: of

text: random-walk

text: centrality,

text: and

text: prove

text: several

text: theoret-

text: ical

text: properties

text: for

text: it.

text: In

text: particular,

text: we

text: show

text: that

text: testing

text: random-walk

text: group

text: centrality

text: can

text: be

text: done

text: in

text: polynomial

text: time.

text: The

text: paper

text: is

text: organized

text: as

text: follows.

text: In

text: Section

text: we

text: present

text: the

text: main

text: arguments

text: of

text: the

text: SWOT

text: analysis

text: and

text: related

text: work

text: on

text: the

text: subject.

text: In

text: Section

text: we

text: show

text: the

text: study

text: of

text: samples

text: of

text: some

text: real

text: semantic

text: networks.

text: In

text: section

text: we

text: include

text: the

text: proofs

text: and

text: support

text: for

text: the

text: theoretical

text: arguments

text: and

text: in

text: section

text: we

text: present

text: the

text: conclusions.

text: Group

text: Centrality

text: in

text: Social

text: Networks

text: Let

text: us

text: begin

text: by

text: stating

text: formally

text: the

text: notions

text: to

text: be

text: studied.

text: Basic

text: graph

text: notions.

text: An

text: undirected

text: and

text: simple

text: graph

text: is

text: a

text: pair

text: G

text: (V,

text: E)

text: where

text: E

text: [V

text: and

text: [V

text: is

text: the

text: set

text: of

text: all

text: subsets

text: from

text: V

text: The

text: elements

text: of

text: V

text: are

text: the

text: vertices

text: of

text: G,

text: and

text: the

text: ones

text: from

text: E

text: are

text: its

text: edges.

text: When

text: necessary,

text: we

text: will

text: use

text: the

text: notation

text: V

text: (G)

text: and

text: E(G)

text: for

text: those

text: sets.

text: From

text: now

text: on,

text: an

text: element

text: u,

text: v

text: E

text: will

text: be

text: denoted

text: simply

text: by

text: uv.

text: A

text: vertex

text: u

text: is

text: said

text: to

text: be

text: a

text: neighbor

text: of

text: another

text: vertex

text: v,

text: when

text: uv

text: E.

text: Note

text: that

text: the

text: deﬁnition

text: of

text: E

text: implies

text: that

text: v

text: is

text: also

text: a

text: neighbor

text: of

text: u.

text: The

text: set

text: of

text: neighbors

text: of

text: v

text: will

text: be

text: denoted

text: by

text: N

text: (v).

text: The

text: degree

text: of

text: v,

text: d

text: (v)

text: is

text: the

text: size

text: of

text: N

text: (v).

text: G

text: G

text: G

text: A

text: graph

text: P

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: with

text: n

text: where

text: all

text: n

text: n

text: n

text: n

text: v

text: are

text: distinct

text: is

text: called

text: a

text: path,

text: and

text: the

text: number

text: of

text: edges

text: in

text: it

text: is

text: its

text: length.

text: A

text: cycle

text: i

text: In

text: the

text: experiments,

text: the

text: biologists

text: were

text: asked

text: separately

text: to

text: tell

text: the

text: most

text: represen-

text: tative

text: concept

text: in

text: the

text: list,

text: and

text: they

text: chose

text: “mammal”.

text: ##LTLine##


text: n degree closeness betweenness random-walk { } { } { } { } 1 25 14 14 13 { } { } { } { } { } { } { } 2 14, 25 5, 14 , 7, 13 , 7, 14 , 8, 13 14, 25 6, 14 { } { } { } { } 3 4, 14, 25 , ... (5) 4, 14, 25 , ... (4) 4, 14, 25 0, 6, 14 { } { } { } { } 4 0, 4, 14, 25 , ... (10) 1, 4, 14, 25 , ... (2) 4, 12, 14, 25 0, 4, 14, 25 Table 15: Solutions for group centrality on Perception sample 1. Fig. 8: Sample 2 from Perception Network. Sample 2 from Perception network labels: – 0.- New Age – 16.- food – 1.- anger – 17.- fuzzy – 2.- astrology – 18.- gene – 3.- baby – 19.- joke – 4.- bad – 20.- kid – 5.- calm – 21.- laugh – 6.- cathedral – 22.- light – 7.- child – 23.- loiter – 8.- cirrus – 24.- negative – 9.- cold – 25.- old – 10.- comedy – 26.- ominous – 11.- competition – 27.- park – 12.- dangerous – 28.- pillar – 13.- dark – 29.- playground – 14.- deep – 30.- reproduction – 15.- evolution – 31.- safe ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: n

label: table

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: Perception

text: sample

text: Fig.

text: Sample

text: from

text: Perception

text: Network.

text: Sample

text: from

text: Perception

text: network

text: labels:

text: New

text: Age

text: food

text: anger

text: fuzzy

text: astrology

text: gene

text: baby

text: joke

text: bad

text: kid

text: calm

text: laugh

text: cathedral

text: light

text: child

text: loiter

text: cirrus

text: negative

text: cold

text: old

text: comedy

text: ominous

text: competition

text: park

text: dangerous

text: pillar

text: dark

text: playground

text: deep

text: reproduction

text: evolution

text: safe

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: n degree closeness betweenness random-walk { } { } { } { } 1 13 13 13 13 { } { } { } { } { } 2 0, 13 , 1, 13 , ... (2) 1, 13 0, 13 12, 13 { } { } { } { } 3 0, 1, 13 , ... (4) 0, 1, 13 0, 1, 13 0, 1, 13 { } { } { } { } 4 0, 1, 3, 13 , ... (1) 0, 1, 3, 13 0, 1, 3, 13 0, 1, 3, 13 Table 19: Solutions for group centrality on DBpedia sample 2. Fig. 12: Sample 3 from DBpedia Categories network. Sample 3 from DBpedia Categories network labels: – 0.- Neognathae – 11.- Buceros – 1.- Birds by classiﬁcation – 12.- Ceratogymna – 2.- Procellariiformes – 13.- Ocyceros – 3.- Phoenicopteriformes – 14.- Penelopides – 4.- Pelecaniformes – 15.- Bucerotinae – 5.- Hornbills – 16.- Tockus – 6.- Bucerotidae – 17.- Phalacrocoracidae – 7.- Ardeidae – 18.- Fregatidae – 8.- Egretta – 19.- Falconiformes – 9.- Aceros – 20.- Accipitridae – 10.- Anthracoceros – 21.- Oceanodroma ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

label: caption

text: for

text: group

text: centrality

text: on

text: DBpedia

text: sample

text: Fig.

text: Sample

text: from

text: DBpedia

text: Categories

text: network.

text: Sample

text: from

text: DBpedia

text: Categories

text: network

text: labels:

text: Neognathae

text: Buceros

text: Birds

text: by

text: classiﬁcation

text: Ceratogymna

text: Procellariiformes

text: Ocyceros

text: Phoenicopteriformes

text: Penelopides

text: Pelecaniformes

text: Bucerotinae

text: Hornbills

text: Tockus

text: Bucerotidae

text: Phalacrocoracidae

text: Ardeidae

text: Fregatidae

text: Egretta

text: Falconiformes

text: Aceros

text: Accipitridae

text: Anthracoceros

text: Oceanodroma

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: between pairs of vertices. A semantic network represents relations between con- cepts, motivated by an speciﬁc context. Should that context change, new and more direct connections may arise. In that regard, as much connections as pos- sible should be taken into consideration, which is precisely what random walk centrality attempts to do. (cid:80) Deﬁnition 1 (Random Walk Centrality). The random walk centrality of ⊂ S V is (cid:46) ∈ \ H(v, S) h (S) = v V| S\ | . V S Essentially random walk centrality is a variation of closeness that takes into consideration all ways to reach S from a vertex v, rather than only through the (cid:46) shortest path. As for group closeness, the lower the value of h (S), the more central the set is. 2.2 The arguments for the SWOT analysis Let us state them in general terms the arguments of the SWOT analysis. Obstacles: weaknesses and threats. First of all, the problem is computationally hard; we prove that for all four measures considered it is NP-hard: Theorem 2. The problem of ﬁnding an optimal solution S of size k, is an NP- hard problem for each of the four group centrality measures studied in this paper ∈ { (cid:46)} (that is, for C C , C , C , h ) . d c bc This theorem points to the diﬃculties of applying the notion to big data (and in this paper for experimenting with it) and gives a ﬁrst program of research on this problem: to develop good approximate algorithms for it. Second, there is a diﬃculty associated to experimenting with big data due to the lack of good benchmarks and semantically “marked” data, that is, networks for which we have a clear agreement on what are their most central concepts at diﬀerent granularities (i.e. the size of an optimum candidate). This is a challenge by itself (the scope of human physical abilities) and that is the reason why we use small (human-scale) datasets in this paper. Third, the quality of data. It turns out that the output of the centrality and group centrality methods depends heavily on the “quality” of the network: in other words, in how well it represents the semantics we are looking for. The ex- amples we discussed on section 1 are prime cases of excellent semantic networks (in fact, developed by psychologists based on systematic experimentation). Un- fortunately, the semantic networks that we see in real life (for example RDF data) are usually not as good. We will show through several sample datasets that many of our current most popular semantic data representations (e.g. RDF graphs) have a bias as they are mostly constructed in ad-hoc manners (union of pieces of information scattered from diﬀerent sources; without the goal of completeness, etc).3 3 We are well aware of the complexities of determining in a network of concepts which one is more relevant. This relies on the underlying semantics of the notions involved, ##LTLine## ##LTLine##

text: between

text: pairs

text: of

text: vertices.

text: A

text: semantic

text: network

text: represents

text: relations

text: between

text: con-

text: cepts,

text: motivated

text: by

text: an

text: speciﬁc

text: context.

text: Should

text: that

text: context

text: change,

text: new

text: and

text: more

text: direct

text: connections

text: may

text: arise.

text: In

text: that

text: regard,

text: as

text: much

text: connections

text: as

text: pos-

text: sible

text: should

text: be

text: taken

text: into

text: consideration,

text: which

text: is

text: precisely

text: what

text: random

text: walk

text: centrality

text: attempts

text: to

text: do.

text: Deﬁnition

text: (Random

text: Walk

text: Centrality).

text: The

text: random

text: walk

text: centrality

text: of

text: S

text: V

text: is

text: H(v,

text: S)

text: h

text: (S)

text: v

text: V|

text: S\

text: V

text: S

text: Essentially

text: random

text: walk

text: centrality

text: is

text: a

text: variation

text: of

text: closeness

text: that

text: takes

text: into

text: consideration

text: all

text: ways

text: to

text: reach

text: S

text: from

text: a

text: vertex

text: v,

text: rather

text: than

text: only

text: through

text: the

text: shortest

text: path.

text: As

text: for

text: group

text: closeness,

text: the

text: lower

text: the

text: value

text: of

text: h

text: (S),

text: the

text: more

text: central

text: the

text: set

text: is.

text: The

text: arguments

text: for

text: the

text: SWOT

text: analysis

text: Let

text: us

text: state

text: them

text: in

text: general

text: terms

text: the

text: arguments

text: of

text: the

text: SWOT

text: analysis.

text: Obstacles:

text: weaknesses

text: and

text: threats.

text: First

text: of

text: all,

text: the

text: problem

text: is

text: computationally

text: hard;

text: we

text: prove

text: that

text: for

text: all

text: four

text: measures

text: considered

text: it

text: is

text: NP-hard:

text: Theorem

text: The

text: problem

text: of

text: ﬁnding

text: an

text: optimal

text: solution

text: S

text: of

text: size

text: k,

text: is

text: an

text: NP-

text: hard

text: problem

text: for

text: each

text: of

text: the

text: four

text: group

text: centrality

text: measures

text: studied

text: in

text: this

text: paper

text: (that

text: is,

text: for

text: C

text: C

text: C

text: C

text: h

text: d

text: c

text: bc

text: This

text: theorem

text: points

text: to

text: the

text: diﬃculties

text: of

text: applying

text: the

text: notion

text: to

text: big

text: data

text: (and

text: in

text: this

text: paper

text: for

text: experimenting

text: with

text: it)

text: and

text: gives

text: a

text: ﬁrst

text: program

text: of

text: research

text: on

text: this

text: problem:

text: to

text: develop

text: good

text: approximate

text: algorithms

text: for

text: it.

text: Second,

text: there

text: is

text: a

text: diﬃculty

text: associated

text: to

text: experimenting

text: with

text: big

text: data

text: due

text: to

text: the

text: lack

text: of

text: good

text: benchmarks

text: and

text: semantically

text: “marked”

text: data,

text: that

text: is,

text: networks

text: for

text: which

text: we

text: have

text: a

text: clear

text: agreement

text: on

text: what

text: are

text: their

text: most

text: central

text: concepts

text: at

text: diﬀerent

text: granularities

text: (i.e.

text: the

text: size

text: of

text: an

text: optimum

text: candidate).

text: This

text: is

text: a

text: challenge

text: by

text: itself

text: (the

text: scope

text: of

text: human

text: physical

text: abilities)

text: and

text: that

text: is

text: the

text: reason

text: why

text: we

text: use

text: small

text: (human-scale)

text: datasets

text: in

text: this

text: paper.

text: Third,

text: the

text: quality

text: of

text: data.

text: It

text: turns

text: out

text: that

text: the

text: output

text: of

text: the

text: centrality

text: and

text: group

text: centrality

text: methods

text: depends

text: heavily

text: on

text: the

text: “quality”

text: of

text: the

text: network:

text: in

text: other

text: words,

text: in

text: how

text: well

text: it

text: represents

text: the

text: semantics

text: we

text: are

text: looking

text: for.

text: The

text: ex-

text: amples

text: we

text: discussed

text: on

text: section

text: are

text: prime

text: cases

text: of

text: excellent

text: semantic

text: networks

text: (in

text: fact,

text: developed

text: by

text: psychologists

text: based

text: on

text: systematic

text: experimentation).

text: Un-

text: fortunately,

text: the

text: semantic

text: networks

text: that

text: we

text: see

text: in

text: real

text: life

text: (for

text: example

text: RDF

text: data)

text: are

text: usually

text: not

text: as

text: good.

text: We

text: will

text: show

text: through

text: several

text: sample

text: datasets

text: that

text: many

text: of

text: our

text: current

text: most

text: popular

text: semantic

text: data

text: representations

text: (e.g.

text: RDF

text: graphs)

text: have

text: a

text: bias

text: as

text: they

text: are

text: mostly

text: constructed

text: in

text: ad-hoc

text: manners

text: (union

text: of

text: pieces

text: of

text: information

text: scattered

text: from

text: diﬀerent

text: sources;

text: without

text: the

text: goal

text: of

text: completeness,

text: We

text: are

text: well

text: aware

text: of

text: the

text: complexities

text: of

text: determining

text: in

text: a

text: network

text: of

text: concepts

text: which

text: one

text: is

text: more

text: relevant.

text: This

text: relies

text: on

text: the

text: underlying

text: semantics

text: of

text: the

text: notions

text: involved,

text: ##LTLine##

text: ##LTLine##


text: n degree closeness betweenness random-walk { } { } { } { } { } 1 4 , 20 4 20 4 { } { } { } { } 2 4, 20 4, 20 4, 20 4, 20 { } { } { } { } { } 3 4, 6, 20 , 6, 7, 20 0, 4, 20 4, 7, 20 4, 18, 20 { } { } { } { } { } 4 4, 6, 18, 20 , 0, 4, 6, 20 0, 4, 6, 20 4, 6, 7, 20 4, 6, 18, 20 Table 5: Solutions for group centrality on DBpedia sample 1. n degree closeness betweenness random-walk { } { } { } { } 1 13 13 13 13 { } { } { } { } { } 2 0, 13 , 1, 13 , ... (2) 1, 13 0, 13 12, 13 { } { } { } { } 3 0, 1, 13 , ... (4) 0, 1, 13 0, 1, 13 0, 1, 13 { } { } { } { } 4 0, 1, 3, 13 , ... (1) 0, 1, 3, 13 0, 1, 3, 13 0, 1, 3, 13 Table 6: Solutions for group centrality on DBpedia sample 2. n degree closeness betweenness random-walk { } { } { } { } 1 25 14 14 13 { } { } { } { } { } { } { } 2 14, 25 5, 14 , 7, 13 , 7, 14 , 8, 13 14, 25 6, 14 { } { } { } { } 3 4, 14, 25 , ... (5) 4, 14, 25 , ... (4) 4, 14, 25 0, 6, 14 { } { } { } { } 4 0, 4, 14, 25 , ... (10) 1, 4, 14, 25 , ... (2) 4, 12, 14, 25 0, 4, 14, 25 Table 7: Solutions for group centrality on Perception sample 1. n degree closeness betweenness random-walk { } { } { } { } 1 29 , ... (1) 15 1 29 { } { } { } { } 2 2, 29 0, 15 , ... (1) 1, 2 29, 39 { } { } { } { } 3 2, 8, 29 , ... (3) 0, 15, 32 , ... (7) 1, 2, 8 2, 8, 39 { } { } { } { } 4 2, 8, 29, 39 , ... (2) 2, 26, 29, 39 , ... (1) 2, 8, 10, 29 2, 26, 29, 39 Table 8: Solutions for group centrality on Perception sample 2. n degree closeness betweenness random-walk { } { } { } { } 1 10 35 35 10 { } { } { } { } 2 10, 25 10, 25 25, 35 10, 25 { } { } { } { } 3 10, 25, 39 10, 25, 39 10, 25, 35 10, 25, 39 { } { } { } { } 4 10, 17, 25, 39 , ... (87) 10, 17, 25, 39 , ... (87) 10, 17, 25, 35 10, 17, 25, 39 Table 9: Solutions for group centrality on Roget’s Thesaurus sample 1. n degree closeness betweenness random-walk { } { } { } { } 1 11 37 37 37 { } { } { } { } 2 11, 14 14, 26 26, 37 14, 26 { } { } { } { } 3 1, 14, 29 , ... (6) 11, 14, 29 , ... (6) 11, 26, 37 11, 14, 29 { } { } { } { } 4 11, 14, 29, 37 , ... (440) 11, 14, 29, 37 , ... (440) 11, 14, 26, 37 11, 14, 29, 37 Table 10: Solutions for group centrality on Roget’s Thesaurus sample 2. 3.2 Discussion of results For each semantic network, and each centrality measure, we computed the optimal solutions of size 1, 2, 3, and 4. The results are presented in Tables 1 to 10. It is important to note that in some cases there were multiple candidates for ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: DBpedia

text: sample

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: DBpedia

text: sample

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: Perception

text: sample

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: Perception

text: sample

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: Roget’s

text: Thesaurus

text: sample

text: n

text: degree

text: closeness

text: betweenness

text: random-walk

text: Table

text: Solutions

text: for

text: group

text: centrality

text: on

text: Roget’s

text: Thesaurus

text: sample

text: Discussion

text: of

text: results

text: For

text: each

text: semantic

text: network,

text: and

text: each

text: centrality

text: measure,

text: we

text: computed

text: the

text: optimal

text: solutions

text: of

text: size

text: and

text: The

text: results

text: are

text: presented

text: in

text: Tables

text: to

text: It

text: is

text: important

text: to

text: note

text: that

text: in

text: some

text: cases

text: there

text: were

text: multiple

text: candidates

text: for

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: optimal solution, but we only include at most two of them4 (if there are more than two solutions, there is a mark “... (n)” where n is the number of extra solutions) . From the results obtained, we can advance two main observations: Robustness of group centrality. It is noticeable that in the samples the optimal solutions for all centrality measures become similar as the size k of the set increases. Indeed, for groups of size 1, it can observed that there are networks for which the solution is diﬀerent, depending on the centrality notion applied (e.g. Table 13). On the other hand, for groups of size 4, it can be observed that in most networks there is a common set of nodes selected by all four diﬀerent measures used. Non-ambiguity of group random-walk. As stated previously, for a given size k, more than one optimal solution may exist for group centrality. Moreover, from the results it can be inferred that as k increases, so does the number of optimal candidates for certain particular measures. For example, Table 11 shows that degree and closeness centrality have 24 (resp. 6) optimal solutions of size 4. There is even an extreme case in Table 23, where degree and closeness have more than 400 diﬀerent optimal group solutions. In a small sample of 40 nodes this variance does not help achieve the proposed goal. However, betweenness centrality seems to behave in general better in this matter (there is some dispersion, e.g. Table 14, but it is small). Random-walk centrality, on the other hand, is consistently better in this regard. In our sample selections, it is the only notion for which there is systematically a unique optimal solution for any size, and for all the networks. 4 Theoretical aspects of Group Centrality As we saw in previous sections, group centrality oﬀers interesting new insights on semantic networks. In this section we study the notion from a theoretical point of view, focusing in the complexity of computing it. 4.1 Complexity of Group Centrality Let us deﬁne formally the problem of computing the most central set of nodes in a network under diﬀerent centrality measures. Deﬁnition 3 (Optimumset). Given a graph G = (V, E), a positive integer k P → R and a function C : (V ) , deﬁne optimumset(G, k, C) as the problem of ⊂ ﬁnding a set S V , of size k such that ∈ S arg min C(S). ⊂ | | U V ; U =k For a real number α > 0, optimumset(G, k, C, α) will denote the corresponding ⊂ decision problem: ﬁnd if there exists a set S V , of size k such that C(S) = α. Theorem 2. optimumset(G, k, C, α) is NP-complete for all four group central- ∈ { (cid:46)} ity measures studied in this paper (that is, for C C , C , C , h ). d c bc 4 The complete results, graphs and labels of the networks can be found in the ap- pendix. ##LTLine##

text: optimal

text: solution,

text: but

text: we

text: only

text: include

text: at

text: most

text: two

text: of

text: (if

text: there

text: are

text: more

text: than

text: two

text: solutions,

text: there

text: is

text: a

text: mark

text: (n)”

text: where

text: n

text: is

text: the

text: number

text: of

text: extra

text: solutions)

text: From

text: the

text: results

text: obtained,

text: we

text: can

text: advance

text: two

text: main

text: observations:

text: Robustness

text: of

text: group

text: centrality.

text: It

text: is

text: noticeable

text: that

text: in

text: the

text: samples

text: the

text: optimal

text: solutions

text: for

text: all

text: centrality

text: measures

text: become

text: similar

text: as

text: the

text: size

text: k

text: of

text: the

text: set

text: increases.

text: Indeed,

text: for

text: groups

text: of

text: size

text: it

text: can

text: observed

text: that

text: there

text: are

text: networks

text: for

text: which

text: the

text: solution

text: is

text: diﬀerent,

text: depending

text: on

text: the

text: centrality

text: notion

text: applied

text: (e.g.

text: Table

text: On

text: the

text: other

text: hand,

text: for

text: groups

text: of

text: size

text: it

text: can

text: be

text: observed

text: that

text: in

text: most

text: networks

text: there

text: is

text: a

text: common

text: set

text: of

text: nodes

text: selected

text: by

text: all

text: four

text: diﬀerent

text: measures

text: used.

text: Non-ambiguity

text: of

text: group

text: random-walk.

text: As

text: stated

text: previously,

text: for

text: a

text: given

text: size

text: k,

text: more

text: than

text: one

text: optimal

text: solution

text: may

text: exist

text: for

text: group

text: centrality.

text: Moreover,

text: from

text: the

text: results

text: it

text: can

text: be

text: inferred

text: that

text: as

text: k

text: increases,

text: so

text: does

text: the

text: number

text: of

text: optimal

text: candidates

text: for

text: certain

text: particular

text: measures.

text: For

text: example,

text: Table

text: shows

text: that

text: degree

text: and

text: closeness

text: centrality

text: have

text: (resp.

text: optimal

text: solutions

text: of

text: size

text: There

text: is

text: even

text: an

text: extreme

text: case

text: in

text: Table

text: where

text: degree

text: and

text: closeness

text: have

text: more

text: than

text: diﬀerent

text: optimal

text: group

text: solutions.

text: In

text: a

text: small

text: sample

text: of

text: nodes

text: this

text: variance

text: does

text: not

text: help

text: achieve

text: the

text: proposed

text: goal.

text: However,

text: betweenness

text: centrality

text: seems

text: to

text: behave

text: in

text: general

text: better

text: in

text: this

text: matter

text: (there

text: is

text: some

text: dispersion,

text: e.g.

text: Table

text: but

text: it

text: is

text: small).

text: Random-walk

text: centrality,

text: on

text: the

text: other

text: hand,

text: is

text: consistently

text: better

text: in

text: this

text: regard.

text: In

text: our

text: sample

text: selections,

text: it

text: is

text: the

text: only

text: notion

text: for

text: which

text: there

text: is

text: systematically

text: a

text: unique

text: optimal

text: solution

text: for

text: any

text: size,

text: and

text: for

text: all

text: the

text: networks.

text: Theoretical

text: aspects

text: of

text: Group

text: Centrality

text: As

text: we

text: saw

text: in

text: previous

text: sections,

text: group

text: centrality

text: oﬀers

text: interesting

text: new

text: insights

text: on

text: semantic

text: networks.

text: In

text: this

text: section

text: we

text: study

text: the

text: notion

text: from

text: a

text: theoretical

text: point

text: of

text: view,

text: focusing

text: in

text: the

text: complexity

text: of

text: computing

text: it.

text: Complexity

text: of

text: Group

text: Centrality

text: Let

text: us

text: deﬁne

text: formally

text: the

text: problem

text: of

text: computing

text: the

text: most

text: central

text: set

text: of

text: nodes

text: in

text: a

text: network

text: under

text: diﬀerent

text: centrality

text: measures.

text: Deﬁnition

text: (Optimumset).

text: Given

text: a

text: graph

text: G

text: (V,

text: E),

text: a

text: positive

text: integer

text: k

text: P

text: R

text: and

text: a

text: function

text: C

text: (V

text: deﬁne

text: optimumset(G,

text: k,

text: C)

text: as

text: the

text: problem

text: of

text: ﬁnding

text: a

text: set

text: S

text: V

text: of

text: size

text: k

text: such

text: that

text: S

text: arg

text: min

text: C(S).

text: U

text: V

text: U

text: =k

text: For

text: a

text: real

text: number

text: α

text: optimumset(G,

text: k,

text: C,

text: α)

text: will

text: denote

text: the

text: corresponding

text: decision

text: problem:

text: ﬁnd

text: if

text: there

text: exists

text: a

text: set

text: S

text: V

text: of

text: size

text: k

text: such

text: that

text: C(S)

text: α.

text: Theorem

text: optimumset(G,

text: k,

text: C,

text: α)

text: is

text: NP-complete

text: for

text: all

text: four

text: group

text: central-

text: ity

text: measures

text: studied

text: in

text: this

text: paper

text: (that

text: is,

text: for

text: C

text: C

text: C

text: C

text: h

text: d

text: c

text: bc

text: The

text: complete

text: results,

text: graphs

text: and

text: labels

text: of

text: the

text: networks

text: can

text: be

text: found

text: in

text: the

text: ap-

text: pendix.

text: ##LTLine##


text: (cid:16) (cid:17) (ii) (Polynomial tails) { }− (cid:107) (cid:107) 2 { − } n > 21233 min π 2K2C2C2λ4 1 + ρ L 1/2 s log p max λ , 4λ4 α 1 . k 1 2 Θ 2 2 Ψ Θ k Corollary 2. Suppose that Conditions 3, 6 and 8 hold. Suppose also that Condition 5 holds ⊗ (k) (k) without requiring the invertibility of (Θ Θ ) . Then, under Condition 1 or 2, 0 0 S(k)S(k) M → → ∞ P ( (Ωˆ , Ω )) 1 as n, p where ρ is given in Lemma 1 in the Appendix with ρn 0 n γ = min π /2. k k 4 Laplacian Shrinkage based on Hierarchical Clustering Our proposed LASICH approach utilizes the information in the subpopulation network G. In practice, however, similarity between subpopulations may be diﬃcult to ascertain or quantify. In this section, we present a modiﬁed LASICH framework, called HC-LASICH, which utilizes hierarchical clustering to learn the relationships among subpopulations. The information from hierarchical clustering is then used to deﬁne the weighted subpopulation network. Importantly, HC-LASICH can even be used in settings where the subpopulation membership is unavailable, for instance, to learn the genetic network of cancer patients, where cancer subtypes may be unknown. We use hierarchical clustering with a complete, single or average linkage to estimate both the subpopulation memberships and the weighted subpopulation network G. Speciﬁcally, the length of a path between two subpopulations in the dendrogram is used as a measure of dissimilarity between two subpopulations; the weights for the subpopulation networks are simply deﬁned by taking the inverse of these lengths. Throughout this section, we assume that the number of subpopulations K is known. While a number of methods have been proposed for estimating the number of subpopulations in hierarchical clustering (see e.g. Borysov et al. (2014) and the references therein), the problem is beyond the scope of this paper. I I I I Let = ( (1), . . . , (K)) be the subpopulation membership indicator such that follows the multinomial distribution Mult (1, (π , . . . , π )) with parameter 1 and subpopulation mem- K 1 K ∈ I bership probabilities (π , . . . , π ) (0, 1)K. Note that is missing and is to be estimated. 1 K I I I I I Let , i = 1, . . . , n be i.i.d. copies of and ˆ = (ˆ1, . . . , ˆK) be an estimated subpopu- i i i i lation indicator for the ith observation via hierarchical clustering. Based on the estimated subpopulation membership and subpopulation network Gˆ, we apply our method to obtain 17

text: (ii)

text: (Polynomial

text: tails)

text: n

text: min

text: π

text: ρ

text: L

text: s

text: log

text: p

text: max

text: λ

text: α

text: k

text: Θ

text: Ψ

text: Θ

text: k

text: Corollary

text: Suppose

text: that

text: Conditions

text: and

text: hold.

text: Suppose

text: also

text: that

text: Condition

text: holds

text: (k)

text: (k)

text: without

text: requiring

text: the

text: invertibility

text: of

text: (Θ

text: Θ

text: Then,

text: under

text: Condition

text: or

text: S(k)S(k)

text: M

text: P

text: (Ωˆ

text: Ω

text: as

text: n,

text: p

text: where

text: ρ

text: is

text: given

text: in

text: Lemma

text: in

text: the

text: Appendix

text: with

text: ρn

text: n

text: γ

text: min

text: π

text: k

text: k

text: Laplacian

text: Shrinkage

text: based

text: on

text: Hierarchical

text: Clustering

text: Our

text: proposed

text: LASICH

text: approach

text: utilizes

text: the

text: information

text: in

text: the

text: subpopulation

text: network

text: G.

text: In

text: practice,

text: however,

text: similarity

text: between

text: subpopulations

text: may

text: be

text: diﬃcult

text: to

text: ascertain

text: or

text: quantify.

text: In

text: this

text: section,

text: we

text: present

text: a

text: modiﬁed

text: LASICH

text: framework,

text: called

text: HC-LASICH,

text: which

text: utilizes

text: hierarchical

text: clustering

text: to

text: learn

text: the

text: relationships

text: among

text: subpopulations.

text: The

text: information

text: from

text: hierarchical

text: clustering

text: is

text: then

text: used

text: to

text: deﬁne

text: the

text: weighted

text: subpopulation

text: network.

text: Importantly,

text: HC-LASICH

text: can

text: even

text: be

text: used

text: in

text: settings

text: where

text: the

text: subpopulation

text: membership

text: is

text: unavailable,

text: for

text: instance,

text: to

text: learn

text: the

text: genetic

text: network

text: of

text: cancer

text: patients,

text: where

text: cancer

text: subtypes

text: may

text: be

text: unknown.

text: We

text: use

text: hierarchical

text: clustering

text: with

text: a

text: complete,

text: single

text: or

text: average

text: linkage

text: to

text: estimate

text: both

text: the

text: subpopulation

text: memberships

text: and

text: the

text: weighted

text: subpopulation

text: network

text: G.

text: Speciﬁcally,

text: the

text: length

text: of

text: a

text: path

text: between

text: two

text: subpopulations

text: in

text: the

text: dendrogram

text: is

text: used

text: as

text: a

text: measure

text: of

text: dissimilarity

text: between

text: two

text: subpopulations;

text: the

text: weights

text: for

text: the

text: subpopulation

text: networks

text: are

text: simply

text: deﬁned

text: by

text: taking

text: the

text: inverse

text: of

text: these

text: lengths.

text: Throughout

text: this

text: section,

text: we

text: assume

text: that

text: the

text: number

text: of

text: subpopulations

text: K

text: is

text: known.

text: While

text: a

text: number

text: of

text: methods

text: have

text: been

text: proposed

text: for

text: estimating

text: the

text: number

text: of

text: subpopulations

text: in

text: hierarchical

text: clustering

text: (see

text: e.g.

text: Borysov

text: et

text: al.

text: and

text: the

text: references

text: therein),

text: the

text: problem

text: is

text: beyond

text: the

text: scope

text: of

text: this

text: paper.

text: I

text: I

text: I

text: I

text: Let

text: (K))

text: be

text: the

text: subpopulation

text: membership

text: indicator

text: such

text: that

text: follows

text: the

text: multinomial

text: distribution

text: Mult

text: (π

text: π

text: with

text: parameter

text: and

text: subpopulation

text: mem-

text: K

text: K

text: I

text: bership

text: probabilities

text: (π

text: π

text: Note

text: that

text: is

text: missing

text: and

text: is

text: to

text: be

text: estimated.

text: K

text: I

text: I

text: I

text: I

text: I

text: Let

text: i

text: n

text: be

text: i.i.d.

text: copies

text: of

text: and

text: ˆ

text: ˆK)

text: be

text: an

text: estimated

text: subpopu-

text: i

text: i

text: i

text: i

text: lation

text: indicator

text: for

text: the

text: ith

text: observation

text: via

text: hierarchical

text: clustering.

text: Based

text: on

text: the

text: estimated

text: subpopulation

text: membership

text: and

text: subpopulation

text: network

text: Gˆ,

text: we

text: apply

text: our

text: method

text: to

text: obtain


text: the estimator, HC-LASICH, Ωˆ = (Ωˆ(1) , . . . , Ωˆ(K) ). Interestingly, HC-LASICH en- HC,ρn HC,ρn HC,ρn joys the same theoretical properties as LASICH, under the normality assumption. To show this, we ﬁrst establish the consistency of hierarchical clustering in high dimensions, which is of independent interest. Our result is motivated by the recent work of (Borysov et al., 2014), who study the consistency of hierarchical clustering for independent normal variables ∼ X(k) N(µ(k), σ(k)I); we establish similar results for multivariate normal distributions with arbitrary covariance structures. We make the following assumption. (cid:48) Condition 9. For k, k = 1, . . . , K, let (cid:88) p − λ(k) = p 1 (cid:13)(cid:13) λ(k),j, (cid:104) (cid:105) (cid:104) (cid:105)(cid:13)(cid:13) (cid:13) (cid:13) j=(cid:13)1 (cid:13) (cid:48) − (cid:48) 1/2 − (cid:48) 2 µ(k,k ) = p 1 Λ1/2(cid:48)QT (cid:48) Σ(k) + Σ(k ) µ(k) µ(k ) , k,k k,k ≤ ≤ ≤ where λ(k),j is the eigenvalues of Σ(k) with λ(k),1 λ(k),2 . . . λ(k),p, and the spectral (cid:48) (cid:48) decomposition of Σ(k) + Σ(k ) is Σ(k) + Σ(k ) = Q (cid:48)Λ (cid:48)QT (cid:48). It holds that k,k k,k k,k (cid:110) (cid:111) (cid:48) (cid:48) − − (cid:48) (cid:54) (cid:48) (cid:48) µ(k,k ) > 2 min λ(k), λ(k ) λ(k),p λ(k ),p, k = k , k, k = 1, . . . , K, ≤ ≤ ∞ (cid:107) (cid:107) ≤ 0 < c λ(k),j c < , µ(k) c , k = 1, . . . , K, j = 1, . . . , p. 10 11 11 for constants m and M. Under the normality assumption, the following results shows that the probability of suc- → ∞ cessful clustering converges to 1, as p, n . Theorem 3. Suppose that that X(k), k = 1, . . . , K, is normally distributed. Under Condition 9, I I → P (ˆ = , i = 1, . . . , n) 1, (7) i i → ∞ as n, p . 18 ##LTLine## ##LTLine## ##LTLine##

text: the

text: estimator,

text: HC-LASICH,

text: Ωˆ

text: Ωˆ(K)

text: Interestingly,

text: HC-LASICH

text: en-

text: HC,ρn

text: HC,ρn

text: HC,ρn

text: joys

text: the

text: same

text: theoretical

text: properties

text: as

text: LASICH,

text: under

text: the

text: normality

text: assumption.

text: To

text: show

text: this,

text: we

text: ﬁrst

text: establish

text: the

text: consistency

text: of

text: hierarchical

text: clustering

text: in

text: high

text: dimensions,

text: which

text: is

text: of

text: independent

text: interest.

text: Our

text: result

text: is

text: motivated

text: by

text: the

text: recent

text: work

text: of

text: (Borysov

text: et

text: al.,

text: who

text: study

text: the

text: consistency

text: of

text: hierarchical

text: clustering

text: for

text: independent

text: normal

text: variables

text: X(k)

text: N(µ(k),

text: σ(k)I);

text: we

text: establish

text: similar

text: results

text: for

text: multivariate

text: normal

text: distributions

text: with

text: arbitrary

text: covariance

text: structures.

text: We

text: make

text: the

text: following

text: assumption.

text: Condition

text: For

text: k,

text: k

text: K,

text: let

text: p

text: λ(k)

text: p

text: λ(k),j,

text: µ(k,k

text: p

text: Σ(k)

text: Σ(k

text: µ(k)

text: µ(k

text: k,k

text: k,k

text: where

text: λ(k),j

text: is

text: the

text: eigenvalues

text: of

text: Σ(k)

text: with

text: λ(k),p,

text: and

text: the

text: spectral

text: decomposition

text: of

text: Σ(k)

text: Σ(k

text: is

text: Σ(k)

text: Σ(k

text: Q

text: It

text: holds

text: that

text: k,k

text: k,k

text: k,k

text: µ(k,k

text: min

text: λ(k),

text: λ(k

text: λ(k),p

text: λ(k

text: ),p,

text: k

text: k

text: k,

text: k

text: K,

text: c

text: λ(k),j

text: c

text: µ(k)

text: c

text: k

text: K,

text: j

text: p.

text: for

text: constants

text: m

text: and

text: M.

text: Under

text: the

text: normality

text: assumption,

text: the

text: following

text: results

text: shows

text: that

text: the

text: probability

text: of

text: suc-

text: cessful

text: clustering

text: converges

text: to

text: as

text: p,

text: n

text: Theorem

text: Suppose

text: that

text: that

text: X(k),

text: k

text: K,

text: is

text: normally

text: distributed.

text: Under

text: Condition

text: I

text: I

text: P

text: (ˆ

text: i

text: n)

text: i

text: i

text: as

text: n,

text: p

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ≥ (k) (k) ω = δ γ . Identiﬁability of the estimates is ensured by assuming δ 0. A zero common ij ij ij ij (k) factor δ = 0 induces sparsity across all subpopulations, whereas γ = 0 results in condition- ij (cid:80) (cid:80)ij (cid:80) (k) speciﬁc sparsity for ω . This reparametrization results in a non-convex optimization problem ij | | based on the Gaussian likelihood with (cid:96) -penalties (cid:54) δ and (cid:54) K γ(k) . Danaher 1 i=j ij i=(cid:80)j k(cid:80)=1 ij et al. (2014) proposed two alternative(cid:113)estimators by adding an additional convex penalty to (cid:80) (cid:80) | − (cid:48)| the graphical lasso objective function: either a fused lasso penalty (cid:54) (cid:54) (cid:48) ω(k) ωk i=j k=k ij ij (FGL), or a group lasso penalty (cid:54) K (ω(k))2 (GGL). The fused lasso penalty has also i=j k=1 ij been used by Kolar et al. (2009), for joint estimation of multiple graphical models in multiple (k) time points. The fused lasso penalty strongly encourages the values of ω to be similar across ij all subpopulations, both in values as well as sparsity patterns. On the other hand, the group (cid:80) (k) lasso penalty results in similar estimates by shrinking all ω across subpopulations to zero ij if K (ω(k))2 is small. k=1 ij Despite their diﬀerences, methods of Guo et al. (2011) and Danaher et al. (2014) inherently assume that precision matrices in K subpopulations are equally similar to each other, in that (cid:48) (cid:48)(cid:48) (k) (k ) (k) (k ) they encourage ω and ω and ω and ω to be equally similar. However, when K > 2, ij ij ij ij some subpopulations are expected to be more similar to each other than others. For instance, it is expected that genetic networks of two subtypes of cancer be more similar to each other than to the network of normal cells. Similarly, diﬀerences among genetic networks of various strains of a virus or bacterium are expected to correspond to the evolutionary lineages of their phylogenetic trees. Unfortunately, existing methods for joint estimation of multiple graphical models ignore this heterogeneity in multiple subpopulations. Furthermore, existing methods assume subpopulation memberships are known, which limits their applicability in settings with complex but unknown population structures; an important example is estimation of genetic networks of cancer cells with unknown subtypes. In this paper, we propose a general framework for joint estimation of multiple precision matrices by capturing the heterogeneity among subpopulations. In this framework, similarities among disparate subpopulations are presented using a subpopulation network G(V, E, W ), a weighted graph whose node set V is the set of subpopulations. The edges in E and the weights (cid:48) ∈ (cid:48) W (cid:48) for (k, k ) E represent the degree of similarity between any two subpopulations k, k . In kk (cid:48) the special case where W (cid:48) = 1 for all k, k , the subpopulation similarities are only captured kk by the structure of the graph G. An example of such a subpopulation network is the line graph corresponding to observations over multiple time points, which is used in estimation of 3 ##LTLine##

text: (k)

text: (k)

text: ω

text: δ

text: γ

text: Identiﬁability

text: of

text: the

text: estimates

text: is

text: ensured

text: by

text: assuming

text: δ

text: A

text: zero

text: common

text: ij

text: ij

text: ij

text: ij

text: (k)

text: factor

text: δ

text: induces

text: sparsity

text: across

text: all

text: subpopulations,

text: whereas

text: γ

text: results

text: in

text: condition-

text: ij

text: (k)

text: speciﬁc

text: sparsity

text: for

text: ω

text: This

text: reparametrization

text: results

text: in

text: a

text: non-convex

text: optimization

text: problem

text: ij

text: based

text: on

text: the

text: Gaussian

text: likelihood

text: with

text: -penalties

font: default

text: δ

text: and

text: K

text: γ(k)

text: Danaher

text: i=j

text: ij

text: ij

text: et

text: al.

text: proposed

text: two

text: by

text: adding

text: an

text: additional

text: convex

text: penalty

text: to

text: the

text: graphical

text: lasso

text: objective

text: function:

text: either

text: a

text: fused

text: lasso

text: penalty

text: ω(k)

text: ωk

text: i=j

text: k=k

text: ij

text: ij

text: (FGL),

text: or

text: a

text: group

text: lasso

text: penalty

text: K

text: (GGL).

text: The

text: fused

text: lasso

text: penalty

text: has

text: also

text: i=j

text: ij

text: been

text: used

text: by

text: Kolar

text: et

text: al.

text: for

text: joint

text: estimation

text: of

text: multiple

text: graphical

text: models

text: in

text: multiple

text: (k)

text: time

text: points.

text: The

text: fused

text: lasso

text: penalty

text: strongly

text: encourages

text: the

text: values

text: of

text: ω

text: to

text: be

text: similar

text: across

text: ij

text: all

text: subpopulations,

text: both

text: in

text: values

text: as

text: well

text: as

text: sparsity

text: patterns.

text: On

text: the

text: other

text: hand,

text: the

text: group

text: (k)

text: lasso

text: penalty

text: results

text: in

text: similar

text: estimates

text: by

text: shrinking

text: all

text: ω

text: across

text: subpopulations

text: to

text: zero

text: ij

text: if

text: K

text: is

text: small.

text: ij

text: Despite

text: their

text: diﬀerences,

text: methods

text: of

text: Guo

text: et

text: al.

text: and

text: Danaher

text: et

text: al.

text: inherently

text: assume

text: that

text: precision

text: matrices

text: in

text: K

text: subpopulations

text: are

text: equally

text: similar

text: to

text: each

text: other,

text: in

text: that

text: (k)

text: (k

text: (k)

text: (k

text: they

text: encourage

text: ω

text: and

text: ω

text: and

text: ω

text: and

text: ω

text: to

text: be

text: equally

text: similar.

text: However,

text: when

text: K

text: ij

text: ij

text: ij

text: ij

text: some

text: subpopulations

text: are

text: expected

text: to

text: be

text: more

text: similar

text: to

text: each

text: other

text: than

text: others.

text: For

text: instance,

text: it

text: is

text: expected

text: that

text: genetic

text: networks

text: of

text: two

text: subtypes

text: of

text: cancer

text: be

text: more

text: similar

text: to

text: each

text: other

text: than

text: to

text: the

text: network

text: of

text: normal

text: cells.

text: Similarly,

text: diﬀerences

text: among

text: genetic

text: networks

text: of

text: various

text: strains

text: of

text: a

text: virus

text: or

text: bacterium

text: are

text: expected

text: to

text: correspond

text: to

text: the

text: evolutionary

text: lineages

text: of

text: their

text: phylogenetic

text: trees.

text: Unfortunately,

text: existing

text: methods

text: for

text: joint

text: estimation

text: of

text: multiple

text: graphical

text: models

text: ignore

text: this

text: heterogeneity

text: in

text: multiple

text: subpopulations.

text: Furthermore,

text: existing

text: methods

text: assume

text: subpopulation

text: memberships

text: are

text: known,

text: which

text: limits

text: their

text: applicability

text: in

text: settings

text: with

text: complex

text: but

text: unknown

text: population

text: structures;

text: an

text: important

text: example

text: is

text: estimation

text: of

text: genetic

text: networks

text: of

text: cancer

text: cells

text: with

text: unknown

text: subtypes.

text: In

text: this

text: paper,

text: we

text: propose

text: a

text: general

text: framework

text: for

text: joint

text: estimation

text: of

text: multiple

text: precision

text: matrices

text: by

text: capturing

text: the

text: heterogeneity

text: among

text: subpopulations.

text: In

text: this

text: framework,

text: similarities

text: among

text: disparate

text: subpopulations

text: are

text: presented

text: using

text: a

text: subpopulation

text: network

text: G(V,

text: E,

text: W

text: a

text: weighted

text: graph

text: whose

text: node

text: set

text: V

text: is

text: the

text: set

text: of

text: subpopulations.

text: The

text: edges

text: in

text: E

text: and

text: the

text: weights

text: W

text: for

text: (k,

text: k

text: E

text: represent

text: the

text: degree

text: of

text: similarity

text: between

text: any

text: two

text: subpopulations

text: k,

text: k

text: In

text: kk

text: the

text: special

text: case

text: where

text: W

text: for

text: all

text: k,

text: k

text: the

text: subpopulation

text: similarities

text: are

text: only

text: captured

text: kk

text: by

text: the

text: structure

text: of

text: the

text: graph

text: G.

text: An

text: example

text: of

text: such

text: a

text: subpopulation

text: network

text: is

text: the

text: line

text: graph

text: corresponding

text: to

text: observations

text: over

text: multiple

text: time

text: points,

text: which

text: is

text: used

text: in

text: estimation

text: of

text: ##LTLine##


text: ⊂ { } Ψ(k) = (ψ )p , and Θˆ (k) = (θˆ(k) )p . For a vector x = (x , . . . , x )T and J 1, . . . , p , n n,ij i,j=1 ρn ρn,ij i,j=1 1 p ∈ we denote x = (x , j J)T . For a matrix A, λ (A) is the kth smallest eigenvalue and A(cid:126) J j k ⊂ { } ∈ R × is the vectorization of A. For J (i, j) : i, j = 1, . . . , p and A p p, A(cid:126) is a vector in J R| | ∈ J obtained by removing elements corresponding to (i, j) / J from A(cid:126). A zero-ﬁlled matrix ∈ R × ∈ A p p is obtained from A by replacing a by 0 for (i, j) / J. J ij 8.1 Consistency in Matrix Norms Theorem 1 is a direct consequence of the following result. (cid:26) ∈ (cid:16) (cid:17) (cid:27) Lemma 1. (i) Suppose that Condition 1 holds. Let γ (0, min π ) be arbitrary. For k k ≥ − − { } (cid:107) (cid:107) 2 n max 6γ 1 log p, 21533C2γ 3(1 +(cid:112)4c2)2 max σ(k) 2λ4 1 + ρ L 1/2 s log p 1 1 ii Θ 2 2 k,i √ − − − and ρ = 23 6C (1 + 4c2)γ 1/2 max σ(k) log p/n, we have with probability (1 2K/p)(1 n 1 1 k,i ii − − 2K exp( 2n(min π γ)2)) that k k (cid:114) (cid:88) (cid:16) (cid:17) K (cid:107) − (cid:107) ≤ − (cid:107) (cid:107) s log p Θˆ (k) Θ(k) 215/233/2C γ 3/2(1 + 4c2) max σ(k)λ2 1 + ρ L 1/2 . ρn 0 F 1 1 k,i ii Θ 2 2 n k=1 ≤ (ii) Suppose that Condition 2 holds with p c7nc2, c2, c3, c7 > 0. For ρn = C1Kδn satisfying (cid:113) − (cid:107) (cid:107) ≤ 2432C ρ2γ 2s(1 + ρ L 1/2)2λ4 1/4 1 n 2 2 Θ { } { } − and τ > (27 + 23 1 + 2432c max σ(k) 2)/(9c max σ(k) 2) we have with probability (1 4 k,i ii 4 k,i ii − − 2K exp( 2n(min π γ)2))ν that k k n (cid:88) (cid:16) (cid:17) K (cid:107) − (cid:107) ≤ − (cid:107) (cid:107) Θˆ (k) Θ(k) 2433/2C γ 2K 1 + ρ L 1/2 λ2 s1/2δ , ρn 0 F 1 2 2 Θ n k=1 where 29 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Ψ(k)

text: (ψ

text: )p

text: and

text: Θˆ

text: (k)

text: (θˆ(k)

text: )p

text: For

text: a

text: vector

text: x

text: (x

text: x

text: )T

text: and

text: J

text: p

text: n

text: n,ij

text: ρn

text: ρn,ij

text: p

text: we

text: denote

text: x

text: (x

text: j

text: J)T

text: For

text: a

text: matrix

text: A,

text: λ

text: (A)

text: is

text: the

text: kth

text: smallest

text: eigenvalue

text: and

text: J

text: j

text: k

text: R

text: is

text: the

text: vectorization

text: of

text: A.

text: For

text: J

text: (i,

text: j)

text: i,

text: j

text: p

text: and

text: A

text: p

text: p,

text: is

text: a

text: vector

text: in

text: J

text: R|

text: J

text: obtained

text: by

text: removing

text: elements

text: corresponding

text: to

text: (i,

text: j)

text: J

text: from

text: A

text: zero-ﬁlled

text: matrix

text: R

text: A

text: p

text: p

text: is

text: obtained

text: from

text: A

text: by

text: replacing

text: a

text: by

text: for

text: (i,

text: j)

text: J.

text: J

text: ij

text: Consistency

text: in

text: Matrix

text: Norms

text: Theorem

text: is

text: a

text: direct

text: consequence

text: of

text: the

text: following

text: result.

text: Lemma

text: (i)

text: Suppose

text: that

text: Condition

text: holds.

text: Let

text: γ

text: min

text: π

text: be

text: arbitrary.

text: For

text: k

text: k

text: n

text: max

text: 6γ

text: log

text: p,

text: max

text: σ(k)

text: ρ

text: L

text: s

text: log

text: p

text: ii

text: Θ

text: k,i

text: and

text: ρ

text: max

text: σ(k)

text: log

text: p/n,

text: we

text: have

text: with

text: probability

text: n

text: k,i

text: ii

text: exp(

text: π

text: that

text: k

text: k

text: K

text: s

text: log

text: p

text: Θˆ

text: (k)

text: Θ(k)

text: γ

text: max

text: ρ

text: L

text: ρn

text: F

text: k,i

text: ii

text: Θ

text: n

text: (ii)

text: Suppose

text: that

text: Condition

text: holds

text: with

text: p

text: For

text: ρn

text: satisfying

text: ρ2γ

text: ρ

text: L

text: n

text: Θ

text: and

text: τ

text: max

text: σ(k)

text: max

text: σ(k)

text: we

text: have

text: with

text: probability

text: k,i

text: ii

text: k,i

text: ii

text: exp(

text: π

text: that

text: k

text: k

text: n

text: K

text: Θˆ

text: (k)

text: Θ(k)

text: γ

text: ρ

text: L

text: λ2

text: ρn

text: F

text: Θ

text: n

text: where

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##