IEEE TRANSACTIONS ON INFORMATION THEORY 5 does very well.However,community detection by spectral Definition 3(Entropy gap):The entropy gap of an undi- algorithms in sparse graphs often fails,because the spectrum rected graph G=(V,E,A)is defined as AH(G)=H1(G)- contains no clear evidence of community structure.This is 孔vm(G) exemplified under the sparse stochastic block model with two The von Neumann graph entropy and the structural informa- clusters of equal size [38],[40],where the second smallest tion are well-defined for all the undirected graphs except for eigenvalue of the adjacency matrix gets lost in the bulk of the graphs with empty edge set,in which vol(G)=0.When uninformative eigenvalues.Our experiments complement the E=,we take it for granted that H1(G)=Hvn(G)=0. correlation between graph spectrum and community structure by showing that the spikes in a sequence of spectral gaps are IV.APPROXIMATION ERROR ANALYSIS good indicators of the community structure. In this section we bound the entropy gap in the undirected The significance and detectability of community structure graphs of order n.Since the nodes with degree 0 have no has found its application in an emerging area called com- contribution to both the structural information and the von munity obfuscation [41]-[47],where the graph structure is Neumann graph entropy,without loss of generality we assume minimally perturbed to protect its community structure from that di>0 for any node iV. being detected.None of these practical algorithms exploit the correlation between graph spectrum and community structure except for the structural entropy proposed by Liu et al.[45]. A.Bounds on the Approximation Error Our work bridges the one-dimensional structural entropy in We first provide bounds on the additive approximation error [45]with the spectral entropy,elaborates both empirically and in Theorem 1,Corollary 1,and Corollary 2,then analyze the theoretically that maximizing the spectral entropy is effective multiplicative approximation error in Theorem 2 in community obfuscation,and thus provides a theoretical Theorem I (Bounds on the absolute approximation error): foundation for the success of the structural entropy [45]. For any undirected graph G=(V,E,A),the inequality III.PRELIMINARIES 0<△H(G)≤1o82e.t(42) (1) 6 vol(G) In this paper,we study the undirected graph G=(V,E,A) holds,where 6=min{dildi>0}is the minimum positive with positive edge weights,where V=[n]{1,...,n} degree. is the node set.E is the edge set and A is the Before proving Theorem 1,we introduce two techniques: symmetric weight matrix with positive entry Aij denoting the the majorization and the Jensen's gap.The former one is weight of an edge (i,j)EE.If the node pair (i,j)E, a preorder of the vector of reals,while the latter is an then Aij=0.If the graph G is unweighted,the weight inverse version of the Jensen's inequality,whose definitions matrix A E(0,1]nxn is called the adjacency matrix of G. are presented as follows. The degree of the node i V in the graph G is defined Definition 4 (Majorization [48]):For a vector x E Rd,we as di= A.The Laplacian matrix of the graph G denote by xERd the vector with the same components,but is defined as L D-A where D=diag(d1,...,dn)is sorted in descending order.Given x,y Rd,we say that x the degree matrix.Let (A:)1 be the sorted eigenvalues of majorizesy(written as x>y)if and only if∑-1≥ L such that0=d≤2≤…≤入n,which is called Laplacian specmm.w demnevoas the ∑=1 for any∈[网and xT1=yr1. Lemma I (Jensen's gap [211):Let X be a one-dimensional volume of graph G,then vol(G)=tr(L)）=∑=1入iwhere random variable with the mean u and the support Let ( tr()is the trace operator.For the convenience of delineation, be a twice differentiable function on and define the function we define a special function f(z)xlog2x on the support h()P-,then Ev(X)】-中(EX])≤ [0,oo)where f(0)limzLo f(x)=0 by convention. suprth()}.var(X).Additionally,if (r)is convex,then In the following,we present the formal definitions of the h(x)is monotonically increasing in x,and if (is concave, von Neumann graph entropy,the structural information,and then h(x)is monotonically decreasing in z. the entropy gap.Slightly different from the one-dimensional Lemma 2:The function f()=xlog2x is convex,its first structural information proposed by Li et al.[3],our definition order derivative f()=log2x+log2e is concave. of structural information does not require the graph G to be Proof:The second order derivative f"(z)=(log2 e)/x> connected. 0,thus f(x)=log2x is convex. Definition I(von Neumann graph entropy):The von Neu- We can see that the majorization characterizes the degree of mann graph entropy of an undirected graph G=(V,E,A) concentration between the two vectors x and y.Specifically. is defined asH(G=-∑=f,/ol(G)》,where0= x>y means that the entries of y are more concentrated on its 入1≤2≤·≤入are the eigenvalues of the Laplacian mean yT1/1T1 than the entires of x.An equivalent definition matrix L=D-A of the graph G,and vol(G)=>=1Ai is of the majorization [48]using linear algebra says that x the volume of G. y if and only if there exists a doubly stochastic matrix P Definition 2 (Structural information):The structural infor- such that Px =y.As a famous example of the majorization, mation of an undirected graph G=(V,E,A)is defined as the Schur-Horn theorem [48]says that the diagonal elements H(G)=->1f(di/vol(G)),where di is the degree of of a positive semidefinite Hermitian matrix are majorized by node i in G and vol(G)=d is the volume of G. its eigenvalues.Since xTLx=(i)Aj()20IEEE TRANSACTIONS ON INFORMATION THEORY 5 does very well. However, community detection by spectral algorithms in sparse graphs often fails, because the spectrum contains no clear evidence of community structure. This is exemplified under the sparse stochastic block model with two clusters of equal size [38], [40], where the second smallest eigenvalue of the adjacency matrix gets lost in the bulk of uninformative eigenvalues. Our experiments complement the correlation between graph spectrum and community structure by showing that the spikes in a sequence of spectral gaps are good indicators of the community structure. The significance and detectability of community structure has found its application in an emerging area called com￾munity obfuscation [41]–[47], where the graph structure is minimally perturbed to protect its community structure from being detected. None of these practical algorithms exploit the correlation between graph spectrum and community structure except for the structural entropy proposed by Liu et al. [45]. Our work bridges the one-dimensional structural entropy in [45] with the spectral entropy, elaborates both empirically and theoretically that maximizing the spectral entropy is effective in community obfuscation, and thus provides a theoretical foundation for the success of the structural entropy [45]. III. PRELIMINARIES In this paper, we study the undirected graph G = (V, E, A) with positive edge weights, where V = [n] , {1, . . . , n} is the node set, E is the edge set, and A ∈ R n×n + is the symmetric weight matrix with positive entry Aij denoting the weight of an edge (i, j) ∈ E. If the node pair (i, j) ∈/ E, then Aij = 0. If the graph G is unweighted, the weight matrix A ∈ {0, 1} n×n is called the adjacency matrix of G. The degree of the node i ∈ V in the graph G is defined as di = Pn j=1 Aij . The Laplacian matrix of the graph G is defined as L , D − A where D = diag(d1, . . . , dn) is the degree matrix. Let {λi} n i=1 be the sorted eigenvalues of L such that 0 = λ1 ≤ λ2 ≤ · · · ≤ λn, which is called Laplacian spectrum. We define vol(G) = Pn i=1 di as the volume of graph G, then vol(G) = tr(L) = Pn i=1 λi where tr(·) is the trace operator. For the convenience of delineation, we define a special function f(x) , x log2 x on the support [0, ∞) where f(0) , limx↓0 f(x) = 0 by convention. In the following, we present the formal definitions of the von Neumann graph entropy, the structural information, and the entropy gap. Slightly different from the one-dimensional structural information proposed by Li et al. [3], our definition of structural information does not require the graph G to be connected. Definition 1 (von Neumann graph entropy): The von Neu￾mann graph entropy of an undirected graph G = (V, E, A) is defined as Hvn(G) = − Pn i=1 f(λi/vol(G)), where 0 = λ1 ≤ λ2 ≤ · · · ≤ λn are the eigenvalues of the Laplacian matrix L = D − A of the graph G, and vol(G) = Pn i=1 λi is the volume of G. Definition 2 (Structural information): The structural infor￾mation of an undirected graph G = (V, E, A) is defined as H1(G) = − Pn i=1 f(di/vol(G)), where di is the degree of node i in G and vol(G) = Pn i=1 di is the volume of G. Definition 3 (Entropy gap): The entropy gap of an undi￾rected graph G = (V, E, A) is defined as ∆H(G) = H1(G)− Hvn(G). The von Neumann graph entropy and the structural informa￾tion are well-defined for all the undirected graphs except for the graphs with empty edge set, in which vol(G) = 0. When E = ∅, we take it for granted that H1(G) = Hvn(G) = 0. IV. APPROXIMATION ERROR ANALYSIS In this section we bound the entropy gap in the undirected graphs of order n. Since the nodes with degree 0 have no contribution to both the structural information and the von Neumann graph entropy, without loss of generality we assume that di > 0 for any node i ∈ V . A. Bounds on the Approximation Error We first provide bounds on the additive approximation error in Theorem 1, Corollary 1, and Corollary 2, then analyze the multiplicative approximation error in Theorem 2. Theorem 1 (Bounds on the absolute approximation error): For any undirected graph G = (V, E, A), the inequality 0 < ∆H(G) ≤ log2 e δ · tr(A2 ) vol(G) (1) holds, where δ = min{di |di > 0} is the minimum positive degree. Before proving Theorem 1, we introduce two techniques: the majorization and the Jensen’s gap. The former one is a preorder of the vector of reals, while the latter is an inverse version of the Jensen’s inequality, whose definitions are presented as follows. Definition 4 (Majorization [48]): For a vector x ∈ R d , we denote by x ↓ ∈ R d the vector with the same components, but sorted in descending order. Given x, y ∈ R d , we say that x majorizes y (written as x  y) if and only if Pk i=1 x ↓ i ≥ Pk i=1 y ↓ i for any k ∈ [d] and x |1 = y |1. Lemma 1 (Jensen’s gap [21]): Let X be a one-dimensional random variable with the mean µ and the support Ω. Let ψ(x) be a twice differentiable function on Ω and define the function h(x) , ψ(x)−ψ(µ) (x−µ) 2 − ψ 0 (µ) x−µ , then E[ψ(X)] − ψ(E[X]) ≤ supx∈Ω{h(x)}· var(X). Additionally, if ψ 0 (x) is convex, then h(x) is monotonically increasing in x, and if ψ 0 (x) is concave, then h(x) is monotonically decreasing in x. Lemma 2: The function f(x) = x log2 x is convex, its first order derivative f 0 (x) = log2 x + log2 e is concave. Proof: The second order derivative f 00(x) = (log2 e)/x > 0, thus f(x) = x log2 x is convex. We can see that the majorization characterizes the degree of concentration between the two vectors x and y. Specifically, x  y means that the entries of y are more concentrated on its mean y |1/1 |1 than the entires of x. An equivalent definition of the majorization [48] using linear algebra says that x  y if and only if there exists a doubly stochastic matrix P such that Px = y. As a famous example of the majorization, the Schur-Horn theorem [48] says that the diagonal elements of a positive semidefinite Hermitian matrix are majorized by its eigenvalues. Since x TLx = P (i,j)∈E Aij (xi − xj ) 2 ≥ 0