  Community partition is an important problem in many areas such as biology
network, social network. The objective of this problem is to analyse the
relationships among data via the network topology. In this paper, we consider
the community partition problem under IC model in social networks. We formulate
the problem as a combinatorial optimization problem which aims at partitioning
a given social network into disjoint M communities. The objective is to
maximize the sum of influence propagation of a social network through
maximizing it within each community. The existing work shows the influence
maximization for community partition problem (IMCPP) to be NP hard. We first
prove that the objective function of IMCPP under IC model is neither submodular
nor supermodular. Then both supermodular upper bound and submodular lower bound
are constructed and proved so that the sandwich framework can be applied. A
continuous greedy algorithm and a discrete implementation are designed for
upper bound and lower bound problems and the algorithm for both of the two
problems gets a 1-1/e approximation ratio. We also devise a simply greedy to
solve the original objective function and apply the sandwich approximation
framework to it to guarantee a data dependent approximation factor. Finally,
our algorithms are evaluated on two real data sets, which clearly verifies the
effectiveness of our method in community partition problem, as well as the
advantage of our method against the other methods.
