Source author record

Enqiang Zhu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Social and Information Networks

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

PHEE: A phased hybrid evaluation-enhanced approach for identifying influential users in social networks

For the purpose of maximizing the spread of influence caused by a certain small number k of nodes in a social network, we are asked to find a k-subset of nodes (i.e., a seed set) with the best capacity to influence the nodes not in it. This problem of influence maximization (IM) has wide application, belongs to subset problems, and is NP-hard. To solve it, we should theoretically examine all seed sets and evaluate their influence spreads, which is time-consuming. Therefore, metaheuristic strategies are generally employed to gain a good seed set within a reasonable time. We observe that many algorithms for the IM problem only adopt a uniform mechanism in the whole solution search process, which lacks a response measure when the algorithm becomes trapped in a local optimum. To address this issue, we propose a phased hybrid evaluation-enhanced (PHEE) approach for IM, which utilizes two distinct search strategies to enhance the search of optimal solutions: a randomized range division evolutionary (RandRDE) algorithm to improve the solution quality, and a fast convergence strategy. Our approach is evaluated on 10 real-world social networks of different sizes and types. Experimental results demonstrate that our algorithm is efficient and obtains the best influence spread for all the datasets compared with three state-of-the-art algorithms, outperforms the time consuming CELF algorithm on four datasets, and performs worse than CELF on only two networks.

preprint2015arXiv

On uniquely 3-colorable plane graphs without prescribed adjacent faces

A graph $G$ is \emph{uniquely k-colorable} if the chromatic number of $G$ is $k$ and $G$ has only one $k$ -coloring up to permutation of the colors. For a plane graph $G$ , two faces $f_1$ and $f_2$ of $G$ are \emph{adjacent $(i,j)$ -faces} if $d(f_1)=i$ , $d(f_2)=j$ and $f_1$ and $f_2$ have a common edge, where $d(f)$ is the degree of a face $f$ . In this paper, we prove that every uniquely 3-colorable plane graph has adjacent $(3,k)$ -faces, where $k\leq 5$ . The bound 5 for $k$ is best possible. Furthermore, we prove that there exist a class of uniquely 3-colorable plane graphs having neither adjacent $(3,i)$ -faces nor adjacent $(3,j)$ -faces, where $i,j\in \{3,4,5\}$ and $i \neq j$ . One of our constructions implies that there exist an infinite family of edge-critical uniquely 3-colorable plane graphs with $n$ vertices and $\frac{7}{3}n-\frac{14}{3}$ edges, where $n(\geq 11)$ is odd and $n\equiv 2\pmod{3}$ .

preprint2014arXiv

Tree-colorable maximal planar graphs

A tree-coloring of a maximal planar graph is a proper vertex $4$ -coloring such that every bichromatic subgraph, induced by this coloring, is a tree. A maximal planar graph $G$ is tree-colorable if $G$ has a tree-coloring. In this article, we prove that a tree-colorable maximal planar graph $G$ with $δ(G)\geq 4$ contains at least four odd-vertices. Moreover, for a tree-colorable maximal planar graph of minimum degree 4 that contains exactly four odd-vertices, we show that the subgraph induced by its four odd-vertices is not a claw and contains no triangles.

preprint2013arXiv

Size of edge-critical uniquely 3-colorable planar graphs

A graph $G$ is \emph{uniquely k-colorable} if the chromatic number of $G$ is $k$ and $G$ has only one $k$ -coloring up to permutation of the colors. A uniquely $k$ -colorable graph $G$ is edge-critical if $G-e$ is not a uniquely $k$ -colorable graph for any edge $e\in E(G)$ . Mel'nikov and Steinberg [L. S. Mel'nikov, R. Steinberg, One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977) 203-206] asked to find an exact upper bound for the number of edges in a edge-critical 3-colorable planar graph with $n$ vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if $G$ is such a graph with $n(\geq6)$ vertices, then $|E(G)|\leq \frac{5}{2}n-6$ , which improves the upper bound $\frac{8}{3}n-\frac{17}{3}$ given by Matsumoto [N. Matsumoto, The size of edge-critical uniquely 3-colorable planar graphs, Electron. J. Combin. 20 (3) (2013) $\#$ P49]. Furthermore, we find some edge-critical 3-colorable planar graphs which have $n(=10,12, 14)$ vertices and $\frac{5}{2}n-7$ edges.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.