Visual search is ubiquitous in daily life and has attracted substantial research interest over the past decades. Although accumulating evidence has suggested complex neurocognitive processes underlying visual search, the neural communication across the brain regions remains poorly understood. The present work aimed to fill this gap by investigating functional networks of fixation-related potential (FRP) during the visual search task. Multi-frequency electroencephalogram (EEG) networks were constructed from 70 university students (male/female = 35/35) using FRPs time-locked to target and non-target fixation onsets, which were determined by concurrent eye-tracking data. Then graph theoretical analysis (GTA) and a data-driven classification framework were employed to quantitatively reveal the divergent reorganization between target and non-target FRPs. We found distinct network architectures between target and non-target mainly in the delta and theta bands. More importantly, we achieved a classification accuracy of 92.74% for target and non-target discrimination using both global and nodal network features. In line with the results of GTA, we found that the integration corresponding to target and non-target FRPs significantly differed, while the nodal features contributing most to classification performance primarily resided in the occipital and parietal-temporal areas. Interestingly, we revealed that females exhibited significantly higher local efficiency in delta band when focusing on the search task. In summary, these results provide some of the first quantitative insights into the underlying brain interaction patterns during the visual search process.