
While influence maximization in social networks has been studied extensively
in computer science community for the last decade the focus has been on the
progressive influence models, such as independent cascade (IC) and Linear
threshold (LT) models, which cannot capture the reversibility of choices. In
this paper, we present the Heat Conduction (HC) model which is a
nonprogressive influence model with realworld interpretations. We show that
HC unifies, generalizes, and extends the existing nonprogressive models, such
as the Voter model [1] and nonprogressive LT [2]. We then prove that selecting
the optimal seed set of influential nodes is NPhard for HC but by establishing
the submodularity of influence spread, we can tackle the influence maximization
problem with a scalable and provably nearoptimal greedy algorithm. We are the
first to present a scalable solution for influence maximization under
nonprogressive LT model, as a special case of the HC model. In sharp contrast
to the other greedy influence maximization methods, our fast and efficient
C2GREEDY algorithm benefits from two analytically computable steps: closedform
computation for finding the influence spread as well as the greedy seed
selection. Through extensive experiments on several large real and synthetic
networks, we show that C2GREEDY outperforms the stateoftheart methods, in
terms of both influence spread and scalability.

We first present a comprehensive review of various random walk metrics used
in the literature and express them in a consistent framework. We then introduce
fundamental tensor  a generalization of the wellknown fundamental matrix 
and show that classical random walk metrics can be derived from it in a unified
manner. We provide a collection of useful relations for random walk metrics
that are useful and insightful for network studies. To demonstrate the
usefulness and efficacy of the proposed fundamental tensor in network analysis,
we present four important applications: 1) unification of network centrality
measures, 2) characterization of (generalized) network articulation points, 3)
identification of network most influential nodes, and 4) fast computation of
network reachability after failures.

Directed links  representing asymmetric social ties or interactions (e.g.,
"followerfollowee")  arise naturally in many social networks and other
complex networks, giving rise to directed graphs (or digraphs) as basic
topological models for these networks. Reciprocity, defined for a digraph as
the percentage of edges with a reciprocal edge, is a key metric that has been
used in the literature to compare different directed networks and provide
"hints" about their structural properties: for example, are reciprocal edges
generated randomly by chance or are there other processes driving their
generation? In this paper we study the problem of maximizing achievable
reciprocity for an ensemble of digraphs with the same prescribed in and
outdegree sequences. We show that the maximum reciprocity hinges crucially on
the in and outdegree sequences, which may be intuitively interpreted as
constraints on some "social capacities" of nodes and impose fundamental limits
on achievable reciprocity. We show that it is NPcomplete to decide the
achievability of a simple upper bound on maximum reciprocity, and provide
conditions for achieving it. We demonstrate that many real networks exhibit
reciprocities surprisingly close to the upper bound, which implies that users
in these social networks are in a sense more "social" than suggested by the
empirical reciprocity alone in that they are more willing to reciprocate,
subject to their "social capacity" constraints. We find some surprising linear
relationships between empirical reciprocity and the bound. We also show that a
particular type of small network motifs that we call 3paths are the major
source of loss in reciprocity for real networks.

A divideandconquer based approach for computing the MoorePenrose
pseudoinverse of the combinatorial Laplacian matrix $(\bb L^+)$ of a simple,
undirected graph is proposed. % The nature of the underlying subproblems is
studied in detail by means of an elegant interplay between $\bb L^+$ and the
effective resistance distance $(\Omega)$. Closed forms are provided for a novel
{\em twostage} process that helps compute the pseudoinverse incrementally.
Analogous scalar forms are obtained for the converse case, that of structural
regress, which entails the breaking up of a graph into disjoint components
through successive edge deletions. The scalar forms in both cases, show
absolute elementwise independence at all stages, thus suggesting potential
parallelizability. Analytical and experimental results are presented for
dynamic (timeevolving) graphs as well as large graphs in general (representing
realworld networks). An order of magnitude reduction in computational time is
achieved for dynamic graphs; while in the general case, our approach performs
better in practice than the standard methods, even though the worst case
theoretical complexities may remain the same: an important contribution with
consequences to the study of online social networks.

Influence diffusion and influence maximization in largescale online social
networks (OSNs) have been extensively studied, because of their impacts on
enabling effective online viral marketing. Existing studies focus on social
networks with only friendship relations, whereas the foe or enemy relations
that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely
ignored. In this paper, we make the first attempt to investigate the influence
diffusion and influence maximization in OSNs with both friend and foe
relations, which are modeled using positive and negative edges on signed
networks. In particular, we extend the classic voter model to signed networks
and analyze the dynamics of influence diffusion of two opposite opinions. We
first provide systematic characterization of both shortterm and longterm
dynamics of influence diffusion in this model, and illustrate that the steady
state behaviors of the dynamics depend on three types of graph structures,
which we refer to as balanced graphs, antibalanced graphs, and strictly
unbalanced graphs. We then apply our results to solve the influence
maximization problem and develop efficient algorithms to select initial seeds
of one opinion that maximize either its shortterm influence coverage or
longterm steady state influence coverage. Extensive simulation results on both
synthetic and realworld networks, such as Epinions and Slashdot, confirm our
theoretical analysis on influence diffusion dynamics, and demonstrate the
efficacy of our influence maximization algorithm over other heuristic
algorithms.

We explore the geometry of complex networks in terms of an ndimensional
Euclidean embedding represented by the MoorePenrose pseudoinverse of the
graph Laplacian $(\bb L^+)$. The squared distance of a node $i$ to the origin
in this ndimensional space $(l^+_{ii})$, yields a topological centrality index
$(\mathcal{C}^{*}(i) = 1/l^+_{ii})$ for node $i$. In turn, the sum of
reciprocals of individual node structural centralities,
$\sum_{i}1/\mathcal{C}^*(i) = \sum_{i} l^+_{ii}$, i.e. the trace of $\bb L^+$,
yields the wellknown Kirchhoff index $(\mathcal{K})$, an overall structural
descriptor for the network. In addition to this geometric interpretation, we
provide alternative interpretations of the proposed indices to reveal their
true topological characteristics: first, in terms of forced detour overheads
and frequency of recurrences in random walks that has an interesting analogy to
voltage distributions in the equivalent electrical network; and then as the
average connectedness of $i$ in all the bipartitions of the graph. These
interpretations respectively help establish the topological centrality
$(\mathcal{C}^{*}(i))$ of node $i$ as a measure of its overall position as well
as its overall connectedness in the network; thus reflecting the robustness of
node $i$ to random multiple edge failures. Through empirical evaluations using
synthetic and real world networks, we demonstrate how the topological
centrality is better able to distinguish nodes in terms of their structural
roles in the network and, along with Kirchhoff index, is appropriately
sensitive to perturbations/rewirings in the network.

Many social networks, e.g., Slashdot and Twitter, can be represented as
directed graphs (digraphs) with two types of links between entities: mutual
(bidirectional) and oneway (unidirectional) connections. Social science
theories reveal that mutual connections are more stable than oneway
connections, and oneway connections exhibit various tendencies to become
mutual connections. It is therefore important to take such tendencies into
account when performing clustering of social networks with both mutual and
oneway connections.
In this paper, we utilize the dyadic methods to analyze social networks, and
develop a generalized mutuality tendency theory to capture the tendencies of
those node pairs which tend to establish mutual connections more frequently
than those occur by chance. Using these results, we develop a
mutualitytendencyaware spectral clustering algorithm to identify more stable
clusters by maximizing the withincluster mutuality tendency and minimizing the
crosscluster mutuality tendency. Extensive simulation results on synthetic
datasets as well as real online social network datasets such as Slashdot,
demonstrate that our proposed mutualitytendencyaware spectral clustering
algorithm extracts more stable social community structures than traditional
spectral clustering methods.