what-when-how
In Depth Tutorials and Information
4.5 ConclusionandFutureWork
he focus of the first part of our paper was the development of a spectrum-based
framework characterizing graph nonrandomness at various levels. We first pro-
posed a novel measure to characterize edge nonrandomness using the spectral
coordinates of two connected nodes projected in
k
-dimensional spectral space. We
then characterized node nonrandomness based on the nonrandomness of edges
connected to this node, and graph nonrandomness based on the nonrandomness
of all edges within the graph. All nonrandomness measures are simple numeri-
cal indices that can be derived elegantly from the graph spectrum. We studied
several real-world social networks for which our nonrandomness measures dis-
play useful and desirable properties. We also show that nonrandomness measures
have different distributions between real-world networks and random graphs. In
the future, we will explore how different choices of
k
affect graph nonrandom-
ness. Second, we will investigate in full the relationship between our proposed
nonrandomness measures (especially graph nonrandomness) with traditional
measures. Traditional measures such as modularity can also be used to mea-
sure community structural property. It is interesting to compare our measures
with traditional ones and explore how to apply the proposed nonrandomness
framework to solve practical problems such as graph partition. We will consider
computational complexity issues when extremely large networks are available.
Finally, we will explore how to extend our framework to directed and weighted
graphs.
In the second part of this paper, we have developed one spectrum-preserving
randomization approach that can significantly improve edge-based graph random-
ization methods (
RandAdd/Del
and
RandSwitch
) by increasing the utility of the
perturbed graph. We have also given a loose bound of the graph spectrum changes
for pure randomization strategies (i.e., reallocating or switching edges randomly).
Since the graph spectrum is closely related to many real-graph characteristics, this
bound provides a perspective on the extent to which edge randomization affects the
graph structure. In the future, we are interested in deriving some (tight) bound of
graph spectrum changes for spectrum-preserving randomization strategies. We will
also investigate the intermediate eigenvalue problem, aiming to derive conditions
to adjust any eigenvalue (in addition to
λ
1
and
μ
2
) that may indicate a certain struc-
ture character of the graph. Finally, we will investigate thoroughly how spectrum-
preserving randomization strategies protect link privacy.
Acknowledgments
his work was supported in part by U.S. National Science Foundation IIS-0546027
and CNS-0831204. Partial results have been published in two papers [40, 43].
