In recent years, there has been an increasing interest in the study of large-scale brain activity interaction structure from the perspective of complex networks, based on functional magnetic resonance imaging (fMRI) measurements. To assess the strength of interaction (functional connectivity, FC) between two brain regions, the linear (Pearson) correlation coefficient of the respective time series is most commonly used. Since a potential use of nonlinear FC measures has recently been discussed in this and other fields, the question arises whether particular nonlinear FC measures would be more informative for the graph analysis than linear ones. We present a comparison of network analysis results obtained from the brain connectivity graphs capturing either full (both linear and nonlinear) or only linear connectivity using 24 sessions of human resting-state fMRI. For each session, a matrix of full connectivity between 90 anatomical parcel time series is computed using mutual information. For comparison, connectivity matrices obtained for multivariate linear Gaussian surrogate data that preserve the correlations, but remove any nonlinearity are generated. Binarizing these matrices using multiple thresholds, we generate graphs corresponding to linear and full nonlinear interaction structures. The effect of neglecting nonlinearity is then assessed by comparing the values of a range of graph-theoretical measures evaluated for both types of graphs. Statistical comparisons suggest a potential effect of nonlinearity on the local measures-clustering coefficient and betweenness centrality. Nevertheless, subsequent quantitative comparison shows that the nonlinearity effect is practically negligible when compared to the intersubject variability of the graph measures. Further, on the group-average graph level, the nonlinearity effect is unnoticeable.