# Visual Orbits & Alignments of Planet Hosting Binary Systems

Kathryn V. Lester NASA Ames Research Center, Moffett Field, CA 94035, USA
Steve B. Howell NASA Ames Research Center, Moffett Field, CA 94035, USA
Rachel A. Matson U.S. Naval Observatory, Washington, D.C. 20392, USA  Elise
Furlan NASA Exoplanet Science Institute, Caltech/IPAC, Pasadena, CA 91125, USA
Crystal L. Gnilka NASA Ames Research Center, Moffett Field, CA 94035, USA
Colin Littlefield NASA Ames Research Center, Moffett Field, CA 94035, USA  Bay
Area Environmental Research Institute, Moffett Field, CA 94035, USA  David R.
Ciardi NASA Exoplanet Science Institute, Caltech/IPAC, Pasadena, CA 91125, USA
Mark E. Everett NSF’s National Optical-Infrared Astronomy Research Laboratory,
Tucson, AZ 85719, USA  Sergio B. Fajardo-Acosta Caltech/IPAC, Pasadena, CA
91125  Catherine A. Clark NASA Exoplanet Science Institute, Caltech/IPAC,
Pasadena, CA 91125, USA  Jet Propulsion Laboratory, California Institute of
Technology, Pasadena, CA 91109 USA

(Accepted in The Astronomical Journal)

###### Abstract

Roughly half of Solar-type planet hosts have stellar companions, so
understanding how these binary companions affect the formation and evolution
of planets is an important component to understanding planetary systems
overall. Measuring the dynamical properties of planet host binaries enables a
valuable test of planet formation in multi-star systems and requires knowledge
of the binary orbital parameters. Using high resolution imaging, we have
measured the relative astrometry and visual orbits of 13 binary systems where
one of the stars is known to host a transiting exoplanet. Our results indicate
that the mutual inclination between the orbits of the binary hosts and the
transiting planets are well aligned. Our results for close binary systems
($a<100$ AU) complement past work for wide planet host binaries from Gaia.

††facilities: Gemini North (‘Alopeke), Gemini South (Zorro), WIYN (NESSI)

##  1 Introduction

Multi-star systems make up about 50% of Solar-type stars (Raghavan et al.,
2010) and 25% of M-type stars (Winters et al., 2019a) in the Solar
neighborhood. Recent work has shown that the fraction of planet hosting stars
with stellar companions is similar to that of field binaries (Horch et al.,
2014; Matson et al., 2018; Clark et al., 2022), so understanding how stellar
companions affect the formation and evolution of exoplanets is an important
component to understanding planetary systems overall. Observational radial
velocity surveys and transit detections for exoplanets both have biases
against the study of binary star systems and their planets; radial velocity
studies often avoid known binaries due to contamination from the companion’s
spectral lines (e.g., Chontos et al., 2022), while transit studies often miss
terrestrial-size planets when flux dilution from stellar companions causes a
transit to become shallower than the detectability of the survey (Lester et
al., 2021). Therefore, our knowledge of planetary architectures,
characteristics, and occurrence rates is biased toward single-star systems,
despite the fact that a significant fraction of binary systems are likely to
host exoplanets.

Theoretical studies show that a close stellar companion can impact planets
through the truncation or misalignment of the protoplanetary disk (Artymowicz
& Lubow, 1994; Kraus et al., 2012; Martin et al., 2014), the formation and
migration of gas giant planets (Dawson & Johnson, 2018; Fontanive et al.,
2019), and the scattering of planets in unstable triple star systems (Thebault
& Haghighipour, 2015). For example, recent simulations of protoplanetary disks
around the primary star in wide binary systems (with separations $a=100-400$
AU) often result in the disk fragmentation needed to form giant planets
(Cadman et al., 2022). Modeling also predicts that the shape and size of the
companion’s orbit can play a significant role in planet formation, such that
close, eccentric, or highly inclined companions could hinder planet formation
(Holman & Wiegert, 1999; Quintana et al., 2002; Jang-Condell, 2015; Cadman et
al., 2022).

Over the past decade, observational evidence has accumulated to indicate that
planet formation is suppressed in close ($a<100$ AU) binary systems. First,
high resolution imaging surveys of known transiting planet host stars from
Kepler, K2, and TESS have found a dearth of close stellar companions (Bergfors
et al., 2013; Wang et al., 2014a; Kraus et al., 2016; Fontanive et al., 2019;
Moe & Kratter, 2021; Lester et al., 2021; Fontanive & Bardalez Gagliuffi,
2021). Next, when searching for planets in binary systems, the frequency of
giant planets in close binaries was found to be significantly less than the
frequency in wide ($a>$100 AU) binaries (Wang et al., 2014b; Hirsch et al.,
2021). Su et al. (2021) also found that multi-planet systems are more often
found in wide binaries. Furthermore, observations of young binaries show that
protoplanetary disks are smaller and less massive in binaries than around
single stars (Zurlo et al., 2021), suggesting that stellar companions within
about 300 AU often truncate the protoplanetary disks (Harris et al., 2012).
However, the detection of planets in systems with close companions (e.g.,
Hatzes et al., 2003; Dupuy et al., 2016; Winters et al., 2019b) demonstrates
it is possible for planets to form in such systems, so it is currently unclear
why some close binaries are able to host planets and which factors influence
the survival of the planet.

Little observational evidence exists to test how the other binary orbital
parameters (such as inclination and eccentricity) affect planet formation,
primarily due to the high angular resolution and long time baselines required
to measure the binary orbits. Several recent papers (Dupuy et al., 2022;
Behmard et al., 2022; Christian et al., 2022) began probing the mutual
inclination between transiting planets and stellar companions and found that
the orbital planes of the host binaries are often well aligned with the
planetary orbits. For example, Christian et al. (2022) studied wide binaries
from Gaia that likely formed through turbulent fragmentation, which results in
protoplanetary disks randomly aligned with the stellar companion (Offner et
al., 2010). They concluded that subsequent gravitational interactions with a
close companion could re-align the protoplanetary disk and produce the
observed alignments.

Long term observational monitoring of planet host binaries is necessary to
determine how host multiplicity and binary orbital properties influence planet
formation. For this purpose, we present the first results from our astrometric
monitoring campaign of planet host binaries. In this paper, we explore the
mutual orbital alignment of close binary systems ($a<100$ AU) known to host at
least one transiting planet, in order to help characterize the architectures
of binary sytems with planets and help place constraints on the formation and
evolutionary models. We present orbital inclinations and preliminary visual
orbits of 13 binaries hosting circumstellar (S-type) planets to test if these
systems also show planet-binary alignment. We describe our sample and
observations in Sections 2 and 3, our visual orbit analysis in Section 4,
planet-binary alignment results in Section 5, and our conclusions in Section
6.

##  2 Sample

Table 1: Sample of Planet Host Binaries

Target | TIC ID |  $T_{\rm eff~{}A}$ (K) |  $T_{\rm eff~{}B}$ (K) | $q$ |  $M_{tot}$ ($M_{\odot}$) |  $\pi$ (mas) |  $\mu_{RA}$ (mas/yr) |  $\mu_{DEC}$ (mas/yr) | Reference
---|---|---|---|---|---|---|---|---|---
KOI 270 | 270779644 | 5650 | 5340 | 0.90 | 1.90 | $3.84\pm 0.05$ | $-9.40\pm 0.01$ | $-44.40\pm 0.01$ | 1,3
KOI 307 | 138097531 | 6000 | 5800 | 0.95 | 2.16 | $1.27\pm 0.11$ | $-4.10\pm 0.12$ | $-3.88\pm 0.12$ | 1,2
KOI 1613 | 120576846 | 6080 | 5340 | 0.75 | 2.10 | $2.03\pm 0.50$ | $-18.78\pm 0.54$ | $-20.46\pm 0.58$ | 1,2,3
KOI 1961 | 158552426 | 5350 | 5140 | 0.89 | 1.70 | $2.47\pm 0.03$ | $1.13\pm 0.03$ | $-22.97\pm 0.03$ | 3
KOI 2124 | 27457135 | 4060 | 3300 | 0.50 | 0.90 | $3.33\pm 0.04$ | $-12.85\pm 0.06$ | $-18.33\pm 0.06$ | 1,3
KOI 3234 | 164525743 | 6350 | 6000 | 0.83 | 2.44 | $1.55\pm 0.06$ | $-3.24\pm 0.07$ | $-10.63\pm 0.08$ | 1
KOI 3456 | 137408775 | 5600 | 5500 | 0.98 | 1.92 | $2.05\pm 0.04$ | $6.32\pm 0.04$ | $0.41\pm 0.05$ | 1
KOI 4252 | 158489110 | 3930 | 4000 | 0.83 | 1.10 | $5.08\pm 0.02$ | $4.41\pm 0.03$ | $25.69\pm 0.03$ | 3
KOI 5971 | 27778479 | 4620 | 4300 | 0.94 | 1.36 | $2.52\pm 0.02$ | $9.27\pm 0.03$ | $28.23\pm 0.03$ | 1
TOI 271 | 259511357 | 6110 | 3800 | 0.47 | 1.68 | $10.01\pm 0.13$ | $46.72\pm 0.15$ | $49.46\pm 0.17$ | 4
TOI 1287 | 352764091 | 5890 | 4500 | 0.71 | 1.80 | $10.76\pm 0.03$ | $33.87\pm 0.02$ | $-88.51\pm 0.02$ | 4,5
EPIC 212303338 | 422290347 | 5100 | 4410 | 0.79 | 1.54 | $12.48\pm 0.09$ | $31.54\pm 0.10$ | $10.40\pm 0.06$ | 6
EPIC 220555384 | 406410648 | 4160 | 4330 | 0.93 | 1.37 | $6.85\pm 0.51$ | $28.90\pm 1.45$ | $-24.37\pm 1.22$ | 6

References. — 1\. Furlan et al. (2017), 2\. Colton et al. (2021) 3\. Dupuy et
al. (2022), 4\. Lester et al. (2021), 5\. Howell et al. (2021), 6\. Matson et
al. (2018).

Table 2: Estimated Planet Properties

Planet |  $P_{pl}$ (days) |  $R_{pl}$ ($R_{\oplus}$) |  $a_{pl}$ (AU) | Designation**We note whether each planet is listed on the NASA Exoplanet Archive as a confirmed planet (CP) or planet candidate. | Reference
---|---|---|---|---|---
KOI 270.01 | 12.6 | 1.53 | 0.10 | CP (Kepler-449 b) | 1,2
KOI 270.02 | 33.7 | 1.86 | 0.20 | CP (Kepler-449 c) | 1,2
KOI 307.01 | 19.7 | 1.78 | 0.14 | CP (Kepler-520 b) | 1,3
KOI 307.02 | 5.2 | 1.18 | 0.06 | CP (Kepler-520 c) | 1,3
KOI 1613.01 | 15.9 | 1.31 | 0.12 | CP (Kepler-907 b) | 1,3
KOI 1613.02 | 20.6 | 0.85 | 0.15 | Candidate | 4
KOI 1613.03 | 94.1 | 0.90 | 0.40 | Candidate | 4
KOI 1961.01 | 1.9 | 0.91 | 0.03 | CP (Kepler-1027 b) | 1,3
KOI 2124.01 | 42.3 | 1.45 | 0.20 | Candidate | 4
KOI 3234.01 | 2.4 | 0.83 | 0.04 | CP (Kepler-1443 b) | 3,4
KOI 3456.01 | 30.9 | 1.08 | 0.19 | CP (Kepler-1505 b) | 3,4
KOI 3456.02 | 486.1 | 1.18 | 1.20 | Candidate | 5
KOI 4252.01 | 15.6 | 0.72 | 0.10 | CP (Kepler-1948 b) | 4,6
KOI 5971.01 | 493.3 | 1.08 | 1.00 | Candidate | 5
TOI 271.01 | 2.5 | 2.81 | 0.04 | Candidate | 7
TOI 1287.01 | 9.6 | 2.52 | 0.09 | Candidate | 7
EPIC 212303338.01 | 0.6 | 0.58 | 0.01 | Candidate | 8,9
EPIC 220555384.01 | 4.3 | 1.20 | 0.05 | Candidate | 8,10

References. — 1\. Batalha et al. (2013), 2. Van Eylen & Albrecht (2015), 3\.
Morton et al. (2016), 4\. Rowe et al. (2015), 5. Mullally et al. (2015), 6.
Valizadegan et al. (2022), 7\. Guerrero et al. (2021), 8\. Huber et al.
(2016), 9\. Kostov et al. (2019), 10\. Kruse et al. (2019).

We started building our sample from transiting planet host stars from Kepler,
K2, and TESS for which close stellar companions were previously detected using
speckle interferometry (Furlan et al., 2017; Matson et al., 2018; Ziegler et
al., 2020; Howell et al., 2021; Lester et al., 2021). For each binary, we
estimated the projected physical separation using the projected angular
separation from the most recent speckle epoch and the Gaia DR3 parallax (Gaia
Collaboration et al., 2016, 2022). We then kept only those with projected
separations less than 100 AU, where stellar companions are most likely to
impact planet formation. Transit false positive systems identified by follow-
up photometry as listed on the Exoplanet Follow-up Observing Program (ExoFOP)
website were also removed. Our full sample contains 40 binaries, for which we
are conducting an on-going astrometric and spectroscopic monitoring campaign
with the Gemini, WIYN, and Keck telescopes. With angular separations less than
1 arcsec, these systems are expected to be gravitationally bound (Everett et
al., 2015; Hirsch et al., 2017; Matson et al., 2018) but we confirm the bound
nature of each system in Section 4.

We present preliminary visual orbit solutions for 13 of the exoplanet host
binaries in our sample, for which orbital motion can already be seen. These
systems are listed in Table 2 with their TIC ID, primary star effective
temperature ($T_{\rm eff~{}A}$) from the TIC catalog, estimates of the
secondary star effective temperature ($T_{\rm eff~{}B}$), binary mass ratio
($q$) and total system mass ($M_{tot}$) from the magnitude difference (see
Section 4), Gaia DR3 parallax ($\pi$) and proper motion ($\mu$), and companion
detection reference. We list the planet properties in Table 2, including the
planet name, period ($P_{pl}$), radius ($R_{pl}$, uncorrected for flux
dilution) and semi-major axis ($a_{pl}$) from the KOI/EPIC/TOI catalogs,
whether each planet is designated on the NASA Exoplanet Archive as a planet
candidate or confirmed planet (CP), and literature reference. Most of the
binaries discussed herein are Kepler targets due to the long observational
baselines available, and therefore Table 2 contains mainly Solar-type stars
with Earth-sized planets. Four systems have multiple planets/planet
candidates, so we list the estimated properties of each one.

Figure 1: Power spectra and relative astrometric solution for KOI 4252 on 2021 Oct 24. The top panel shows the observed binary power spectrum (left), the best-fit model (center), and the residuals (right). The bottom left plot shows the full reconsructed image from the speckle pipeline, which often has a reflected image of the companion. The bottom right plot shows a close-in view of the $\chi^{2}$ values around the best-fit solution, where the best-fit position of the companion is marked with an X. The 1-, 2-, and 3-$\sigma~{}\chi^{2}$ contour levels (corresponding to $\chi^{2}_{min}+1,~{}\chi^{2}_{min}+4,~{}\chi^{2}_{min}+9$) are shown in black.  Table 3: New Relative Astrometry from Speckle Interferometry  Target | UT Date | MJD |  $\rho$ (mas) |  $\theta$ (deg) |  $\Delta m$ (mag) | Filter | Telescope
---|---|---|---|---|---|---|---
KOI 270 | 2022-09-16 | 59836.30 | $186.0\pm 1.6$ | $65.0\pm 0.6$ | $0.6\pm 0.5$ | $i^{\prime}$ | WIYN
KOI 1613 | 2022-09-19 | 59836.21 | $191.5\pm 4.0$ | $185.3\pm 0.6$ | $1.2\pm 0.5$ | $i^{\prime}$ | WIYN
KOI 1961 | 2021-06-24 | 59389.47 | $46.8\pm 2.0$ | $275.2\pm 2.4$ | $0.2\pm 0.4$ | 832 nm | Gemini
KOI 1961 | 2021-10-15 | 59502.25 | $44.9\pm 2.5$ | $276.7\pm 3.8$ | $0.0\pm 0.5$ | 832 nm | Gemini
KOI 1961 | 2022-05-10 | 59709.55 | $47.0\pm 3.5$ | $277.6\pm 3.7$ | $0.4\pm 0.3$ | 832 nm | Gemini
KOI 2124 | 2021-06-26 | 59391.53 | $79.5\pm 3.3$ | $53.3\pm 2.3$ | $0.3\pm 0.4$ | 832 nm | Gemini
KOI 2124 | 2021-10-19 | 59506.26 | $78.1\pm 2.5$ | $53.5\pm 1.8$ | $0.2\pm 0.3$ | 832 nm | Gemini
KOI 2124 | 2022-05-09 | 59708.61 | $80.9\pm 5.2$ | $53.2\pm 3.8$ | $0.5\pm 0.4$ | 832 nm | Gemini
KOI 3234 | 2022-09-14 | 59836.77 | $70.5\pm 5.0$ | $158.6\pm 3.0$ | $0.9\pm 0.5$ | $z^{\prime}$ | WIYN
KOI 3456 | 2022-09-12 | 59834.28 | $50.8\pm 3.5$ | $11.9\pm 3.9$ | $0.0\pm 1.3$ | 832 nm | Gemini
KOI 4252 | 2021-06-25 | 59390.50 | $67.7\pm 2.5$ | $325.3\pm 2.1$ | $0.6\pm 0.2$ | 832 nm | Gemini
KOI 4252 | 2021-10-24 | 59511.21 | $69.1\pm 4.2$ | $325.0\pm 3.6$ | $0.8\pm 0.2$ | 832 nm | Gemini
KOI 4252 | 2022-05-09 | 59708.55 | $70.3\pm 4.5$ | $323.7\pm 3.7$ | $0.8\pm 0.2$ | 832 nm | Gemini
KOI 4252 | 2022-09-12 | 59834.28 | $72.9\pm 3.5$ | $323.2\pm 2.7$ | $0.5\pm 0.2$ | 832 nm | Gemini
KOI 5971 | 2021-06-28 | 59393.50 | $29.9\pm 4.5$ | $128.0\pm 8.6$ | $1.0\pm 0.9$ | 832 nm | Gemini
KOI 5971 | 2021-10-21 | 59508.25 | $29.9\pm 3.3$ | $128.0\pm 6.1$ | $0.8\pm 0.5$ | 832 nm | Gemini
KOI 5971 | 2022-05-11 | 59710.56 | $26.9\pm 5.7$ | $130.2\pm 12.3$ | $0.8\pm 1.0$ | 832 nm | Gemini
TOI 271 | 2021-09-18 | 59840.77 | $153.0\pm 5.0$ | $226.8\pm 2.0$ | $5.1\pm 1.0$ | 832 nm | Gemini
TOI 1287 | 2021-06-24 | 59389.54 | $131.5\pm 9.0$ | $346.4\pm 3.9$ | $3.2\pm 0.5$ | 832 nm | Gemini
TOI 1287 | 2021-10-23 | 59510.24 | $135.8\pm 10.1$ | $346.0\pm 4.6$ | $3.3\pm 0.6$ | 832 nm | Gemini
TOI 1287 | 2022-05-11 | 59710.58 | $144.7\pm 11.1$ | $346.4\pm 4.7$ | $3.3\pm 0.7$ | 832 nm | Gemini
TOI 1287 | 2022-09-18 | 59840.51 | $147.0\pm 10.0$ | $349.4\pm 5.0$ | $2.7\pm 1.0$ | $z^{\prime}$ | WIYN
EPIC 212303338 | 2023-01-28 | 59971.50 | $124.0\pm 5.0$ | $100.4\pm 2.0$ | $1.8\pm 0.5$ | $z^{\prime}$ | WIYN
EPIC 220555384 | 2021-10-16 | 59503.40 | $210.9\pm 2.0$ | $276.9\pm 0.5$ | $0.7\pm 0.1$ | 832 nm | Gemini
EPIC 220555384 | 2021-12-09 | 59557.25 | $204.9\pm 5.0$ | $277.1\pm 2.6$ | $0.7\pm 0.1$ | 832 nm | Gemini
EPIC 220555384 | 2022-09-14 | 59837.51 | $211.5\pm 2.4$ | $278.3\pm 0.5$ | $0.7\pm 0.3$ | $i^{\prime}$ | WIYN
EPIC 220555384 | 2022-09-15 | 59837.51 | $211.9\pm 2.5$ | $276.5\pm 0.5$ | $0.7\pm 0.1$ | $i^{\prime}$ | Gemini

##  3 Observations

We observed our binary sample using the ‘Alopeke and Zorro speckle cameras
(Scott et al., 2021) on the Gemini 8.1 m North and South telescopes from June
2021 to September 2022 and using the NN-EXPLORE Exoplanet and Stellar Speckle
Imager (NESSI) speckle camera on the WIYN 3.5 m telescope (Scott et al., 2018)
from October 2022 to January 2023. At least three image sets were obtained for
each target, where one set consists of 1000 60 ms (Gemini) or 40 ms (WIYN)
exposures taken simultaneously in two filters. The 2021 data were taken using
562 nm and 832 nm narrow-band filters, while some of the 2022–2023 data were
taken using the SDSS $r^{\prime}$, $i^{\prime}$, or $z^{\prime}$ broad-band
filters to increase the signal-to-noise ratio. Additional image sets were
taken for fainter targets ($V>9$ mag), and a point source standard star was
observed immediately before or after each target for calibration. We reduced
the data using the pipeline developed by the speckle team (Howell et al.,
2011; Horch et al., 2011) to calculate the power spectrum of each target,
divide the mean power spectrum of the target by that of the standard star, and
fit the fringes for initial estimates of the binary parameters. For solutions
with a 180 deg position angle ambiguity, we selected the solution consistent
with other speckle or adaptive optics observations.

We then determined the final relative positions and uncertainties from the
binary power spectra by performing a grid search in relative separation and
position angle based on the gridfit code of Schaefer et al. (2016). We first
calibrated the $uv$-plane with the power spectra of known binary stars and the
predicted relative positions from literature orbital solutions: HD 214850 and
HIP 46454 (Muterspaugh et al., 2010), HIP 84949 (Muterspaugh et al., 2006),
and HIP 4849 (Tokovinin et al., 2015). Once the $uv$-plane was calibrated for
each observing run, we tested a range of separations in right ascension
($\Delta$RA) and declination ($\Delta$DEC) around the solution found by the
speckle pipeline in steps of 1 mas. At each grid point, we created a model
power spectrum for these binary parameters, fit for the magnitude difference
of the binary, and calculated the $\chi^{2}$ goodness-of-fit statistic between
the observed and model fringes. We then mapped out the $1\sigma$ $\chi^{2}$
contour, fit for the uncertainties in $\Delta$RA and $\Delta$DEC, and
converted these values & uncertainties to relative separation ($\rho$) and
position angle ($\theta$, measured East of North). An example power spectrum,
reconstructed image, and $\chi^{2}$ map are shown in Figure 1. Table 3 lists
the UT date, Modified Julian Date (MJD), separation, position angle, magnitude
difference, filter, and telescope for each observation.

##  4 Visual Orbits

We combined our new relative astrometry with past measurements from Keck NIRC2
adaptive optics observations (Furlan et al., 2017; Dupuy et al., 2022), WIYN
speckle observations (Matson et al., 2018; Colton et al., 2021; Howell et al.,
2021), and Gemini speckle observations (Furlan et al., 2017; Lester et al.,
2021). If uncertanties were not listed in the literature, we adopted values of
5 mas and 2 deg for the relative separation and position angle, repsectively
(Howell et al., 2021).

We first used the compiled relative astrometry data to test the bound nature
of each binary system and confirm that the observed on-sky motion is actually
orbital motion. Because our binary stars are unresolved by Gaia, we could not
do a typical common proper motion analysis (e.g., Colton et al., 2021).
Instead, we compared the proper motion ($\mu$) of the primary star from Gaia
DR3 (listed in Table 2) to the observed relative motion of the secondary star.
If the binary companion is unbound, i.e. a background line-of-sight companion,
then the companion’s observed motion would be equal in magnitude to the proper
motion of the primary star. Figure 2 shows the ratio of the total proper
motion to the mean angular speed of the companion, which was calculated in RA
and DEC separately from the first to last observations then added in
quadrature. We found that the proper motion was $3-140$ times larger compared
to the observed motion for all our binaries. Therefore, the observed motion is
likely true orbital motion and can be fit with a Keplerian orbit. We also show
the direction of the primary star’s proper motion in the orbit plots in the
Appendix to compare with the orbital motion.

Figure 2: Ratio of the total Gaia DR3 proper motion to the total observed
motion for each binary in our sample. The proper motion is at least three
times larger compared to the observed relative motion for all systems, so this
motion is likely true orbital motion of a bound companion rather than motion
of an unbound, line-of-sight companion.

Table 4: Visual Orbit Solutions  Target |  $P$ (yr) | $\tau$ |  $i$ (deg) | $e$ |  $\omega_{B}$ (deg) |  $\Omega_{B}$ (deg) |  $a$ (AU)
---|---|---|---|---|---|---|---
KOI 270 | $290.0^{+251.0}_{-200.0}$ | $0.65^{+0.10}_{-0.10}$ | $86.8^{+1.3}_{-1.9}$ | $0.10^{+0.18}_{-0.10}$ | $323.5^{+8.7}_{-7.2}$ | $248.8^{+3.5}_{-3.5}$ | $55.0^{+11.1}_{-16.0}$
KOI 307 | $290.0^{+212.8}_{-75.5}$ | $0.03^{+0.08}_{-0.08}$ | $129.0^{+24.5}_{-23.7}$ | $0.67^{+0.25}_{-0.25}$ | $165.0^{+49.3}_{-54.4}$ | $267.5^{+25.0}_{-25.0}$ | $61.0^{+20.5}_{-14.9}$
KOI 1613 | $675.0^{+557.4}_{-218.3}$ | $0.15^{+0.14}_{-0.14}$ | $86.5^{+3.9}_{-4.5}$ | $0.23^{+0.19}_{-0.19}$ | $152.5^{+47.6}_{-53.4}$ | $182.5^{+3.3}_{-3.3}$ | $102.5^{+38.6}_{-27.0}$
KOI 1961 | $27.5^{+73.9}_{-9.5}$ | $0.55^{+0.08}_{-0.08}$ | $64.5^{+6.6}_{-11.8}$ | $0.79^{+0.21}_{-0.22}$ | $325.0^{+27.7}_{-21.9}$ | $101.0^{+22.1}_{-22.1}$ | $11.5^{+3.1}_{-2.3}$
KOI 2124 | $150.0^{+243.4}_{-163.5}$ | $0.77^{+0.13}_{-0.13}$ | $89.9^{+1.2}_{-1.3}$ | $0.04^{+0.32}_{-0.04}$ | $341.0^{+8.3}_{-11.9}$ | $233.8^{+1.8}_{-1.8}$ | $27.0^{+12.0}_{-9.3}$
KOI 3234 | $175.0^{+362.5}_{-54.7}$ | $0.97^{+0.29}_{-0.29}$ | $33.0^{+23.0}_{-31.7}$ | $0.01^{+0.53}_{-0.01}$ | $135.0^{+51.1}_{-59.9}$ | $196.0^{+42.9}_{-42.9}$ | $43.0^{+16.1}_{-9.0}$
KOI 3456 | $37.5^{+71.7}_{-10.0}$ | $0.55^{+0.15}_{-0.15}$ | $97.0^{+10.3}_{-10.1}$ | $0.97^{+0.03}_{-0.63}$ | $312.5^{+21.7}_{-28.6}$ | $192.5^{+4.2}_{-4.2}$ | $15.0^{+4.7}_{-4.3}$
KOI 4252 | $70.0^{+75.0}_{-40.0}$ | $0.73^{+0.16}_{-0.16}$ | $99.5^{+5.5}_{-3.5}$ | $0.33^{+0.10}_{-0.10}$ | $307.5^{+12.2}_{-9.6}$ | $117.0^{+4.1}_{-4.1}$ | $19.0^{+12.5}_{-6.3}$
KOI 5971 | $50.0^{+46.8}_{-40.0}$ | $0.29^{+0.12}_{-0.12}$ | $93.0^{+6.2}_{-6.2}$ | $0.39^{+0.28}_{-0.28}$ | $37.5^{+25.1}_{-32.3}$ | $313.0^{+4.8}_{-4.8}$ | $13.0^{+4.5}_{-4.7}$
TOI 271 | $22.5^{+47.2}_{-12.3}$ | $0.73^{+0.11}_{-0.11}$ | $98.5^{+11.0}_{-6.2}$ | $0.95^{+0.05}_{-0.08}$ | $327.5^{+95.6}_{-24.9}$ | $49.8^{+4.2}_{-4.2}$ | $11.0^{+4.3}_{-3.4}$
TOI 1287 | $27.5^{+39.6}_{-13.3}$ | $0.75^{+0.11}_{-0.11}$ | $86.8^{+3.1}_{-4.3}$ | $0.29^{+0.49}_{-0.29}$ | $341.0^{+36.8}_{-20.3}$ | $169.0^{+4.3}_{-4.3}$ | $11.5^{+3.9}_{-2.7}$
EPIC 212303338 | $57.5^{+184.5}_{-25.8}$ | $0.63^{+0.27}_{-0.27}$ | $103.5^{+8.1}_{-4.0}$ | $0.47^{+0.14}_{-0.14}$ | $102.5^{+34.0}_{-32.6}$ | $44.5^{+5.8}_{-5.8}$ | $17.5^{+14.3}_{-5.1}$
EPIC 220555384 | $67.5^{+231.0}_{-16.2}$ | $0.59^{+0.12}_{-0.12}$ | $77.0^{+6.6}_{-16.1}$ | $0.91^{+0.09}_{-0.33}$ | $293.0^{+14.3}_{-22.2}$ | $99.0^{+3.4}_{-3.4}$ | $18.5^{+11.3}_{-3.2}$
Figure 3: Example corner plot of the orbital solution for KOI 1961. The
diagonal frames show posterior histograms for each orbital parameter, and the
off-diagonal frames show the covariance between different pairs of parameters.
Figure 4: Example visual orbit for planet hosting binary KOI 1961. The primary
star is positioned at the origin (black cross), and the relative positions of
the secondary component are marked with colored points. A random subset of the
orbital solutions from orbitize! are shown in grey.

We fit for the visual orbits using the orbitize! package (Blunt et al., 2020)
and Orbits For The Impatient (Blunt et al., 2017) module, which was built
specifically for long period systems. For each binary, we estimated the
primary star’s mass from the effective temperature and the Modern Mean Dwarf
Stellar Color and Effective Temperature Sequence (Pecaut & Mamajek, 2013),
then used the speckle magnitude difference to estimate the secondary’s mass
(see Matson et al., 2018). We used the resulting total mass (with
uncertainties of 30%) and the Gaia DR3 parallaxes & uncertainties (Gaia
Collaboration et al., 2016) as priors, which are listed in Table 2. The free
parameters were then the semi-major axis ($a$), inclination ($i$),
eccentricity ($e$), argument of periastron of the companion ($\omega_{B}$)
111Note that our visual orbit solutions use argument of periastron of the
secondary star ($\omega_{B}$), while spectroscopic orbit solutions typically
use the argument of periastron of the primary star
($\omega_{A}=\omega_{B}+180^{\circ}$)., longitude of the ascending node of the
companion ($\Omega_{B}$), and epoch of periastron. Orbitize! uses a parameter
$\tau$ to represent the epoch of periastron as a fraction of the orbital
period past the reference epoch MJD 58849. We ran orbitize! until $10^{5}$
orbits were accepted, created histograms for each orbital parameter, and fit
asymmetrical Gaussians to each distribution to find the best-fit values and
uncertainties. Table 4 lists the orbital solutions for each binary. An example
corner plot and visual orbit are shown in Figures 3 and 4, respectively, while
the visual orbits for all systems are shown in Figures 7–19 in the Appendix.
Next, we used the total system mass and the semi-major axis to estimate the
orbital period ($P$) for each system. Our observations cover roughly 1–25% of
the orbits so the orbital periods are not yet well constrained, but orbital
coverage of a few percent is sufficient to reliably measure the orbital
inclination (Dupuy et al., 2022).

As a consistency check, we also fit for the visual orbits using a custom code.
We created $10^{6}$ sets of random orbital parameters, calculated the
predicted binary positions, and determined the $\chi^{2}$ value of each
solution. Orbital parameters for each iteration were drawn from uniform
distributions. We then found parameters with the lowest reduced $\chi^{2}$
value, fit a parabola to the bottom of the $\chi^{2}$ distribution, and found
the $1\sigma$ uncertainties where $\chi^{2}\leq\chi^{2}_{min}+1$. The
inclinations from orbitize! are consistent with those found by our fitting
method to within the uncertainties. However, our code could not converge on a
full orbital solution as well as orbitize! due to the orbital period as a free
parameter, so we used the orbitize! solutions in the rest of this paper.

##  5 Results

###  5.1 Planet-Binary Orbital Alignment

We compared the orbital inclinations of the stellar companions ($i$) and of
the transiting planets (assumed to be $90^{\circ}$, i.e. edge-on to our line
of sight) to determine the planet-binary orbital alignment ($\sin|90-i|$) in
each system. Note that this is only the minimum alignment, because we do not
know the longitude of the ascending node of the transiting planet. Figure 5
shows a histogram of the planet-binary orbital alignment for our 13 binary
host systems. The uncertainties for each histogram bin were found by varying
each binary inclination within it’s Gaussian uncertainty over $10^{5}$
iterations, then taking the standard deviation of the values in each histogram
bin from all iterations. In the case of asymmetric uncertainties in
inclination, the larger uncertainty value was used. We found that our binary
host orbits are more often aligned with the planetary orbits, with all mutual
inclinations less than $60^{\circ}$. Our result is consistent with the results
of Dupuy et al. (2022) using linear orbital motion estimates and of Christian
et al. (2022) using Gaia astrometric parameters. Specifically, Christian et
al. (2022) found that only systems with $a<700$ AU were preferentially
aligned, so our sample confirms this result down to systems with much smaller
separations.

Furthermore, low mutual inclination between the planetary and binary orbits is
consistent with theories of binary star formation and with planet formation in
multi-star systems. Close binaries (such as those in this study), that formed
in-situ via disk fragmentation or via turbulent fragmentation and migration,
are expected to have binary orbits aligned with the primary stars’
protoplanetary disks. From a planet formation perspective, all of the binaries
in our sample have mutual inclinations less than $60^{\circ}$, which is
consistent with theoretical predictions. For example, (Quintana et al., 2002)
simulated planet formation around each star in the $\alpha$ Cen AB system;
they found that planets could form more easily when the protoplanetary disk
was inclined by $30-45^{\circ}$ compared to the binary orbit, but were
unstable when the disk was inclined by $60^{\circ}$. Because most of our
systems are well aligned, they likely did not undergo strong tidal
interactions that would have torqued the protoplanetary disk and resulted in
either non-transiting planets or poor binary-planet alignment.

Figure 5: Alignment between the planetary and binary orbital inclinations
($\sin|90-i|$). A random inclination distribution would result in uniform
histograms, but instead our binary host star orbits are often well aligned
with the planets’ orbits. This is consistent with numerical simulations of
planet formation, which found it more difficult to form planets in
protoplanetary disks with a highly misaligned stellar companion (Quintana et
al., 2002).

###  5.2 Planet Stability

We next tested the binary and planet configurations of our sample against
dynamical stability predictions from numerical simulations. We calculated the
critical planet semi-major axis ($a_{crit}$) using Equation 1 in Holman &
Wiegert (1999), for which planets with semi-major axes ($a_{pl}$) less than
$a_{crit}$ would be stable orbiting one star in a binary system over thousands
of binary orbital cycles. For the multi-planet systems, we evaluated each
planet separately. The critical value depends on the binary’s semi-major axis,
eccentricity, and mass ratio, so we used the mass ratios estimated from the
speckle magnitude difference in Section 4. The uncertainties in $a_{crit}$
were estimated by varying the binary parameters within their uncertainties
over $10^{5}$ iterations and taking the standard deviation of the results.
Figure 6 compares the planet separations to the critical separations for the
binaries in our sample. We found that all planets have separations less than
$a_{crit}$ and therefore would be dynamically stable. The only systems with
planet separations near the critical separation are KOI 5971.01, with
$a_{pl}\approx 1.0$ AU and $a_{crit}=1.3\pm 0.6$ AU, and KOI 3456.02, with
$a_{pl}\approx 1.2$ AU and $a_{crit}=2.7\pm 2.1$ AU. These systems would
benefit from continued speckle monitoring to better constrain the binary
orbits and confirm $a_{crit}$, as well as additional transit follow-up to
confirm the planetary nature of these planet candidates. Increasing the number
of binary planet hosts in our sample and extending to longer period planets
would provide additional tests of these dynamical stability models.

Figure 6: Critical semi-major axis ($a_{crit}$) versus planet semi-major axis
($a_{pl}$) for the planet candidates in our sample. Holman & Wiegert (1999)
predict that planets with $a_{crit}>a_{pl}$ would be dynamically stable in
binary systems. All systems in our sample lie above the 1:1 line (dotted) and
therefore are expected to be dynamically stable, though two planets (labeled)
are close to their critical separation.

##  6 Conclusions

We presented new relative astrometry of 13 planet host binary systems and
measured preliminary visual orbits using the orbitize! code. We investigated
the mutual orbital inclination between the binary orbits and the transiting
planets, and found that our binary host stars have orbital inclinations
similar to those of the planets. Our result for close ($a<100$ AU) binaries is
consistent with past work for wide, planet host binaries (e.g., Christian et
al., 2022), and supports the predictions of planet formation simulations that
binary companions inclined with respect to the protoplanetary disk will hinder
planet formation.

We plan to continue monitoring our full sample of 40 planet host binaries in
order to increase our orbital coverage and sample size and better constrain
all of the orbital parameters. Eccentric companions cause increased torque on
the protoplanetary disks and could cause the planets to become misaligned
relative to the stellar companion, so investigating planet-binary orbital
alignment as a function of binary separation and eccentricity would be a
valuable test of planet formation theory. Continued astrometric monitoring
will better constrain the binary orbital parameters (e.g., $i$ and $e$) and
enable such investigations. We also started spectroscopic monitoring of these
systems to measure the radial velocity trends and help break the degeneracy
between the binary orbital inclination and eccentricity. Overall, we are
working to build the orbital demographics of planet host binaries to better
understand how planets form in multi-star systems.

Future work could also investigate the alignment of all components of the
binary and planetary system, such as the spin-orbital alignment of the host
star compared to the planetary and stellar companions. This would complement
past work that typically studied planet-star alignment in single star systems
(e.g., Winn et al., 2010; Triaud et al., 2010; Morton & Winn, 2014) and star-
companion alignment in non-planet hosting binaries (e.g., Albrecht et al.,
2007; Justesen & Albrecht, 2020), as well as theoretical modeling of
misaligned disks in binary systems (Lai, 2014; Martin et al., 2014). Such an
investigation would require the Rossiter-McLaughlin technique to measure the
orientation of the planet’s orbit with respect to the host star’s rotation
(Albrecht et al., 2022), as well as measurement of the binary orbital
inclination with respect to the stellar rotation. One could estimate the
stellar rotation angle based on the rotation period, projected rotational
velocity, and radius for the stars with rotational spot modulation in the
light curve (Justesen & Albrecht, 2020). The spin-orbit alignment of planetary
and binary systems is a useful probe of formation and dynamical history (Winn
& Fabrycky, 2015), so this work provides the binary orbital inclinations
necessary for future studies.

The authors would like to thank the anonymous referee for their thorough
review and helpful comments. We also thank the staff at Gemini and WIYN for
their invaluable help conducting observations, as well as Josh Winn for useful
conversations. KVL is supported by an appointment to the NASA Postdoctoral
Program at the NASA Ames Research Center, administered by Oak Ridge Associated
Universities under contract with NASA. This work made use of the High-
Resolution Imaging instruments NESSI, ‘Alopeke, and Zorro, which were funded
by the NASA Exoplanet Exploration Program and built at the NASA Ames Research
Center by Steve B. Howell, Nic Scott, Elliott P. Horch, and Emmett Quigley.
Gemini Observatory is a program of NSF’s NOIRLab, which is managed by the
Association of Universities for Research in Astronomy (AURA) under a
cooperative agreement with the National Science Foundation on behalf of the
Gemini partnership: the National Science Foundation (United States), National
Research Council (Canada), Agencia Nacional de Investigación y Desarrollo
(Chile), Ministerio de Ciencia, Tecnología e Innovación (Argentina),
Ministério da Ciência, Tecnologia, Inovações e Comunicações (Brazil), and
Korea Astronomy and Space Science Institute (Republic of Korea). The authors
wish to recognize and acknowledge the very significant cultural role and
reverence that the summit of Maunakea has always had within the indigenous
Hawaiian community. We are most fortunate to have the opportunity to conduct
observations from this mountain. Data presented herein were obtained at the
WIYN Observatory from telescope time allocated to NN-EXPLORE through the
scientific partnership of the National Aeronautics and Space Administration,
the National Science Foundation, and the NSF’s National Optical-Infrared
Astronomy Research Laboratory. The WIYN Observatory is a joint facility of the
NSF’s NOIRLab, Indiana University, the University of Wisconsin-Madison,
Pennsylvania State University, the University of Missouri, the University of
California-Irvine, and Purdue University. DRC and CAC acknowledge partial
support from NASA Grant 18-2XRP18_2-0007, and CAC acknowledges that this
research was carried out at the Jet Propulsion Laboratory, California
Institute of Technology, under a contract with the National Aeronautics and
Space Administration (80NM0018D0004). This research has made use of the
Exoplanet Follow-up Observing Program (2022) website and NASA Exoplanet
Archive (2019), which are operated by the California Institute of Technology,
under contract with the National Aeronautics and Space Administration under
the Exoplanet Exploration Program.

Figure 7: Left: Visual orbit solutions for KOI 270. The primary star is
positioned at the origin (black cross), and the relative positions of the
secondary component are marked with colored points. A random subset of the
accepted orbital solutions from orbitize! are shown in grey. The green arrow
shows the Gaia proper motion of the primary star (in a single year), which is
inconsistent with the observed motion of the secondary. Right: The observed
changes in position angle and relative separation over time, plotted against
the possible orbital solutions.  Figure 8: Left: Visual orbit solutions for
KOI 307. The primary star is positioned at the origin (black cross), and the
relative positions of the secondary component are marked with colored points.
A random subset of the accepted orbital solutions from orbitize! are shown in
grey. The green arrow shows the Gaia proper motion of the primary star (in a
single year), which is inconsistent with the observed motion of the secondary.
Right: The observed changes in position angle and relative separation over
time, plotted against the possible orbital solutions.  Figure 9: Left: Visual
orbit solutions for KOI 1613. The primary star is positioned at the origin
(black cross), and the relative positions of the secondary component are
marked with colored points. A random subset of the accepted orbital solutions
from orbitize! are shown in grey. The green arrow shows the Gaia proper motion
of the primary star (in a single year), which is inconsistent with the
observed motion of the secondary. Right: The observed changes in position
angle and relative separation over time, plotted against the possible orbital
solutions.  Figure 10: Left: Visual orbit solutions for KOI 1961. The primary
star is positioned at the origin (black cross), and the relative positions of
the secondary component are marked with colored points. A random subset of the
accepted orbital solutions from orbitize! are shown in grey. The green arrow
shows the Gaia proper motion of the primary star (in a single year), which is
inconsistent with the observed motion of the secondary. Right: The observed
changes in position angle and relative separation over time, plotted against
the possible orbital solutions.  Figure 11: Left: Visual orbit solutions for
KOI 2124. The primary star is positioned at the origin (black cross), and the
relative positions of the secondary component are marked with colored points.
A random subset of the accepted orbital solutions from orbitize! are shown in
grey. The green arrow shows the Gaia proper motion of the primary star (in a
single year), which is inconsistent with the observed motion of the secondary.
Right: The observed changes in position angle and relative separation over
time, plotted against the possible orbital solutions.  Figure 12: Left: Visual
orbit solutions for KOI 3234. The primary star is positioned at the origin
(black cross), and the relative positions of the secondary component are
marked with colored points. A random subset of the accepted orbital solutions
from orbitize! are shown in grey. The green arrow shows the Gaia proper motion
of the primary star (in a single year), which is inconsistent with the
observed motion of the secondary. Right: The observed changes in position
angle and relative separation over time, plotted against the possible orbital
solutions.  Figure 13: Left: Visual orbit solutions for KOI 3456. The primary
star is positioned at the origin (black cross), and the relative positions of
the secondary component are marked with colored points. A random subset of the
accepted orbital solutions from orbitize! are shown in grey. The green arrow
shows the Gaia proper motion of the primary star (in a single year), which is
inconsistent with the observed motion of the secondary. Right: The observed
changes in position angle and relative separation over time, plotted against
the possible orbital solutions.  Figure 14: Left: Visual orbit solutions for
KOI 4252. The primary star is positioned at the origin (black cross), and the
relative positions of the secondary component are marked with colored points.
A random subset of the accepted orbital solutions from orbitize! are shown in
grey. The green arrow shows the Gaia proper motion of the primary star (in a
single year), which is inconsistent with the observed motion of the secondary.
Right: The observed changes in position angle and relative separation over
time, plotted against the possible orbital solutions.  Figure 15: Left: Visual
orbit solutions for KOI 5971. The primary star is positioned at the origin
(black cross), and the relative positions of the secondary component are
marked with colored points. A random subset of the accepted orbital solutions
from orbitize! are shown in grey. The green arrow shows the Gaia proper motion
of the primary star (in a single year), which is inconsistent with the
observed motion of the secondary. Right: The observed changes in position
angle and relative separation over time, plotted against the possible orbital
solutions.  Figure 16: Left: Visual orbit solutions for TOI 271. The primary
star is positioned at the origin (black cross), and the relative positions of
the secondary component are marked with colored points. A random subset of the
accepted orbital solutions from orbitize! are shown in grey. The green arrow
shows the Gaia proper motion of the primary star (in a single year), which is
inconsistent with the observed motion of the secondary. Right: The observed
changes in position angle and relative separation over time, plotted against
the possible orbital solutions.  Figure 17: Left: Visual orbit solutions for
TOI 1287. The primary star is positioned at the origin (black cross), and the
relative positions of the secondary component are marked with colored points.
A random subset of the accepted orbital solutions from orbitize! are shown in
grey. The green arrow shows the Gaia proper motion of the primary star (in a
single year), which is inconsistent with the observed motion of the secondary.
Right: The observed changes in position angle and relative separation over
time, plotted against the possible orbital solutions.  Figure 18: Left: Visual
orbit solutions for EPIC 212303338. The primary star is positioned at the
origin (black cross), and the relative positions of the secondary component
are marked with colored points. A random subset of the accepted orbital
solutions from orbitize! are shown in grey. The green arrow shows the Gaia
proper motion of the primary star (in a single year), which is inconsistent
with the observed motion of the secondary. Right: The observed changes in
position angle and relative separation over time, plotted against the possible
orbital solutions.  Figure 19: Left: Visual orbit solutions for EPIC
220555384. The primary star is positioned at the origin (black cross), and the
relative positions of the secondary component are marked with colored points.
A random subset of the accepted orbital solutions from orbitize! are shown in
grey. The green arrow shows the Gaia proper motion of the primary star (in a
single year), which is inconsistent with the observed motion of the secondary.
Right: The observed changes in position angle and relative separation over
time, plotted against the possible orbital solutions.

## References

  * Albrecht et al. (2007) Albrecht, S., Reffert, S., Snellen, I., et al. 2007, A&A, 474, 565. doi:10.1051/0004-6361:20077953
  * Albrecht et al. (2022) Albrecht, S. H., Dawson, R. I., & Winn, J. N. 2022, PASP, 134, 082001. doi:10.1088/1538-3873/ac6c09
  * Artymowicz & Lubow (1994) Artymowicz, P. & Lubow, S. H. 1994, ApJ, 421, 651. doi:10.1086/173679
  * Batalha et al. (2013) Batalha, N. M., Rowe, J. F., Bryson, S. T., et al. 2013, ApJS, 204, 24. doi:10.1088/0067-0049/204/2/24
  * Behmard et al. (2022) Behmard, A., Dai, F., & Howard, A. W. 2022, AJ, 163, 160. doi:10.3847/1538-3881/ac53a7
  * Bergfors et al. (2013) Bergfors, C., Brandner, W., Daemgen, S., et al. 2013, MNRAS, 428, 182. doi:10.1093/mnras/sts019
  * Blunt et al. (2017) Blunt, S., Nielsen, E. L., De Rosa, R. J., et al. 2017, AJ, 153, 229. doi:10.3847/1538-3881/aa6930
  * Blunt et al. (2020) Blunt, S., Wang, J. J., Angelo, I., et al. 2020, AJ, 159, 89. doi:10.3847/1538-3881/ab6663
  * Cadman et al. (2022) Cadman, J., Hall, C., Fontanive, C., et al. 2022, MNRAS, 511, 457. doi:10.1093/mnras/stac033
  * Christian et al. (2022) Christian, S., Vanderburg, A., Becker, J., et al. 2022, AJ, 163, 207. doi:10.3847/1538-3881/ac517f
  * Chontos et al. (2022) Chontos, A., Murphy, J. M. A., MacDougall, M. G., et al. 2022, AJ, 163, 297. doi:10.3847/1538-3881/ac6266
  * Clark et al. (2022) Clark, C. A., van Belle, G. T., Ciardi, D. R., et al. 2022, AJ, 163, 232. doi:10.3847/1538-3881/ac6101
  * Colton et al. (2021) Colton, N. M., Horch, E. P., Everett, M. E., et al. 2021, AJ, 161, 21. doi:10.3847/1538-3881/abc9af
  * Dawson & Johnson (2018) Dawson, R. I. & Johnson, J. A. 2018, ARA&A, 56, 175. doi:10.1146/annurev-astro-081817-051853
  * Dupuy et al. (2016) Dupuy, T. J., Kratter, K. M., Kraus, A. L., et al. 2016, ApJ, 817, 80. doi:10.3847/0004-637X/817/1/80
  * Dupuy et al. (2022) Dupuy, T. J., Kraus, A. L., Kratter, K. M., et al. 2022, MNRAS, 512, 648. doi:10.1093/mnras/stac306
  * Everett et al. (2015) Everett, M. E., Barclay, T., Ciardi, D. R., et al. 2015, AJ, 149, 55. doi:10.1088/0004-6256/149/2/55
  * Exoplanet Follow-up Observing Program (2022) Exoplanet Follow-up Observing Program. 2022, IPAC. doi:10.26134/EXOFOP5
  * Fontanive et al. (2019) Fontanive, C., Rice, K., Bonavita, M., et al. 2019, MNRAS, 485, 4967. doi:10.1093/mnras/stz671
  * Fontanive & Bardalez Gagliuffi (2021) Fontanive, C. & Bardalez Gagliuffi, D. 2021, Frontiers in Astronomy and Space Sciences, 8, 16. doi:10.3389/fspas.2021.625250
  * Furlan et al. (2017) Furlan, E., Ciardi, D. R., Everett, M. E., et al. 2017, AJ, 153, 71. doi:10.3847/1538-3881/153/2/71
  * Gaia Collaboration et al. (2016) Gaia Collaboration, Prusti, T., de Bruijne, J. H. J., et al. 2016, A&A, 595, A1. doi:10.1051/0004-6361/201629272
  * Gaia Collaboration et al. (2022) Gaia Collaboration, Vallenari, A., Brown, A. G. A., et al. 2022, arXiv:2208.00211. doi:10.48550/arXiv.2208.00211
  * Guerrero et al. (2021) Guerrero, N. M., Seager, S., Huang, C. X., et al. 2021, ApJS, 254, 39. doi:10.3847/1538-4365/abefe1
  * Harris et al. (2012) Harris, R. J., Andrews, S. M., Wilner, D. J., et al. 2012, ApJ, 751, 115. doi:10.1088/0004-637X/751/2/115
  * Hatzes et al. (2003) Hatzes, A. P., Cochran, W. D., Endl, M., et al. 2003, ApJ, 599, 1383. doi:10.1086/379281
  * Hirsch et al. (2017) Hirsch, L. A., Ciardi, D. R., Howard, A. W., et al. 2017, AJ, 153, 117. doi:10.3847/1538-3881/153/3/117
  * Hirsch et al. (2021) Hirsch, L. A., Rosenthal, L., Fulton, B. J., et al. 2021, AJ, 161, 134. doi:10.3847/1538-3881/abd639
  * Holman & Wiegert (1999) Holman, M. J. & Wiegert, P. A. 1999, AJ, 117, 621. doi:10.1086/300695
  * Horch et al. (2011) Horch, E. P., Gomez, S. C., Sherry, W. H., et al. 2011, AJ, 141, 45. doi:10.1088/0004-6256/141/2/45
  * Horch et al. (2014) Horch, E. P., Howell, S. B., Everett, M. E., et al. 2014, ApJ, 795, 60. doi:10.1088/0004-637X/795/1/60
  * Howell et al. (2011) Howell, S. B., Everett, M. E., Sherry, W., et al. 2011, AJ, 142, 19. doi:10.1088/0004-6256/142/1/19
  * Howell et al. (2021) Howell, S. B., Matson, R. A., Ciardi, D. R., et al. 2021, AJ, 161, 164. doi:10.3847/1538-3881/abdec6
  * Huber et al. (2016) Huber, D., Bryson, S. T., Haas, M. R., et al. 2016, ApJS, 224, 2. doi:10.3847/0067-0049/224/1/2
  * Jang-Condell (2015) Jang-Condell, H. 2015, ApJ, 799, 147. doi:10.1088/0004-637X/799/2/147
  * Justesen & Albrecht (2020) Justesen, A. B. & Albrecht, S. 2020, A&A, 642, A212. doi:10.1051/0004-6361/202039138
  * Kostov et al. (2019) Kostov, V. B., Mullally, S. E., Quintana, E. V., et al. 2019, AJ, 157, 124. doi:10.3847/1538-3881/ab0110
  * Kraus et al. (2012) Kraus, A. L., Ireland, M. J., Hillenbrand, L. A., et al. 2012, ApJ, 745, 19. doi:10.1088/0004-637X/745/1/19
  * Kraus et al. (2016) Kraus, A. L., Ireland, M. J., Huber, D., et al. 2016, AJ, 152, 8. doi:10.3847/0004-6256/152/1/8
  * Kruse et al. (2019) Kruse, E., Agol, E., Luger, R., et al. 2019, ApJS, 244, 11. doi:10.3847/1538-4365/ab346b
  * Lai (2014) Lai, D. 2014, MNRAS, 440, 3532. doi:10.1093/mnras/stu485
  * Lester et al. (2021) Lester, K. V., Matson, R. A., Howell, S. B., et al. 2021, AJ, 162, 75. doi:10.3847/1538-3881/ac0d06
  * Martin et al. (2014) Martin, R. G., Nixon, C., Lubow, S. H., et al. 2014, ApJ, 792, L33. doi:10.1088/2041-8205/792/2/L33
  * Matson et al. (2018) Matson, R. A., Howell, S. B., Horch, E. P., et al. 2018, AJ, 156, 31. doi:10.3847/1538-3881/aac778
  * Moe & Kratter (2021) Moe, M. & Kratter, K. M. 2021, MNRAS, 507, 3593. doi:10.1093/mnras/stab2328
  * Morton & Winn (2014) Morton, T. D. & Winn, J. N. 2014, ApJ, 796, 47. doi:10.1088/0004-637X/796/1/47
  * Morton et al. (2016) Morton, T. D., Bryson, S. T., Coughlin, J. L., et al. 2016, ApJ, 822, 86. doi:10.3847/0004-637X/822/2/86
  * Mullally et al. (2015) Mullally, F., Coughlin, J. L., Thompson, S. E., et al. 2015, ApJS, 217, 31. doi:10.1088/0067-0049/217/2/31
  * Muterspaugh et al. (2006) Muterspaugh, M. W., Lane, B. F., Konacki, M., et al. 2006, A&A, 446, 723. doi:10.1051/0004-6361:20053749
  * Muterspaugh et al. (2010) Muterspaugh, M. W., Hartkopf, W. I., Lane, B. F., et al. 2010, AJ, 140, 1623. doi:10.1088/0004-6256/140/6/1623
  * NASA Exoplanet Archive (2019) NASA Exoplanet Archive. 2019, IPAC, Confirmed Planets Table. doi:10.26133/NEA1
  * Offner et al. (2010) Offner, S. S. R., Kratter, K. M., Matzner, C. D., et al. 2010, ApJ, 725, 1485. doi:10.1088/0004-637X/725/2/1485
  * Pecaut & Mamajek (2013) Pecaut, M. J. & Mamajek, E. E. 2013, ApJS, 208, 9
  * Quintana et al. (2002) Quintana, E. V., Lissauer, J. J., Chambers, J. E., et al. 2002, ApJ, 576, 982. doi:10.1086/341808
  * Raghavan et al. (2010) Raghavan, D., McAlister, H. A., Henry, T. J., et al. 2010, ApJS, 190, 1. doi:10.1088/0067-0049/190/1/1
  * Rowe et al. (2015) Rowe, J. F., Coughlin, J. L., Antoci, V., et al. 2015, ApJS, 217, 16. doi:10.1088/0067-0049/217/1/16
  * Schaefer et al. (2016) Schaefer, G. H., Hummel, C. A., Gies, D. R., et al. 2016, AJ, 152, 213. doi:10.3847/0004-6256/152/6/213
  * Scott et al. (2018) Scott, N. J., Howell, S. B., Horch, E. P., et al. 2018, PASP, 130, 054502. doi:10.1088/1538-3873/aab484
  * Scott et al. (2021) Scott, N. J., Howell, S. B., Gnilka, C. L., et al. 2021, Frontiers in Astronomy and Space Sciences, 8, 138. doi:10.3389/fspas.2021.716560
  * Su et al. (2021) Su, X.-N., Xie, J.-W., Zhou, J.-L., et al. 2021, AJ, 162, 272. doi:10.3847/1538-3881/ac2ba3
  * Thebault & Haghighipour (2015) Thebault, P. & Haghighipour, N. 2015, Planetary Exploration and Science: Recent Results and Advances, 309. doi:10.1007/978-3-662-45052-9_13
  * Triaud et al. (2010) Triaud, A. H. M. J., Collier Cameron, A., Queloz, D., et al. 2010, A&A, 524, A25. doi:10.1051/0004-6361/201014525
  * Tokovinin et al. (2015) Tokovinin, A., Mason, B. D., Hartkopf, W. I., et al. 2015, AJ, 150, 50. doi:10.1088/0004-6256/150/2/50
  * Valizadegan et al. (2022) Valizadegan, H., Martinho, M. J. S., Wilkens, L. S., et al. 2022, ApJ, 926, 120. doi:10.3847/1538-4357/ac4399
  * Van Eylen & Albrecht (2015) Van Eylen, V. & Albrecht, S. 2015, ApJ, 808, 126. doi:10.1088/0004-637X/808/2/126
  * Wang et al. (2014a) Wang, J., Xie, J.-W., Barclay, T., et al. 2014, ApJ, 783, 4. doi:10.1088/0004-637X/783/1/4
  * Wang et al. (2014b) Wang, J., Fischer, D. A., Xie, J.-W., et al. 2014, ApJ, 791, 111. doi:10.1088/0004-637X/791/2/111
  * Winn et al. (2010) Winn, J. N., Fabrycky, D., Albrecht, S., et al. 2010, ApJ, 718, L145. doi:10.1088/2041-8205/718/2/L145
  * Winn & Fabrycky (2015) Winn, J. N. & Fabrycky, D. C. 2015, ARA&A, 53, 409. doi:10.1146/annurev-astro-082214-122246
  * Winters et al. (2019a) Winters, J. G., Henry, T. J., Jao, W.-C., et al. 2019, AJ, 157, 216. doi:10.3847/1538-3881/ab05dc
  * Winters et al. (2019b) Winters, J. G., Medina, A. A., Irwin, J. M., et al. 2019, AJ, 158, 152. doi:10.3847/1538-3881/ab364d
  * Ziegler et al. (2020) Ziegler, C., Tokovinin, A., Briceño, C., et al. 2020, AJ, 159, 19. doi:10.3847/1538-3881/ab55e9
  * Zurlo et al. (2021) Zurlo, A., Cieza, L. A., Ansdell, M., et al. 2021, MNRAS, 501, 2305. doi:10.1093/mnras/staa3674


# Topological Filtering for Visual Data Mining and Analysis of Complex
Networks

Faraz Zaidi  CNRS UMR 5800 LaBRI & INRIA Bordeaux - Sud Ouest
351, cours de la Libération
33405 Talence cedex, FRANCE
Email<EMAIL_ADDRESS>
###### Abstract

The discovery of small world and scale free properties of many real world
networks has revolutionized the way we study, analyze, model and process
networks. An important way to analyze these complex networks is to visualize
them using graph layout algorithms. Due to their large size and complex
connectivity, it is difficult to make deductions from the visual
representation of these networks. In this paper, we present a method for
interactive analysis of large graphs based on topological filtering, network
metrics and visualization. We analyze a number of real world networks and draw
interesting conclusions using the proposed method.

##  I Introduction

Recent years have seen the ability of computers to store, process and
visualize large size networks [1]. The term network has different
significations for people from different fields and is used extensively to
represent systems such as social networks [2, 3, 4], online social media [5],
web graphs [6] networks [3, 4], air transport [7], metabolic pathways [8] and
world wide web [9]. Research has shown that although seemingly diverse, these
fields have strong common methodological foundations and share methods to
analyze, model, understand and organize these networks. Different measures
have been studied to classify these networks [10]. Two such classifications
have gained lots of interest when networks exhibit small world [11] and scale
free [12] features.

Having a look at the taxonomy of existing methods to analyze networks, one way
is to develop metrics and measures that return quantitative knowledge about
these networks. These measures can be grouped as element level, group level
and network level [10]. A good example of an element level measure is the
degree of a node, which refers to the number of connections a node has to
other nodes in the network. On the other hand, network level metrics consider
the entire network to calculate a quantitative measure. Betweeness Centrality
[13] is a good example of a network level metric.

Another way is to use visualization to understand and comprehend these
networks. These methods can be grouped into three classes as visual
exploration of data, visualization of data mining results and tightly coupled
data mining and visualization [14, 15]. Visual data exploration is the
interactive exploration of graphical representation of data to discover
knowledge. Visualization of data mining results is the process of graphically
representing the results of a data mining process to enable humans to easily
interpret the obtained results. A hybrid form of these two methods is where
visualization is integrated as part of the data mining algorithm and users or
domain experts interactively guide the data mining algorithm. Visual
exploration is a useful method to discover hidden knowledge and extract
interesting patterns in data [16]. It has been effectively applied in a number
of different fields with graphs following small world and scale free
properties [17].

Most of the real world networks today have hundreds of thousands of nodes and
edges. Metrics that are computationally expensive are no longer practically
applicable for real world networks. Even with the increasing computational
power, we still need faster methods, heuristics and decomposition methods that
can process these networks in reasonable time frames. Moreover, for these
large size networks, measures like centrality and structural organization of
networks are no longer dominated by elements but rather, groups and subsets.
The complex interactivity of these subsets play an important role in the
overall behavior and evolution of networks, thus presenting researchers with a
challenging problem.

An interesting approach to solve this problem is to decompose a network into
sub-components or sub-networks and then apply either measures or visualization
methods on these sub-networks to gain insight of the whole networks. In terms
of a measure, the decomposition speeds up the calculation as a subset of nodes
is considered instead of the entire network. In terms of visualization, it is
easier to visually analyze a network with few nodes as compared to the entire
network. Decomposition techniques are significant for visualization methods as
it is practically impossible to visualize these large size networks on a
computer screen even with the new and advanced visualization tools and
interactive techniques for visualization [18].

The contribution of this work is not the results or findings that we obtained
about different networks. All the findings listed in the paper are well known
(and they are cited) but these were discovered through several different
methods, often requiring complex mathematical and statistical formulations and
derivations. The contribution of this work is the ease of the proposed method,
as domain experts from a variety of different fields can benefit without
requiring any special skills. The proposed method is general and applicable to
a variety of networks as shown in the case studies when applied to social,
biological and technological networks. Furthermore, network metrics, filtering
and visualization methods have never been combined in this way to discover
these findings. Our objective is to rediscover the known facts and findings
using another approach which is suited for domain experts with non-
mathematical and non-computer science background to understand the complex
interconnected behavior of many different real world networks.

In this paper, we introduce a visual data exploration method which decomposes
large graphs through topology based node filtering, uses networks metrics for
quantitative analysis and visualization for macro level analysis and
interactive exploration. This topological decomposition is motivated by two
important features of real networks. The first is that these networks have
power law degree distribution and the second, visualization of these networks
produce highly entangled and hard to read drawings [19]. Our idea is to create
sub-networks based on degree connectivity and then visualize these sub-
networks to understand, analyze and extract information from them.

The rest of the paper is organized as follows: We introduce a number of
networks used for experimentation throughout this article in section III. In
section III, we introduce the proposed method and explain how various data
sets can be analyzed using this method. Finally we present conclusions and
future research directions in section V.

##  II Related Work

The idea to decompose and study complex networks is not new. A decomposition
based on the connectivity of vertices was proposed by Batagelj and Zaversnik
called the $k$-core decomposition [20]. The method consists of identifying
subsets of the network called $k$-cores. These subsets are obtained by
recursively removing all the vertices of degree smaller than $k$, until the
degree of all remaining vertices is larger than or equal to $k$. So for
example, to obtain a $2-core$ of a network, we remove all the vertices with
degree less than $2$ in the network, which is nodes of degree $1$. After this
removal, certain vertices that previously had high degree might now have
degree $1$, the removal process is repeated again until there are no vertices
of degree $1$ left in the network. All the vertices left after this removal
become part of $2-core$ and the process can be restarted for higher values of
$k$.

Cores with larger values of $k$ correspond to sets of vertices with high
degree and connected to high degree vertices only. This gives cores with
larger values of $k$, a more central position in the network’s structure [21].
This method has been used in several domains to analyze networks and the
connectivity of vertices such as, in the analysis of protein interaction
networks [22]. Apart from its utilization in analysis, it has also been used
to visualize large scale networks as it decomposes a network into subsets of
vertices of increasing centrality. It can also help focus on certain regions
of interest in a network [21].

The method we propose is significantly different from $k$-cores, although both
$k$-core and the proposed topological decomposition are based on degree of
vertices and create subsets. Topological decomposition focuses on studying how
edges are distributed in high and low degree nodes. $k$-cores focus on
recursively identifying central nodes and has clearly different objectives.
The differences will become more evident as we explain the details of our
method.

There are a number of other ways to decompose a network. The most widely used
method is Clustering [23], which groups similar nodes together. Clustering has
often been used to decompose large networks for better understanding and
visual mining [16]. Clustering focuses on grouping similar nodes whereas our
objective is to decompose the network and simplify the complex connectivity
behavior of nodes. The toplogical similarity of nodes can be used as a
similarity metric to group nodes together and thus the proposed method can be
considered as a topology based clustering method. For simplicity, we refer to
our method as a decomposition method rather than a clustering method.

Other methods for exploration and mining of networks include the work of
Abello et al. [24]. They introduced efficient network visualization techniques
that allow users to identify useful facts about actors and relations through
interactive navigation. They used abstraction levels starting from an overview
to close-up views where the navigation is based on the notion of graph-slices.
Henry et al.[19] present the idea of NodeTrix, which is only a hybrid
representation of node-link diagrams and adjacency matrix to better support
the analysis of community structures. The representation coupled with various
interaction techniques help users to create useful visualizations. Focus +
Context techniques [25] are another way to reduce the node clutter for visual
analysis and mining. These techniques allow users to simultaneously access
overview information as well as focus on interesting groups. Kreuseler and
Schumann[26] used an approach where they combine both analytical and
visualization methods to interactive data exploration. They proposed a
framework for visual data mining where the objective is to have a better
understanding of the information space.

##  III Data Sets

For experimentation purposes, we selected three datasets. We have transformed
these graphs into simple, undirected and unweighed graphs where required as
the proposed method deals with simple graphs only. We only consider the
biggest connected components for each dataset when the graphs were originally
disconnected. Geometry Network is a collaboration network of authors where two
authors are connected by an edge if they have co-authored an article together.
The network contains 3621 nodes and 9461 edges (http://vlado.fmf.uni-
lj.si/pub/networks/data/. Dblp2008 Network is another co-authorship network
constructed from the DBLP database http://www.informatik.uni-trier.de/~ley/db/
for the year 2008 which contains 93498 nodes and 260152 edges. AirTransport
Network is a network of air traffic between cities [7] having 1540 nodes and
16523 edges. Opte Network is an Internet Tomography network which is a
collection of routing paths from a test host to other networks on the
Internet. The database is available to the public from the Opte Project
website (http://opte.org/). The network has 35836 nodes and 42387 edges.
Protein Network is a Protein-Protein interactions network [27]. The data is
available from http://dip.doe-mbi.ucla.edu/dip and contains 1246 nodes and
3142 edges.

##  IV Topological Decomposition

In this section, we introduce the idea of Degree Induced Subgraphs (DIS) which
is a subgraph created by imposing constraints on node degrees. We define two
such graphs:

Definition 1: Maxd-DIS is an induced subgraph of $G$ with vertex set
$V^{\prime}$ such that nodes in $V^{\prime}$ have maximum degree $d$ in $G$.
Mathematically for a graph $G(V,E)$ where $V$=nodes and $E$=edges, the Maxd-
DIS is defined as an induced subgraph $G^{\prime}(V^{\prime},E^{\prime})$ such
that $V^{\prime}\subseteq V$ and $\forall u\in V^{\prime},deg_{G}(u)\leq d$
where $d$ can have values from $0$ to the maximum node degree possible for the
network under consideration.

Definition 2: Mind-DIS is an induced subgraph of $G$ with vertex set
$V^{\prime}$ such that nodes in $V^{\prime}$ have minimum degree $d$ in $G$.
Mathematically for a graph $G(V,E)$ where $V$=nodes and $E$=edges, the
$Min_{d}-DIS$ is defined as an induced subgraph
$G^{\prime}(V^{\prime},E^{\prime})$ such that $V^{\prime}\subseteq V$ and
$\forall u\in V^{\prime},deg_{G}(u)\geq d$ where $d$ can have values from $0$
to the maximum node degree possible for the network under consideration.

###  IV-A Maxd-DIS: A closer look

Consider a graph shown in Figure 1 (left) and we calculate the Max4-DIS
(right) in the figure. The nodes are labelled by their degree in the entire
graph. Calculating the Max4-DIS, the nodes with degree $5$ and $6$ are removed
and an induced subgraph from the remaining nodes is obtained. In this example,
it is quite clear that in Max4-DIS, the nodes break into disconnected
components. Thus a simple deduction is that the entire network was connected
by high degree nodes, as soon as we removed them, the network broke into
smaller connected components. Another interesting observation is that we can
study how edges are distributed in low degree nodes as by definition, the
Maxd-DIS considers only low degree nodes for low values of parameter $d$. An
important focus in the study of scale free networks has been the role of hubs
[12] where nodes with very high degree stand out in networks. One way to look
at the Maxd-DIS is that we want to avoid the hubs and look at how nodes
connect to each other in their absence.

Figure 1: An example of Max${}_{d}-$DIS before and after calculating
Max${}_{4}-$DIS.

Lets take another example from a real world graph, that of the Geometry
network by drawing several Maxd-DIS graphs. The graphs are drawn using a force
directed algorith FMMM [28]. This algorithm puts nodes densely connected to
each other closer in the layout and pushes nodes that are not connected to
each other at distances. These algorithms are ideally suited for visual
detection of community structures in networks. But in case of networks having
scale free properties, where lots of nodes connect to only a few nodes, it
becomes difficult to visually identify the presence of these communities. This
is because nodes with very high connectivity are placed in the center of the
layout and create an unreadable and tangled drawing in the center. Nodes of
low degree are placed towards the outer periphery and are sparsely connected
to each other. In Figure 2(a), we can see the entire network drawn using FMMM
algorithm. The network contains over 3500 nodes which makes it quite difficult
to see anything interesting in the network.

Figure 2(b) shows the Max5-DIS subgraph which contains $2757$ nodes which is
more than $76\%$ of the total nodes in the entire graph. This suggests that
most of the nodes in the network have low degree. Most of the time, our focus
is towards the high degree nodes that stand out in the analysis of these
complex networks. But the majority of the nodes have low node degree and we
stress that analysis methods should also focus on these nodes as they are in
majority and influence the overall behavior of the network to a large extent.

There are $1481$ edges in the subgraph which makes the average node degree to
be $0.53$ as compared to the overall value of $2.6$ which is a huge difference
in the context. The maximum node degree for the entire network is $102$. This
means that most of these low degree nodes tend to connect with ‘higher’ degree
nodes. Note that we emphasize the relative degree and use ‘higher’ instead of
‘highest’, this is to suggest that since we are analyzing Max5-DIS with degree
limit $5$, these nodes might end up connecting to nodes with degrees $6,7,8$
and not necessarily with nodes of degree closer to the highest node degree
which is $102$. We will have a look at this when we analyze the Max10-DIS and
Max15-DIS graphs.

Another interesting observation is the number of connected components, $1537$
and there are lots of nodes with degree $0$ in the Max5-DIS. Remember that the
entire network is a single connected component, as high degree nodes appear,
these smaller connected components merge to form one big single connected
component. Finally, an important observation is about the structure formed by
these low degree nodes when connecting to each other. We refer to the work of
Georg Simmel [29] who introduced the concept of triads as a fundamental
structure for social networks. The formation of triads has since been observed
in many real world networks.

Figure 2: Visualization of Maxd-DIS graphs for the Geometry network. (a)
Entire Network (b) Max5-DIS (c) Max10-DIS (d) Max15-DIS.

Figure 2(b) verifies the presence of triads as they are clearly visible.
Triads are present not only in connected components of more than three nodes,
but also in connected components of exactly three nodes. Moreover, we also
observe cliques of sizes $4$ and $5$. By construction of this network, we
expect cliques to be present. Since the data set is about articles in which it
is common to have 3, 4 or more authors, it is quite obvious that we will find
these cliques when visualizing the network. To avoid any false implications,
we would like to refer to Figure 1 once again, notice the clique of $5$ nodes,
when a Maxd-DIS is constructed, it no longer remains a clique of same size.
Thus when analyzing a subgraph such as Figure 2(b), we should not conclude
that there are only cliques of size $3$ or $4$, rather there are definitely
cliques of larger sizes in the entire network.

Figure 2(c) shows the Max10-DIS of the same network. Looking at the graph, we
can immediately see that lots of small connected components from Figure 2(b)
are now connected. Two such connected components are quite evident and there
is another one which is of considerable size. In mathematics, this phenomena
is called the emergence of a giant component [30]. The network changes
drastically as certain links are introduced, and becomes a single connected
component. In this case these links are introduced in the network by higher
degree nodes that are responsible of connecting all these smaller components.
The number of connected components in Max10-DIS are $942$ as compared to
$1537$ in Max5-DIS, which is a considerable decrease as we do not have very
high degree nodes.

Note that we still do not have the presences of very high degree nodes. If we
look at the degree distribution of geometry network shown in Figure 4, we see
that it is around degree value $10$ that the long tail starts to develop. In
terms of clustering, this is quite significant. Consider if we want to group
similar nodes, we can use this idea that in the absence of high degree nodes,
this network breaks into smaller connected components, and from the subgraph,
we can say that there are two big and a smaller cluster of nodes in the entire
network. As high degree nodes are introduced in this network, the network
becomes one big connected component and it becomes difficult to identify
clusters. One observation from the degree distribution is that the highest
frequency of nodes is that $60\%$ of the total nodes have degree less than
$4$.

And finally we move to Figure 2(d) which shows the Max15-DIS. A clear
development in this graph is the formation of the big connected component
which comprises of $2133$ nodes and $3523$ edges. Notice that this graph only
contains nodes with a maximum node degree of $15$ in the entire network as
compared to the highest node degree of $102$. This shows that approx. $59\%$
of the nodes are linked in a single connected component without the presence
of very high degree nodes.

An obvious question arises, how we define ‘high’ or ‘very high’ degree? there
is no concrete definition, but a rather vague estimation can be made by using
heuristics. If we compare $15$ with $102$, the gap is quite wide and is easy
to say that the value $15$ does not really represent ‘high’ values of degree.
On the other hand, if we compare $15$ with the average degree which is $2.6$,
the value is quite high and can be considered as a high value for node degree.
If we look in terms of percentage, the Max15-DIS contains $3413$ nodes which
is $94\%$ of the total nodes. If we consider the top $5\%$ nodes as the high
degree nodes, Max15-DIS suggests that in the absence of high degree nodes,
$59\%$ of the nodes in the network are still connected. Thus we suggest that
the Maxd-DIS can be used as a method to study an important feature of scale
free networks studied by Albert et al. [31] i.e. scale free networks are
robust to random loss of nodes but fragile to targeted worst-case attacks on
hubs.

Figure 3: (a)Four cliques representing different articles in a co-authorship
network (b) The cliques are combined to form high average path length with
certain nodes having higher degree (c) The cliques are combined to form low
average path length with Node A standing out as a very high degree node.
Figure 4: (a)Histograms and (b) Log-Log scatter plot of the Degree
Distribution of Geometry Network.

Looking at the average degree in this subgraph, for the $94\%$ of the nodes in
the entire network is $1.33$ as compared to overall value of $2.6$ for the
entire network. Thus the high degree nodes heavily influence the average
degree of nodes in the entire network. Obviously this is a direct implication
of the long tail in the degree distribution. The longer the tail, the bigger
would be the difference in the average node degree of low degree nodes and the
over all network.

About the connectivity of the nodes and the three bigger connected components
in Figure 2(c), there is an interesting observation about their average path
lengths. The three components have values of $12.9$, $12.4$ and $9.7$ which
when compared to the overall value of $5.31$ are quite high. Even the biggest
connected component in Figure 2(d) has a very high average path length of
$12.1$. As the high degree nodes appear in the network the average path length
drops considerably in the network. If we look closely at Figure 2(a,b,c), we
understand an important connectivity principle of these networks. When nodes
connect to each other through ‘higher’ degree nodes, the average path length
is a bit higher as the connections form long paths, and when nodes connect
through ‘very high’ degree nodes, the average path length is lower.

We further explain this using an example of co-authorship network. Consider
the four cliques in Figure 3(a) representing four different articles, where
the number of authors for the four cliques are 5,3,4,3 and each node is
labelled with alphabets from A to O. The four cliques can be connected to each
other by two principles. The first one is shown in Figure 3(b), which is in
the absence of very high degree nodes. Consider a person authoring two
articles with two different set of people, in that case, that node of that
person will be between two cliques. From the example in the figure we consider
person A and G are the same person and thus they connect the two cliques as
shown in Figure 3(b). Another way to connect two cliques is to add edges
between people writing different articles. In this example we add an edge
between F and I, suggesting that earlier these people worked with a different
set of people, but now they have collaborated to write together. Similarly,
person J is the same as O, and L is the same person as N. This connectivity
pattern introduced is due to the absence of very high degree nodes as, in this
connected network, no node has a very high degree. The result is that we get a
long string of cliques connected to each other just as we saw in Figure
2(c,d). On the other hand, another way to connect these cliques is shown in
Figure 3(c) where a single person co-authors many articles with other people,
in this case, that person is shown as node A, which collaborates with all
other authors. This gives a certain node, a very high node degree and reduces
the overall average path length to a large extent. Both these connectivity
patterns are present in the geometry network as we see long paths in Figure
3(c,d) and short paths in Figure 3(a).

Figure 5: Visualization of Maxd-DIS graphs for the Dblp2008 network. (a) Part
of Max5-DIS (b) Part of Max10-DIS.

Lets summarize what we have explained in this section. We have tried to
analyze the Geometry network using the Maxd-DIS decomposition. We identified
several interesting observations such as:

  1. 1.

Studying how edges are distributed in low degree nodes

  2. 2.

Observe the structure of networks such as the formation of triads and cliques
of bigger sizes

  3. 3.

Analyze the connectivity of nodes in the absence of hubs and see if a network
is fragile to targeted attacks

  4. 4.

Break up of nodes in several disconnected components in the absence of high
degree nodes, which motivates the idea of possibly grouping the connected
components as clusters

  5. 5.

For higher values of $d$, the smaller components begin to merge into a single
connected component even if very high degree nodes are not present

  6. 6.

The average path length of biggest connected components in the DIS subgraphs
is considerably higher in the absence of very high degree nodes indicating
that very high degree nodes are also responsible for reducing the overall
average path length

  7. 7.

Two connectivity patterns are observed, one in the presence of higher degree
nodes, and the other, when very high degree nodes appear. These patterns
effect the average path length of a connected component

All of the above findings have been studied using other methods and in most
cases, different methods to study different properties. Our contribution is
not what we can find using the proposed method but towards a unified and non-
complex method to help domain experts operate on their own and extract
knowledge without the help of a computer science expert. From this detailed
analysis of the Geometry network, we will have a look at some other real world
networks and try to see if we observe similar findings in other networks.

Figure 6: Visualization of Maxd-DIS graphs for the AirTransport network. (a)
Max25-DIS (b) Part of Max50-DIS.

Next, we consider another co-authorship network, the Dblp2008 network. In
Figure 5(a) and (b), we show the Max5-DIS and Max10-DIS of the network. In
both these figures, we show only part of the entire subgraphs as Max5-DIS
contains over $60000$ nodes and Max10-DIS over $80000$ nodes. The analysis is
quite similar to that of the Geometry network as in the Max5-DIS we see lots
of smaller connected components forming cliques of sizes between $1$ and $5$.
In Figure 5(b) we clearly see that the smaller components start to combine
into one big connected component. This suggests that even at degree value
$10$, smaller connected components begin to merge into a single connected
component.

We move to another example, the AirTransport network. Figure 6(a) shows the
Max25-DIS and Figure 6(b) shows part of the Part of Max50-DIS. We choose
relatively higher values of $d$ in this example because there were not
sufficient nodes or edges to observe anything interesting in lower values of
$d$. From Figure 6(a), we can see that there are many disconnected components
in the network as the previous examples. Recall, this signifies that these
networks require higher degree nodes to connected to each other. In the
structure of the network, we see that there are triads as well as stars in
Figure 6(a). If we look at the overall clustering coefficient, the presence of
triads is confirmed from the relatively high value of $0.49$. If we look
closely at the biggest connected component in Figure 6(b) with the Max50-DIS,
we see that there are many star like structures, i.e. many nodes with degree
$1$ connect to a single node. This makes a very interesting example to study
as we see that this network is a good mix of the two fundamental structures
that we have identified, the cliques and the stars. Moreover, the average node
degree in Max50-DIS is $1.49$, which is very low as compared to the overall
average degree of $10.7$. Along with the highest node degree of $487$, these
values suggest that the high degree nodes are very well connected to other
nodes in the network and thus push the average node degree to a high value of
$10.7$. The biggest connected component in Figure 6(b) has $832$ nodes and
$1941$ edges which is $54\%$ of the total nodes. The average path length of
the nodes in this component is $5.9$ as compared to the overall value of $2.9$
and the considerable difference again suggests that very high degree nodes are
responsible for the decrease in the overall average path length of the entire
network.

Figure 7: An example of Min${}_{d}-$DIS before and after calculating
Min${}_{4}-$DIS.

###  IV-B Mind-DIS: A closer look

Figure 8: Visualization of Mind-DIS graphs for the AirTransport network (a)
Entire Network (b) Min250-DIS with the $10$ highest degree nodes (c)
Min185-DIS with the $20$ highest degree nodes (d) Min94-DIS with the top $5\%$
highest degree nodes.

In this section, we present the details of Mind-DIS decomposition and how it
can help us to analyze networks. Consider the graph in Figure 7 on the left
and its Min4-DIS on the right. Only the nodes with degree at least $5$ are
left in the subgraph and the low degree nodes are removed. This method by
definition considers only high degree nodes and thus helps us to have a look
at how edges are distributed in high degree nodes of a network. In terms of
analysis of real world networks, lets consider the AirTransport network for a
detailed analysis using Min${}_{d}-$DIS. Figure 8(a) shows the entire network
containing $1540$ nodes and $16523$ edges.

Figure 9: Min17-DIS of Geometry network with $5\%$ highest degree nodes.
Figure 10: Min17-DIS of Dblp2008 network with $5\%$ highest degree nodes.

Figure 8(b) shows the Min${}_{250}-$DIS of the network showing the top $10$
highest degree nodes of the network connected through $44$ edges, which is
just one less to make it a clique. This suggests that the worlds most widely
connected airports have all a direct flight to each other with the exception
of one case. The high degree of a city refers to its many different
connections to other cities and not heavy traffic nor does it refer to the
world’s busiest airports. Figure 8(c) shows the top $20$ widely connected
airports in the world drawn using a circular layout. We have also labelled the
nodes with the city names. The nodes are connected through $189$ edges,
missing the only edge for it to be a clique. This high connectivity of high
degree nodes essentially comes from the design strategy of airlines and
connectivity of any two cities of the world. Since the idea is to minimize the
number of hops required to go from one place to the other, all the hubs in the
network are connected directly to each other. Figure 8(d) shows the top $5\%$
high degree nodes of the network. There are $77$ nodes connected through
$1822$ edges which is an average degree of $23$. In this subgraph, this high
connectivity can be measured in terms of average path length, which is $1.3$
as compared to the average path length value for the entire graph which is
$2.93$. This is a huge difference in the context. Note that there is not a
single node disconnected in this network, thus high connectivity of hubs has
been used as a method to increase the efficiency of transportation where the
criteria is obviously minimizing the hops as described earlier.

This example shows an application of how Mind-DIS can help analyze the
connectivity of hubs in real world networks. From the above example, we
learned that the hubs are very tightly connected to each other. We used the
average path length to quantify how close the nodes are to each other. We
summarize the type of analysis that can be performed using Mind-DIS below:

  * •

Study the distribution of edges in high degree nodes, hubs.

  * •

Observe the connectivity pattern of high degree nodes and see how they connect
to each other in different networks. We use Average path length to quantify
how closely the hubs are connected to each other.

Next, we consider the Geometry and Dblp2008 networks. For each of these
networks, we took the Mind-DIS with approximately $5\%$ highest degree nodes.
The results are shown in Figures 9 and 10 for these networks.

The Geometry network contains $179$ nodes and $1384$ edges. There are only two
nodes that are not connected to the biggest connected component as shown in
Figure 9. The average degree of this sub graph is $7.7$ as compared to $2.6$
of the overall network, which shows that these high degree nodes tend to
connect to each other. The average path length of the big connected component
is $2.4$ as compared to $5.3$ of the entire network, which again is a
considerable difference. In this network, obviously the number of hops is not
a criteria for efficiency, as it was for the AirTransport network. Here, the
social contacts of a research community play an important role to keep the
network well integrated where researchers collaborate to many different
people, which results in a low average path length for this subgraph. We go
back to the description of this network and the way this network is built. The
data set was obtained from Computational Geometry Database which contains
citation record of people working in this domain. The high connectivity of
nodes within and the low average path length of these high degree nodes can be
justified by the fact that people working in the same scientific domain have a
higher probability of interacting with each other. We can compare the behavior
of high average degree and low average path length of this network with that
of AirTransport network as being similar, although the semantics and the
reasoning behind this development are quite different. The other co-authorship
network is the Dblp2008 which is significantly different from the Geometry
network. Figure 10 shows the Min17-DIS of the network with $3872$ nodes and
$20828$. There are $326$ number of connected components which is quite
different from the previous two networks analyzed using Mind-DIS. Although
there is one big connected component, but there are many disconnected
components that are themselves well connected to other nodes forming cliques.
We call this behavior, local peaks as these are people working in different
scientific domains and publishing many articles. Their domains do not cross
necessarily and thus they are high publishing authors interacting with their
restricted research community but not with people of other domains.

The Mind-DIS reveals interesting structural behavior of real world networks
which can be quite useful when analyzing and improving the efficiency of these
networks. We found two interesting phenomena about the way high degree nodes
can connect to each other.

  * •

Nodes with high degree are well connected to each other forming one big
connected component with low average path lengths (comparing with respective
average path lengths of their entire networks) OR

  * •

Nodes with high degree break into several connected components and have a path
to each other through lower degree nodes

We studied the Maxd-DIS graphs for values $d=(5,10,15)$ and Mind-DIS graphs
for values top $5\%$ nodes. These values were chosen based on our analysis of
different real world graphs. One quantitative method to select these values is
based on the degree distribution and the long tail behavior. As discussed
previously, the tangled layout of these graphs is due to the very high degree
nodes, which can be detected by looking at the low frequency values or where
the long tail approximately starts. This value need not be perfect as an
approximation works well as shown in the case studies. To study how edges are
distributed in low degree nodes (Maxd-DIS), values below the starting point of
the tail can be used and to study how edges are distributed among high degree
nodes (Mind-DIS), values above this starting point can be used.

The time complexity of the overall method depends on the individual techniques
applied at each step of the method, be it analysis or visualization. The
decomposition itself is highly efficient and when slow metrics such as average
path length is applied to small subgraphs, there is an exponential reduction
in the time complexity making the overall method quite efficient. As for the
scalability of the proposed method, we have studied graphs of around 100000
nodes and 250000 edges (DBLP2008 network) and it took only less than 1 second
to generate all possible Maxd-DIS and Mind-DIS using the Tulip Software
library on a standard Intel Core i3 machine without the visual representation.
The visual representation depends on the layout algorithm used and FMMM is
known to be one of the fastest layout algorithms producing readable layout
drawings.

##  V Conclusions and Future Research Prospects

In this paper, we have introduced a method to analyze networks based on the
topological decomposition and visualization of networks. The most important
contribution of this method is that it enables us to visualize networks and
see how nodes and edges connect to each other in different networks. Combining
metrics and visualization technique to analyze complex large size networks
proves to be quite useful as the method allows us to understand different
connectivity behaviors as networks change from one domain to the other.

We found some interesting behavior in the way the edges are distributed in
high and low degree nodes. Based on this distribution, we can actually see
that as a function of degree, dense subgraphs can be present in high degree
and/or low degree nodes. Some interesting results about the structure of
networks were discovered, or re-discovered such as the presence of triads,
cliques of higher degree, star-like structures, showing the effectiveness of
the proposed method.

The topological decomposition proposed opens new dimensions in the field of
visual data mining as complex networks can be simplified using the proposed
method. Connectivity of nodes can be studied as a function of varying node
degree of a network and helps us to discover how edges are distributed in a
network. We see this method as an advancement towards the better understanding
of complex networks and an important tool to analyze networks for various
applications such as searching in networks, finding interesting patterns,
studying the connectivity behavior of nodes in networks and develop local as
well as group level metrics.

## References

  * [1] T. von Landesberger, A. Kuijper, T. Schreck, J. Kohlhammer, J. van Wijk, J.-D. Fekete, and D. Fellner, “Visual analysis of large graphs: State-of-the-art and future research challenges,” _Computer Graphics Forum_ , vol. 30, no. 6, pp. 1719–1749, 2011.
  * [2] S. Wasserman and K. Faust, _Social Network Analysis: Methods and Applications._ Cambridge: Cambridge University Press, 1994.
  * [3] R. Bourqui, F. Gilbert, P. Simonetto, F. Zaidi, U. Sharan, and F. Jourdan, “Detecting structural changes and command hierarchies in dynamic social networks,” in _Social Network Analysis and Mining, International Conference on Advances in_. Los Alamitos, CA, USA: IEEE Computer Society, 2009, pp. 83–88.
  * [4] R. Bourqui, F. Zaidi, F. Gilbert, U. Sharan, and P. Simonetto, “Vast 2008 challenge: Social network dynamics using cell phone call patterns,” in _IEEE Symposium on Visual Analytics Science and Technology_ , 2008.
  * [5] P. Comar, P.-N. Tan, and A. Jain, “Simultaneous classification and community detection on heterogeneous network data,” _Data Mining and Knowledge Discovery_ , vol. 25, pp. 420–449, 2012.
  * [6] F. Zaidi, A. Sallaberry, and G. Melançon, “Revealing hidden community structures and identifying bridges in complex networks: An application to analyzing contents of web pages for browsing,” in _WI-IAT ’09: Proceedings of the 2009 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology_ , 2009, pp. 198–205.
  * [7] C. Rozenblat, G. Melançon, and P.-Y. Koenig, “Continental integration in multilevel approach of world air transportation (2000-2004),” _Networks and Spatial Economics_ , 2008.
  * [8] S. Bilke and C. Peterson, “Topological properties of citation and metabolic networks,” _Rev. E_ , vol. 64, p. 036106, 2001.
  * [9] L. A. Adamic, “The small world web,” in _Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries_ , ser. Lecture Notes in Computer Science, vol. 1696. Springer-Verlag, 1999, pp. 443–452.
  * [10] U. Brandes and T. Erlebach, _Network Analysis : Methodological Foundations (Lecture Notes in Computer Science)_. Springer, March 2005.
  * [11] D. J. Watts and S. H. Strogatz, “Collective dynamics of ’small-world’ networks,” _Nature_ , vol. 393, pp. 440–442, Jun. 1998.
  * [12] A. L. Barabási and R. Albert, “Emergence of scaling in random networks,” _Science_ , vol. 286, no. 5439, pp. 509–512, 1999.
  * [13] L. C. Freeman, “A set of measures of centrality based on betweenness,” _Sociometry_ , vol. 40, pp. 35–41, 1977.
  * [14] M. C. de Oliveira and H. Levkowitz, “From visual data exploration to visual data mining: a survey,” _Visualization and Computer Graphics, IEEE Transactions on_ , vol. 9, no. 3, pp. 378–394, 2003.
  * [15] F. Zaidi, “Analysis, structure and organization of complex networks,” Ph.D. dissertation, Ecole doctorale de Mathématiques et Informatique, Université de Bordeaux 1, France, 2010.
  * [16] D. A. Keim, “Information visualization and visual data mining,” _IEEE Tran. on Visualization and Computer Graphics_ , vol. 8(1), pp. 1–8, 2002.
  * [17] Y. Jia, M. Garland, and J. C. Hart, “Social network clustering and visualization using hierarchical edge bundles,” _Computer Graphics Forum_ , vol. 30, no. 8, pp. 2314–2327, 2011.
  * [18] I. Herman, G. Melançon, and M. S. Marshall, “Graph visualization and navigation in information visualization: A survey,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 6, no. 1, pp. 24–43, 2000.
  * [19] N. Henry, J.-D. Fekete, and M. J. McGuffin, “Nodetrix: a hybrid visualization of social networks,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 13, pp. 1302–1309, November 2007.
  * [20] V. Batagelj and M. Zaversnik, “Generalized cores,” in _CoRR_ , 2002.
  * [21] J. I. Alvarez-Hamelin, L. Dall’Asta, A. Barrat, and A. Vespignani, “k-core decomposition: a tool for the visualization of large scale networks,” _Adv. in Neural Info. Processing Systems_ , vol. 18, pp. 41–50, 2006.
  * [22] S. Wuchty and E. Almaas, “Peeling the yeast protein network.” _Proteomics_ , vol. 5, no. 2, pp. 444–449, February 2005.
  * [23] S. E. Schaeffer, “Graph clustering,” _Computer Science Review_ , vol. 1, no. 1, pp. 27–64, August 2007.
  * [24] J. Abello and J. Korn, “Mgv: A system for visualizing massive multidigraphs,” _IEEE Trans. Visualization and Computer Graphics_ , vol. 8, no. 1, pp. 21–38, 2002.
  * [25] F. Boutin, J. Thievre, and M. Hascoët, “Focus-based filtering + clustering technique for power-law networks with small world phenomenon,” in _VDA’06: Visual Data Analysis - SPIE-IS &T Electronic Imaging_, vol. 6060. SPIE P., U.S., 2006, pp. 001–012.
  * [26] M. Kreuseler and H. Schumann, “A flexible approach for visual data mining,” vol. 8(1), pp. 39–51, 2002.
  * [27] A.-C. Gavin, M. Bosche, R. Krause, P. Grandi, M. Marzioch, A. Bauer, J. Schultz, J. M. Rick, A.-M. Michon, C.-M. Cruciat, M. Remor, C. Hofert, M. Schelder, M. Brajenovic, H. Ruffner, A. Merino, K. Klein, M. Hudak, D. Dickson, T. Rudi, V. Gnau, A. Bauch, S. Bastuck, B. Huhse, C. Leutwein, M.-A. Heurtier, R. R. Copley, A. Edelmann, E. Querfurth, V. Rybin, G. Drewes, M. Raida, T. Bouwmeester, P. Bork, B. Seraphin, B. Kuster, G. Neubauer, and G. Superti-Furga, “Functional organization of the yeast proteome by systematic analysis of protein complexes,” _Nature_ , vol. 415, no. 6868, pp. 141–147, January 2002. [Online]. Available: http://dx.doi.org/10.1038/415141a
  * [28] S. Hachul and M. Jünger, “Drawing large graphs with a potential-field-based multilevel algorithm,” _Graph Drawing_ , pp. 285–295, 2005.
  * [29] G. Simmel, _The sociology of Georg Simmel / translated and edited with an introduction by Kurt H. Wolff_. Free Press, Glencoe Ill, 1950.
  * [30] S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel, “The birth of the giant component,” _ArXiv Mathematics e-prints_ , Sep. 1993.
  * [31] Albert, Jeong, and Barabasi, “Error and attack tolerance of complex networks,” _Nature_ , vol. 406, pp. 378–382, 2000.